「poj適当２」の編集履歴（バックアップ）一覧に戻る
poj適当２ - (2012/07/03 (火) 16:36:15) のソース
コード記述者 堀江伸一
世にあるプログラマ養成プロジェクトの一つとして北京大学主催のプログラマ向け練習問題サイトというものがあります。
3000問程度問題が掲載されており、国際的にみても登録者の多いサイトで国際的には有名なサイトでアルゴリズムを勉強するにはちょうどいいサイトです。
問題を解くコードを書いてサーバに送信するとテストデータを使って自動採点までしてくれるので独学にはお勧めのサイトです。
http://poj.org/problemlist
ただ問題が英語か中国語で掲載されているため日本人には敷居が高いかもしれません。
そこでリンク先サイトが役に立ちます。
問題を日本語訳しており挑戦しやすくなっております。
http://wikiwiki.jp/pku/?FrontPage
リンク先サイトでは翻訳者を募集しているのですが、私はこのサイトをいいサイトだと思い簡単な問題だけ選んで翻訳に参加しています。
翻訳した内容を誰かが読んでくれていたら幸いです。
翻訳の手助けをしてもらおうと問題の分かりにくい部分を掲示板などで質問すると冷たい返事しか返ってこない世の中はちょっとつらいです。
*3036 Honeycomb Walk
ヘクス上を1マスずつm回移動してスタート地点に戻る方法は何通りあるかを求める問題。
実装がめんどくさかったので手抜きメモ化計算でアセプト。
#include<stdio.h>
#include<map>
struct point{
int y,x;
bool operator<(const point& p)const{
if(y!=p.y)return y<p.y;
return x<p.x;
}
};
void calc(int m){
int dxs[2][6]={ {1,0,-1,-1,-1,0},
{1,1,0,-1,0,1}};
int dys[6]= {0,-1,-1,0,1,1};
point p,nextP;
p.x=p.y=20;
std::map<point,int> memo[2];
std::map<point,int>::iterator it;
memo[0][p]=1;
for(int i=0;i<m;i++){
int now=i%2;
int next=(i+1)%2;
memo[next].clear();
for(it=memo[now].begin();it!=memo[now].end();it++){
int x=(*it).first.x;
int y=(*it).first.y;
//printf("\n(%d %d %d)",x,y,(*it).second);
for(int j=0;j<6;j++){
nextP.x=x+dxs[y%2][j];
nextP.y=y+dys[j];
//printf("<%d %d %d>",nextP.x,nextP.y,(*it).second);
if(memo[next].find(nextP)!=memo[next].end()){
memo[next][nextP]+=(*it).second;
}else{
memo[next][nextP]=(*it).second;
}
}
}
//printf("\n");
}
p.x=p.y=20;
printf("%d\n",memo[m%2][p]);
}
int main(){
int n,m;
scanf("%d",&n);
while(n--){
scanf("%d",&m);
calc(m);
}
}
*poj2231 Moo Volume
http://poj.org/problem?id=2231
一列に牛舎に牛が並んでいる。
牛がとなりの牛と会話するのに距離に比例したコストがかかる。
全牛の会話コストの合計を答えよという問題。
高校数学風味の問題なので数式がたてば後は簡単に答えが出ます。
#include<stdio.h>
#include <algorithm>
#include <vector>
int main(){
long long int ans=0,n,p;
std::vector<long long int> cows;
scanf("%lld",&n);
for(int i=0;i<n;i++){
scanf("%lld",&p);
cows.push_back(p);
}
std::sort(cows.begin(),cows.end());
for(long long int i=0;i<n-1;i++){
ans+=(n-i-1)*(i+1)*(cows[i+1]-cows[i]);
}
printf("%lld\n",ans*2);
}
*poj1088 滑雪
http://poj.org/problem?id=1088
スキー場の高度表がマス目で与えられる。
マス目を縦横に高いマスから低いマスへの移動のみが許される場合、一番多くのマスを滑った時の移動ます数を答えよという問題。
適当な点からスタートして一度求めた最長ルートは、他の地点からスタートしてその最長ルートへ入った場合後の移動パタンは同じになります。
これを利用してこの問題は原始的にメモ化して解きました。
グラフの問題として見ればもっと高度な解き方があるような気がしますが実質中卒レベルの私にはそういった高度な手法はかなり難しいですね。
#include<stdio.h>
#include<string.h>
#include <algorithm>
int map[103][103];
int memo[103][103];
int dxs[]={1,0,-1,0};
int dys[]={0,1,0,-1};
int saiki(int x,int y,int len){
if(memo[y][x]>0) return len+memo[y][x]-1;
int nx,ny,lenMax=-1;
for(int i=0;i<4;i++){
nx=x+dxs[i];
ny=y+dys[i];
if(map[ny][nx]<=map[y][x])continue;//高い方へ登る
lenMax=std::max(saiki(nx,ny,len+1),lenMax);
}
if(lenMax==-1){
memo[y][x]=1;
return len;
}else{
memo[y][x]=lenMax-len+1;
return lenMax;
}
}
int main(){
int rSize,cSize;
scanf("%d %d",&rSize,&cSize);
memset(map,-1,sizeof(map));//配列の外周を計算に使わない
memset(memo,-1,sizeof(memo));
for(int r=1;r<=rSize;r++){
for(int c=1;c<=cSize;c++){
scanf("%d",&map[r][c]);
}
}
int ans=1;
for(int r=1;r<=rSize;r++){
for(int c=1;c<=cSize;c++){
ans=std::max(saiki(c,r,1),ans);
}
}
/*for(int r=1;r<=rSize;r++){
for(int c=1;c<=cSize;c++){
printf("%d ",memo[r][c]);
}
printf("\n");
}
*/
printf("%d\n",ans);
}
*poj1458 Common Subsequence
http://poj.org/problem?id=1458
最長一致共通部分文字列を求める問題。
与えられる文字数が不明だったので適当なサイズで解。
自分で考えたメモリ圧縮手法で少しだけメモリを圧縮。
#include<stdio.h>
#include<string.h>
#include <algorithm>
bool calc(){
char w1[10002],w2[10002];
int memo[10002],l1,l2,ans=0;
memset(memo,0,sizeof(memo));
if(scanf("%s",w1)==EOF)return false;
scanf("%s",w2);
l1=strlen(w1);
l2=strlen(w2);
for(int i=0;i<l2;i++){
int nowMax=0;
for(int j=0;j<l1;j++){
if(w2[i]==w1[j]){
int tMax=std::max(nowMax,memo[j]);
memo[j]=std::max(nowMax+1,memo[j]);
nowMax=std::max(tMax,nowMax);
}else{
nowMax=std::max(nowMax,memo[j]);
memo[j]=nowMax;
}
ans=std::max(ans,memo[j]);
}
}
printf("%d\n",ans);
return true;
}
int main(){
while(calc());
}
*poj1008
マヤ暦では2種類の暦が使われているのでこれを変換する問題。
どちらかというと読解力が要求されル問題でした。
問題の意味をつかむのにやたらと時間がかかった。
ランキングを見ているとコードをもっと短くする方法が無数にあるらしい。
#include<stdio.h>
#include<map>
#include<string>
std::map<std::string,int> haabToNum;
std::string haabNames[19]={"pop", "no", "zip", "zotz", "tzec", "xul", "yoxkin", "mol",
"chen", "yax", "zac", "ceh", "mac", "kankin", "muan", "pax","koyab","cumhu","uayet"};
std::string numToTzolkin[20]={ "imix", "ik", "akbal", "kan", "chicchan", "cimi", "manik", "lamat", "muluk",
"ok", "chuen", "eb","ben", "ix", "mem", "cib", "caban", "eznab", "canac", "ahau"};
void dataSet(){
for(int i=0;i<19;i++){
haabToNum[haabNames[i]]=i*20;
}
}
int main(){
int d,y,n,d1,d2;
char dName[10];
dataSet();
scanf("%d",&n);
printf("%d\n",n);
for(int i=0;i<n;i++){
scanf("%d. %s %d",&d,dName,&y);
int calcDay=y*365+haabToNum[dName]+d+1;
y =(calcDay-1)/260;
d =(calcDay-1)%260+1;
d1=(d-1)%13+1;
d2=(d-1)%20;
printf("%d %s %d\n",d1,numToTzolkin[d2].c_str(),y);
}
}
*poj1244 Slots of Fun
三角形にボールが並べられボールには小文字のアルファベットが書かれている。
同じ文字の書かれたボールを繋げて正三角形を作れるなら、そのアルファベットの集合を辞書順で出力せよ。
三角形の段数は12段まで。
データは段数とその次にボールの文字を表すデータが与えられる。
与えられるデータは上の段から下の段へ左詰め優先で対応する。
ボールの半径を1とするなら一段の縦方向の差は√3となることに注意せよ。
問題のサイズが小さいことと、賢い方法を思いつかなかったので全ての3点の組み合わせで全探索しボールの数M＾３の計算量で解きました。
回転行列を使えばM^2*logMの計算量で済みますが、そこまでしなくても解けるサイズです。
#include<stdio.h>
#include<vector>
#include<math.h>
struct point{
double x,y;
};
double dlen(point p1,point p2){
return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
}
double queal(double l1,double l2){
return (l1-0.0001<l2 && l2<l1+0.0001);
}
int main(){
int n;
std::vector<point> ps[30];
point p;
char ss[200];
while(1){
scanf("%d",&n);
if(n==0)break;
scanf("%s",ss);
for(int i=0;i<30;i++)ps[i].clear();
int count=0;
for(int y=1;y<=n;y++){
for(int x=0;x<y;x++){
p.y=(double)(y-1)*sqrt(3.0)+1.0;
p.x=n-y+x*2+1;
ps[ss[count]-'a'].push_back(p);
count++;
}
//printf("\n");
}
count=0;
for(int i=0;i<30;i++){
int size=ps[i].size();
//printf("\n%c %d\n",i+'a',size);
bool hit=false;
for(int j=0;j<size;j++){
for(int k=j+1;k<size;k++){
for(int l=k+1;l<size;l++){
double l1=dlen(ps[i][j],ps[i][k]);
double l2=dlen(ps[i][j],ps[i][l]);
double l3=dlen(ps[i][k],ps[i][l]);
//printf("<%c %lf %lf %lf>",i+'a',l1,l2,l3);
if(queal(l1,l2)&&queal(l2,l3)){
count++;
hit=true;
break;
}
}
if(hit==true)break;
}
if(hit==true) break;
}
if(hit==true){
printf("%c",i+'a');
}
}
if(count==0)printf("LOOOOOOOOSER!");
printf("\n");
}
}
*poj1247 Magnificent Meatballs
http://poj.org/problem?id=1247
円の上に時計回りに数字が描かれていて数字には時計回りに1からｎまで番号が付いている。
円の周りを1からスタートするsum氏とｎから反時計回りにスタートするElla氏が互いに出会うまで数字を合計しながらまわり数字の計を2等分できるならその峰を問題で指定されていう法方で表示。
分かりやすく言えば1～ｍまでとｍ+1～ｎまでに分割した時sum(1～ｍ)=sum(m+1,n)となるなら分割点ｍを表示せよ。
無理ならその峰をNo equal partitioning.と表示すること。
#include<stdio.h>
int main(){
int n,v,memo[40];
while(1){
scanf("%d",&n);
if(n==0)break;
memo[0]=0;
for(int i=1;i<=n;i++){
scanf("%d",&v);
memo[i]=v+memo[i-1];
}
bool hit=false;
if(memo[n]%2==0){
for(int i=1;i<n;i++){
if(memo[n]/2==memo[i]){
hit=true;
printf("Sam stops at position %d and Ella stops at position %d.\n",i,i+1);
}
}
}
if(hit==false)printf("No equal partitioning.\n");
}
}
*poj3390
英語の文章が与えられるので各行を指定された文字数に近い文字数になるように改行を入れていく。
各行に対して(指定された文字数ｍ-その行の文字数)^2でペナルティが加算され、ペナルティの総計が最小になるように改行を入れる問題。
この問題はけっこう悩みました。
何個目の単語で区切ったとき、その時のペナルティがいくらになるかだけが大事で実は何行目かは全く関係ない。
という高校生でも気付きそうなことに気づいたとたん簡単な問題に変化した問題でした。
#include<stdio.h>
#include<string.h>
#include <algorithm>
void setData(){
const int max=10000*10000;
int memo[10003],textLens[10003];
int n,m;
scanf("%d %d",&m,&n);
for(int i=0;i<n;i++){
scanf("%d",&textLens[i]);
memo[i+1]=max;
}
memo[0]=0;
for(int i=0;i<n;i++){
int nowLen=-1;
int nowScore=memo[i];
for(int j=i;j<n;j++){
nowLen+=1+textLens[j];
if(nowLen>m) break;
memo[j+1]=std::min(nowScore+(m-nowLen)*(m-nowLen),memo[j+1]);
}
}
printf("%d\n",memo[n]);
}
int main(){
int t;
scanf("%d",&t);
while(t--){
setData();
}
}
*poj 1014
ビー玉が20000個ある。
どのビー玉も1～6までの価値がつく。
二人の人が、価値の合計が同じになるようにビー玉を2人で分けるとき分けることができるならＯＫをできないならＮｏを意味する文章を出力せよ。
動的計画法に枝刈で力づくで解いたけどもう少し賢い解法があるような気もする。
この問題、実は1～6までの価値が作れれば、ビー玉が何万個あろうが二人で分けることが出来るのですがそこまでしなくても計算が間に合いそうなので手抜きしました。
#include<stdio.h>
#include<string.h>
bool memo[60001];
bool setData(int no){
int nums[6],sum=0,max=0;
memset(memo,false,sizeof(memo));
memo[0]=true;
for(int i=0;i<6;i++){
scanf("%d",&nums[i]);
sum+=(i+1)*nums[i];
}
if(sum==0) return false;
if(no>1)printf("\n");
printf("Collection #%d:\n",no);
if(sum%2==1){
printf("Can't be divided.\n");
}else{
sum/=2;
for(int i=0;i<6;i++){
for(int j=max;j>=0;j--){
if(memo[j]==false) continue;
int num=j;
for(int k=1;k<=nums[i];k++){
num+=(i+1);
if(num>sum || memo[num]==true) break;
memo[num]=true;
max=max>num?max:num;
}
}
}
if(memo[sum])printf("Can be divided.\n");
else printf("Can't be divided.\n");
}
return true;
}
int main(){
int no=1;
while(setData(no)){
no++;
}
}
*poj 1517
eの近似値を求める漸化式を計算する問題。
3分で解ける肩慣らし問題ですね。
#include<stdio.h>
int main(){
printf("n e\n- -----------\n");
double fact=1,n=1;
printf("0 1\n1 2\n2 2.5\n");
for(double i=0;i<10;i++){
if(i>2)printf("%d %.9lf\n",(int)i,n);
fact=((i+1)*fact);
n+=1/fact;
}
}
*poj 3199
ｄ枚のCDをN人に分けるとき何通りの分け方があるかを出力する問題。
桁あふれが起こる可能性が考慮して安全策で多倍長整数で対処。
long long intでも間に合ったかな？
#include<stdio.h>
#include<string.h>
const int last=30;
char nums[27][last];
void calc(int i,int num){
int up=0,t;
for(int p=last-1;p>2;p--){
t=nums[i-1][p]*num+up%10;
nums[i][p]=t%10;
up=up/10+t/10;
}
}
void print(int num){
int sp;
for(sp=0;sp<last;sp++)if(nums[num][sp]!=0)break;
for(int p=sp;p<last;p++){
printf("%c",nums[num][p]+'0');
}
printf("\n");
}
bool setData(){
int n,d;
scanf("%d %d",&n,&d);
if(n==0&&d==0)return false;
memset(nums,0,sizeof(nums));
nums[0][last-1]=1;
for(int i=1;i<=d;i++){
calc(i,n);
}
print(d);
return true;
}
int main(){
while(setData()){
}
}
*poj3126
4けたの素数が二つS,Gが与えられる。
Sのケタを一つだけ変化させて4桁の素数に変化させる操作を繰り返す。
最小の操作回数でSをGに変化させた場合何回の操作で終わるかを出力する問題。
とりあえず幅優先探索で力づくで求めたけど、もっと賢い方法がありそうな問題でもある。
最初に素数のグラフを作って、ワーシャルフロイド法で解けば速度出たかな？
#include<stdio.h>
#include<set>
#include<queue>
struct so{
int nums[4],turn;
bool operator<(const so& s)const{
for(int i=0;i<4;i++){
if(nums[i]!=s.nums[i])return nums[i]<s.nums[i];
}
return false;
}
void set(int num){
for(int i=3;i>=0;i--){
nums[i]=num%10;
num/=10;
}
turn=0;
}
};
void setSosuu(std::set<so>& memo){
bool sosuu[10000];
so s;
memset(sosuu,true,sizeof(sosuu));
for(int i=3;i<10000;i+=2){
if(sosuu[i]==false) continue;
if(i>999){
s.set(i);
memo.insert(s);
}
for(int j=i*3;j<10000;j+=i*2){
sosuu[j]=false;
}
}
}
int main(){
std::set<so> memo;
setSosuu(memo);
int n,num1,num2;
so s1,s2;
scanf("%d",&n);
while(n--){
scanf("%d %d",&num1,&num2);
s1.set(num1);
s2.set(num2);
std::queue<so> qu;
std::set<so> spents;
qu.push(s1);
spents.insert(s1);
int t;
while(!qu.empty()){
s1=qu.front();
qu.pop();
if(!(s1<s2)&&!(s2<s1)) break;
s1.turn++;
for(int i=0;i<4;i++){
for(int j=0;j<=9;j++){
t=s1.nums[i];
s1.nums[i]=j;
if(spents.find(s1)==spents.end() && memo.find(s1)!=memo.end()){
spents.insert(s1);
qu.push(s1);
}
s1.nums[i]=t;
}
}
}
printf("%d\n",s1.turn);
}
}
*poj 3126
サンプルとして与えられた表から規則性を見出し、その規則性に沿った表を出力する問題。
うーんforが2回に分かれているの何とかなったかも？
#include<stdio.h>
#include<string.h>
int main(){
int n,s;
char map[21][21];
scanf("%d %d",&n,&s);
memset(map,'0',sizeof(map));
for(int c=0;c<n;c++){
for(int r=0;r<=c;r++){
map[r][c]=s+'0';
s=s%9+1;
}
}
for(int r=0;r<n;r++){
for(int c=0;c<n;c++){
printf("%s%c",c==0?"":" ",map[r][c]=='0'?' ':map[r][c]);
}
printf("\n");
}
}
*poj3176
パスカルの三角形と同じ配置の数字を上からスタートして右下か左下か選びながら移動していったとき、通ったルート上の数字の合計が最大になるルートを探すという問題。
ほとんど同じ問題が別にあったので前の問題を参考にしながら動的計画法でアセプト。
#include<stdio.h>
#include<string.h>
#include <algorithm>
int main(){
int n,nowR,nextR,ans=0;
int memo[2][352];
int num;
scanf("%d",&n);
memset(memo,0,sizeof(memo));
for(int i=1;i<=n;i++){
nowR =i%2;
nextR=(i+1)%2;
for(int j=1;j<=i;j++){
scanf("%d",&num);
memo[nextR][j]=num+std::max(memo[nowR][j-1],memo[nowR][j]);
ans=std::max(ans,memo[nextR][j]);
}
}
printf("%d\n",ans);
}
*poj3100
B=A^nのBとｎからAを求める問題、ただしA、B、Nは3つとも整数。
北京大の問題は中学生でもとける問題から大学生でも悩む問題までそろっていますが、これは高校生向けの問題のようです。
#include<stdio.h>
#include <stdlib.h>
#include <math.h>
bool setData(){
double a,n,b;
int sa=1000001,ans,d,t;
scanf("%lf %lf",&b,&n);
if(b==0&&n==0) return false;
a=pow(b,1/n);
d=(int)a;
if(d>1)d--;
for(int i=d;i<d+3;i++){
t=abs(b-(int)pow(i,n));
if(t<sa){
sa=t;
ans=i;
}
}
printf("%d\n",ans);
return true;
}
int main(){
while(setData()){
}
}
*poj3365
縦横サイズが決まっている板からまず円を切りぬき、次に四角形の縦横と平行に切断を入れて四角い板を切りだす。
このとき、板を丸く曲げて円と接合して上に穴のあいた円柱を作るとき、作ることのできる円柱の最大値を求めよという問題。
縦と横どちらを円中との接合部に使うかということに注意さえすれば高校生に出すとちょうどよさそうな問題ですね。
#define _USE_MATH_DEFINES
#include<stdio.h>
#include<math.h>
#include <algorithm>
int main(){
double w,h,r,v,v2;
while(1){
scanf("%lf %lf",&w,&h);
if(w==0&&h==0)break;
r=h/(2.0*(1.0+M_PI));//高さを円との接合部に使う場合
if(2.0*r>w)r=w/2.0;
v=r*r*M_PI*w;
r=w/(2.0*M_PI);//横を円との接合部に使う場合
v2=r*r*M_PI*(h-2.0*r);
v=std::max(v,v2);
printf("%.3lf\n",v);
}
}
*poj 3366
与えられた単語を複数形にする問題。
特別な場合のリストが最初に与えられ、それ以外は指定されたルールで複数形にチェンジする問題。
末尾をiesに変形する場合のif文のルールが一行だけわからなかったので、掲示板で変形ルールを質問して解いた。
#include<stdio.h>
#include<string>
#include<map>
#include<iostream>
void change(){
std::map<std::string,std::string> memos;
std::string text,cText,lastTwo;
char last,t;
int l,n;
scanf("%d %d",&l,&n);
while(l--){
std::cin>>text>>cText;
memos[text]=cText;
}
while(n--){
std::cin>>text;
last=text[text.size()-1];
if(text.size()>1)lastTwo=text.substr(text.size()-2);
else lastTwo=" ";
t=lastTwo[0];
if(memos.find(text)!=memos.end()){
text=memos[text];
}else if(!(t=='a'||t=='i'||t=='u'||t=='e'||t=='o')&&last=='y'){
text[text.size()-1]='i';
text+="es";
}else if(last=='x' || last=='s' || last=='o' || lastTwo=="ch" || lastTwo=="sh"){
text+="es";
}else{
text+="s";
}
std::cout<<text<<"\n";
}
}
int main(){
change();
}
*poj1316
1949年だがに発見された単調増加数列の初項の集合を求める問題。
求める範囲が狭いので力づくで求めた。
#include<stdio.h>
#include<string.h>
bool hits[10002];
int main(){
int num,next;
memset(hits,false,sizeof(hits));
for(int i=1;i<10000;i++){
if(hits[i]==true)continue;
next=num=i;
while(next<10000){
while(num>0){
next+=num%10;
num/=10;
}
if(hits[next]==true)break;
hits[next]=true;
num=next;
}
}
for(int i=1;i<9994;i++){
if(hits[i]==true)continue;
printf("%d\n",i);
}
}
*poj3331
自然数ｎが与えられる。
ｎ！の中に出てくる数字のうち0～9までのどれか指定された数字がN!の中に何個出てくるかを数えて返す問題。
#include<stdio.h>
#include<string.h>
const int last=1300;
char nums[367][last];
void calc(int i){
int up=0,t;
for(int p=last-1;p>2;p--){
t=nums[i-1][p]*i+up%10;
nums[i][p]=t%10;
up=up/10+t/10;
}
}
void count(int num,int b){
int sp,ans=0;
for(sp=0;sp<last;sp++)if(nums[num][sp]!=0)break;
for(int p=sp;p<last;p++){
if(nums[num][p]==b)ans++;
}
printf("%d\n",ans);
}
void setData(){
memset(nums,0,sizeof(nums));
nums[1][last-1]=1;
for(int i=2;i<367;i++){
calc(i);
}
}
int main(){
setData();
int t,d,n;
scanf("%d",&t);
while(t--){
scanf("%d %d",&d,&n);
count(d,n);
}
}
*poj3390
文字列を改行で区切り各行が指定された文字数に近づくように配置する問題。
よりよい区切り方は、(指定された文字数-その行の文字数)^2の計算を各行についておこない、この合計が最小になる場合が最も良い状態。
最も良い状態のスコアを出力せよという問題。
動的計画法で挑戦。
今日はサーバのメンテなのか採点してくれないらしい？
#include<stdio.h>
#include<string.h>
void setData(){
const long long max=((long long int)10000)*10000*10000;
long long int memo[2][10003],ans=max,score;
bool oks[2][10003];
int textLens[10003];
int n,m;
scanf("%d %d",&m,&n);
for(int i=0;i<n;i++)scanf("%d",&textLens[i]);
memset(memo,0,sizeof(memo));
memset(oks,false,sizeof(oks));
oks[0][0]=true;
int nowLen,nowRow,nextRow,ep=1,tenpEP=0;
for(int row=0;row<n;row++){
nowRow=row%2;
nextRow=(row+1)%2;
memset(memo[nextRow],0, sizeof(memo[nextRow]));
memset( oks[nextRow],false,sizeof(oks[nextRow]));
int count=0;
for(int sp=row;sp<ep;sp++){
if(oks[nowRow][sp]==false) continue;
if(memo[nowRow][sp]>=ans) continue;
count++;
nowLen=-1;
for(int nowP=sp;nowP<n;nowP++){
nowLen+=textLens[nowP]+1;
if(nowLen>m)break;
score=memo[nowRow][sp]+(m-nowLen)*(m-nowLen);
if(memo[nextRow][nowP+1]==0){
memo[nextRow][nowP+1]=score;
}else if(memo[nextRow][nowP+1]>score){
memo[nextRow][nowP+1]=score;
}
oks[nextRow][nowP+1]=true;
tenpEP=tenpEP>nowP+2?tenpEP:nowP+2;
}
ep=ep>tenpEP?ep:tenpEP;
if(memo[nextRow][n]!=0&&ans>memo[nextRow][n])ans=memo[nextRow][n];
}
if(count==0) break;
}
printf("%d\n",ans==max?0:ans);
}
int main(){
int t;
scanf("%d",&t);
while(t--){
setData();
}
}
*poj3372
車座になった生徒に時計回りに1～ｎまで番号が付いている。
先生が時計回りに回りにまわりながら生徒にキャンデーを与えていくが、最初は1番の生徒に、次は2番の生徒に、次は一人飛ばして4番の生徒に、次は2人飛ばして7番の生徒にと飛ばす人数を一人ずつ増やしながら生徒にキャンディを与えていく。
生徒の人数ｎが決まった時、全ての生徒が最低一個以上キャンディーをもらえるかを求める問題。
数式をいくらいじりまわしても理屈が分からなかったのでｎが決まった時の数列の変化をEXCELで表にしてみるとどうやら2の乗数のときのみ全生徒がキャンディをもらえる規則性を発見。
理屈が不明なので合格できるかどうかは運次第だったが幸運にもアセプトとなりました。
理屈不明で解いたのでほとんどカンニングのような解き方かもしれない、、、
#include<stdio.h>
int main(){
int n;
while(scanf("%d",&n)!=EOF){
while(n%2==0){
n/=2;
}
printf("%s\n",n==1?"YES":"NO");
}
}
*poj3302
文字列を前から見て、何文字か抜き出し、後ろから見て何文字か抜き出し、抜き出した結果が指定された文字列になるかを求める問題。
前と後ろから参照して文字列の添え字を二つ使うだけで解けます。
#include<stdio.h>
#include<string.h>
bool hit(char text[101],char search[101],bool revers){
int size=strlen(text);
int sizeS=strlen(search);
int p1,p2=0;
for(int i=0;i<size;i++){
p1=revers?size-1-i:i;
if(text[p1]==search[p2]){
p2++;
if(sizeS==p2)return true;
}
}
return false;
}
int main(){
int n;
char text[102],search[102];
bool ok;
scanf("%d",&n);
while(n--){
scanf("%s %s",text,search);
ok=hit(text,search,true)||hit(text,search,false);
printf("%s\n",ok?"YES":"NO");
}
}
