問題はこちら No.314 ケンケンパ - yukicoderDP a:「パで終わった」 b:「ケンが1回で終わった」 c:「ケンが2回で終わった」とする。このとき次の1歩を進むと aからはbになり、bからはaかcになり、cはaになる。よってこれにより漸化式が立つ。 1歩目はケンで…

問題はこちら No.313 π - yukicoder円周率を20万桁目まで正しく計算するプログラムを書く問題……ではない 「0～9の各数字が何回登場するか」がわかれば、どこの値が間違っているかわかる 幸いsample1.txtに、整数部以外の20万桁は正しいものがおいてあるので…

問題はこちら No.312 置換処理 - yukicoder少し考えると、「2より大きな最小の約数を求めよ」という問題だとわかる N≦10^12なのでN以下のすべての数で割ることは出来ないが、2を無視するので普通の素数判定とは微妙に違うことに注意が必要 int main(){ long …

問題はこちら No.311 z in FizzBuzzString - yukicodera:「3の倍数かつ5の倍数」1個につきzが4個 b:「5の倍数でない3の倍数」1個につきzが2個 c:「3の倍数でない5の倍数」1個につきzが2個 ところで1つ目の条件はバラして2つ目と3つ目にまとめることができ B:…

問題はこちら No.306 さいたま2008 - yukicoder元ネタは高校入試の問題らしいけど、むしろ中学入試の難問としてよくみる問題のように思うそういうわけで中学数学くらい丁寧に証明してみよう。 Aをy軸に対称に移してA'としAA'とy軸の交点をHとする。 AH=A'H、…

問題はこちら No.304 鍵(1) - yukicoder総当りすれば良い int main(){ int i; char s[20]; for(i=0;i<1000;i++){ printf("%03d\n",i); fflush(0); scanf("%s",s); if(strcmp(s,"unlocked")==0)break; } return 0; } 文字列をint型に読み込むいつもの暴挙をや…

問題はこちら No.300 平方数 - yukicoder「平方数⇔素因数分解した時の指数が全て偶数」なので、Xを素因数分解して、指数が奇数のものを掛けあわせれば良い 最悪でもX自身をかければ平方数になるので、Y≦X≦10^12 int main(){ long x,y=1,i,p; scanf("%ld",&x)…

問題はこちら No.299 蟻本が読めない - yukicoder初項316、公差52の等差数列の第N項を求める問題 公式としては316+52*(N-1)とするのだろうけど、この-1がいつも邪魔に思うので、第0項を316-52=264として 264+52*Nと求めるほうが好き。 N≦10^10なので、intだ…

問題はこちら No.296 n度寝 - yukicoder1回寝過ごす度にT分経過するので、N度寝すると、T*(N-1)分経過する T*N≦1.44*10^9なのでオーバーフローはしない int main(){ int n,h,m,t; scanf("%d%d%d%d",&n,&h,&m,&t); m+=(n-1)*t; printf("%d\n%d",(h+m/60)%24,m…

問題はこちら No.294 SuperFizzBuzz - yukicoder整数が3の倍数である必要十分条件は、各位の和が3の倍数であること。 5の倍数である必要十分条件は、一の位が0or5であること。 これより、問題は「各位の数字が'3'or'5'で、1の位が5であり、'5'の個数が3の倍…

問題はこちら No.293 4>7の世界 - yukicoder上位から見ていって、一致しなくなったところを比べれば良い int main(){ int p=1000000000,x,y,a,b; scanf("%d%d",&a,&b); do{ x=a/p%10; y=b/p%10; //これでx,yにはa,bの上から何桁目かが入る p/=10; }while(x==…

問題はこちら No.292 芸名 - yukicoder読み込んだ文字列を1文字ずつ見ていって、tでもuでも無いところを出力していけば良い int main(){ char s[60]; int i,t,u; scanf("%s%d%d",s,&t,&u); for(i=0;s[i];i++)if(i!=t&&i!=u)putchar(s[i]); return 0; } 基本 …

問題はこちら No.290 1010 - yukicoder問題名がヒントになっているうまい問題 問題文は要するに「繰り返しが登場するか」ということ なのでもし同じ文字が2つ連続していればYES 同じ文字が連続しないなら、それは1010…か0101…という列になるので、N≧4なら「1…

問題はこちら No.289 数字を全て足そう - yukicoder読み込んだ文字が数字かどうか確かめて足す int main(){ char s[10010]; int i,m=0; gets(s); for(i=0;s[i];i++)if(s[i]>='0'&&s[i]<='9')m+=s[i]-'0'; printf("%d",m); return 0; } sは半角英数字からなる…

問題はこちら No.287 場合の数 - yukicoder意図としてはDPなのだろうけど、数学的考察により一発で求められる各変数をN-a,N-b,...と置き換えることにより、1つ目の条件式はa+...+h=2Nとしてよい 2つ目以降の条件を忘れて、a+...+h=2Nを満たすようなa～hの組…

問題はこちら No.286 Modulo Discount Store - yukicoderyukicoder No.90 品物の並び替え - メモ これと同様にしてbitDP ほとんど同じなので通常解説は省略 int main(){ int d[99999]={},a[20],i,j,k,n,m; scanf("%d",&n); for(i=0;i<n;i++)scanf("%d",a+n); for(i=0;i<1<<n;i++){ //既に買った商品のbitが立っている for(j=0;j<n;j++){ //j番目の商品を新たに買う(jは0-based) if(i>>j&1)cont…</n;i++)scanf("%d",a+n);>

問題はこちら No.285 消費税２ - yukicoderd≦10^12なので、1.08を書けてもせいぜい15桁の精度があればよい double型は約15.9桁の精度があるので、多分そのまま計算しても多分大丈夫 int main(){ long d; scanf("%ld",&d); printf("%.2f",d*1.08); //出力形式…

問題はこちら No.281 門松と魔法(1) - yukicoder3本の竹をa,b,cとする 門松列にするにはbを最大か最小にしなければならない #define max(p,q)(p>q?p:q) int main(){ int a,b,c,ta,tb,tc,d,s,t; scanf("%d%d%d%d",&d,&ta,&tb,&tc); ta>tc?ta^=tc^=ta^=tc:0; /…

問題はこちら No.280 歯車の問題(1) - yukicoder歯数ZaとZbの歯車があり、前者が|θa|回転したとき後者は|θb|=|θa|*Za/Zbだけ回転するとの事だったので、 Zbの歯車が更にZcの歯車と接している時、|θc|=|θb|*Zb/Zc=|θa|*Za/Zb*Zb/Zc=|θa|*Za/Zc ここから帰納的…

問題はこちら No.279 木の数え上げ - yukicoder「tの個数」「rの個数」「(eの個数)/2」の中で一番小さいものが答え #define min(a,b)(a

問題はこちら No.278 連続する整数の和(2) - yukicoder前回の問題yukicoder No.276 連続する整数の和(1) - メモの考察から、σ1を約数関数として Nが偶数の時σ1(N/2)、奇数の時σ1(N)となることが分かるのでこれを求める int main(){ long s=0,i,n,m; scanf("%…

問題はこちら No.276 連続する整数の和(1) - yukicoderaから始まる連続するN個の自然数の和はaN+N(N-1)/2となる。 aは任意なのでGCD(N,N(N-1)/2)が求める答えになる（十分性は明らか。必要性はa=0,1から）ところで Nが奇数の時(N-1)は2で割り切れるのでN(N-1…

問題はこちら No.275 中央値を求めよ - yukicoderソートして中央値を求めるだけ 要素の個数が偶数の時にちょっと注意が必要 int c(int*a,int*b){return*a-*b;} int main(){ int a[1010]; int n,i; scanf("%d",&n); for(i=0;i

問題はこちら No.273 回文分解 - yukicoder不要な部分は1文字にバラしてしまえば良いので、全体でない最長の回文の長さが求める値になる int main(){ char s[99]; int i,j,k,f=1; //fはフラグ。0になったら回文が見つかった gets(s); for(i=strlen(s);f&&--i…

問題はこちら No.272 NOT回路 - yukicoder普通の解説はまあいらないでしょう int main(){ int n; scanf("%d",&n); printf("%d",1-n); return 0; } 文字として読みこめば、'0'が48で'1'が49なので1とbitxorを取ると他方に変換できる n;main(){n=!putchar(getc…

問題はこちら No.269 見栄っ張りの募金活動 - yukicoderこれはメモ化再帰が書きやすかった 予めKの分を処理しておくことでK=0の場合に帰着すると良い int a[101][20001],l[101][20001]; int f(int n,int s){ //k=0のときn人でちょうどs円払う方法 if(l[n][s]…

問題はこちら No.268 ラッピング（Easy） - yukicoder縦横高さをa,b,cとすると、各向き1周の長さは2*(a+b),2*(a+c),2*(b+c)となる。 なので、長いところの回数を少なく、短いところの回数を多くするようにすれば良い int main(){ int a,b,c,p,q,r; scanf("%d…

問題はこちら No.267 トランプソート - yukicoderカードの種類が高々52なので、ソートするのではなく「どのカードがあるか」を記録して、前から順番に出力すれば良い int main(){ int n,i,j,card[99][99]={}; char p,q,suit[]="DCHS",num[]="A23456789TJQK";…

問題はこちら No.264 じゃんけん - yukicoder手が同じなら引き分け 負けるのは(1,0)(2,1)(0,2)なのでn-kがmod 3で1になるとき 出力する英語は過去形になっているので気をつけましょう（） int main(){ int n,k; scanf("%d%d",&n,&k); if(n==k)puts("Drew"); …

問題はこちら No.257 N言っちゃダメゲーム (3) - yukicoder先手後手の選択は次のように読み替えられる 「あなたは先手であり、最初の1手に限り0が認められる」 ということで、以前やったとおり(N-1)%(K+1)を初手で言い、後はK+1ずつ増やした値を言っていけば…