問題はこちら No.75 回数の期待値の問題 - yukicoder要求誤差がゆるいのでモンテカルロ int main(){ int s=0,i,t,k; scanf("%d",&k); for(i=0;i<100000;i++){ for(t=k;t;){ //残りマス数tが0でなければ s++; t-=rand()%6+1; //サイコロを振って if(t<0)t=k; …

問題はこちら No.73 helloworld - yukicoderhelloworldに登場しない文字はどうでもいいので除いておく 文字の並びはそれぞれ固めておくのが良い h..e..l..o..w..o..r..l..d.. と並べた時、helloworldの作り方を考える l,o以外は、その文字数だけ選び方がある…

問題はこちら No.72 そろばん Med - yukicoder前の問題と同じなので基本的な考え方は省略先にnの剰余をとっておけば、平方しても8Byteの範囲で収まるが n≡m mod pでもfloor(n*n/4)≡floor(m*m/4) mod pとは限らない しかし n≡m mod 2pならfloor(n*n/4)≡floor(…

問題はこちら No.71 そろばん - yukicoderN個のうちk個を上の珠として扱うと 上の珠の状態はk+1通り 下の珠の状態は(N-k)+1通りなので 扱える最大の値は(k+1)(N-k+1)-1となる ところでこれは、和が一定の2数の積を最大化する問題なので、2数が近くなるように…

問題はこちら No.70 睡眠の重要性！ - yukicoder0≦a,b＜pのとき、a-bをpで割ったあまりは(a-b+p)%pで計算できる h時m分を、1日が始まってから(h*60+m)分が経過していると見れば h1時m1分からh2時m2分までの時間は(h2*60+m2-(h1*60+m1)+1440)%1440で求める事…

問題はこちら No.69 文字を自由に並び替え - yukicoderBにある文字がAにも使われているか順番に調べる int main(){ char a[11]={},b[11]={}; int i,j,n; scanf("%s%s",a,b); n=strlen(a); for(i=0;i

問題はこちら No.67 よくある棒を切る問題 (1) - yukicoder「ある長さxの棒をK本つくれるか？」という問題には ΣLi/x がK以上か否かを見ることで簡単に答えることができる これを用いて2分探索をする int main(){ int a[200010],i,t,n; long k,s; double u=1…

問題はこちら No.65 回数の期待値の練習 - yukicoder問題文中の漸化式にしたがってそのまま実装 int main(){ double e[30]={}; int k; scanf("%d",&k); while(k--)e[k]=(e[k+1]+e[k+2]+e[k+3]+e[k+4]+e[k+5]+e[k+6])/6+1; printf("%f",e[0]); return 0; } 要…

問題はこちら No.63 ポッキーゲーム - yukicoder1回につき2Kずつ食べていくので、食べる回数は Lが2Kの倍数の時L/2K-1 Lが2Kの倍数出ない時floor(L/2K) となる これは「L/2Kの切り上げ-1」なのでfloor((L-1)/2K)とまとめられる 食べる量はこれのK倍 int main…

問題はこちら No.58 イカサマなサイコロ - yukicoderDPすれば正確な値が求められるけど、誤差が緩いのでモンテカルロ int main(){ int n,k,i,j,t,s; scanf("%d%d",&n,&k); s=0; for(i=0;i<1e6;i++){ t=0; for(j=0;j<k;j++)t+=rand()%3+4; for(;j<n;j++)t+=rand()%6+1; for(j=0;j<n;j++)t-=rand()%6+1; if(t>0)s++; } printf("%f",s/1e6); return 0; }</k;j++)t+=rand()%3+4;>…

問題はこちら No.57 ミリオンダイス - yukicoderサイコロ1個の期待値は3.5 よって「期待値の線形性」から3.5*Nが答え b;main(){b=!printf("%f",atoi(gets(&b))*3.5);} 45B

問題はこちら No.56 消費税 - yukicoder 「税抜価格+税」で計算するだけ a;main(b){scanf("%d%d",&a,&b);a=!printf("%d",a+a*b/100);} 57B

問題はこちら No.55 正方形を描くだけの簡単なお仕事です。 - yukicoderもし正方形になり得る3点なら その3点は直角二等辺三角形になっているはず なので、「その点の周りが直角で、それをなす辺の長さが等しい」というような点が3つの中にあるかどうか探す …

問題はこちら No.53 悪の漸化式 - yukicoder三項間漸化式なので高校数学を思い出して一般項を求める特性方程式は 4λ^2=19λ-12 なので λ=3,3/4 一般項は a[n]=p*3^n+q*(3/4)^n の形になる n=0,1を代入してp=0,q=4 つまり一般項はa[n]=4*(3/4)^nこれはn→∞で0に…

問題はこちら No.52 よくある文字列の問題 - yukicoder全探索 Cだと、重複を除いた要素数を数えたり、文字列の集合を作ったり、いちいち困難 char s[11],a[1030][11]; int c(char*a,char*b){return strcmp(a,b);} int main(){ int t,l,r,n,i; n=strlen(gets(…

問題はこちら No.51 やる気の問題 - yukicoder実際に毎日作業していくだけ D≦10^5なのでint型だと2乗するとオーバーフローする int main(){ a,b; scanf("%d%d",&a,&b); for(;b>1;b--)a-=a/b/b; printf("%d",a); return 0; } 処理系依存の未定義動作にまとめ…

問題はこちら No.49 算数の宿題 - yukicoder数→記号→数→記号→数→… と順番に読み込みつつ、前から計算していけば良い int main(){ int a,s,p; scanf("%d",&s); while(p=getchar()-10){ //改行が来るまで読み込み scanf("%d",&a); if(p=='+'-10)s*=a;else s+=a…

問題はこちら No.48 ロボットの操縦 - yukicoderまず、各方向の移動には、以前やったとおり、「距離÷1歩の長さ」の切り上げだけかかる 向きの変更には、Yが負なら必ず2回必要で、そうでないなら、まずY軸方向の移動を消化した後、X!=0なら横を向く必要がある…

問題はこちら No.47 ポケットを叩くとビスケットが２倍 - yukicoderk回叩くと最大2^k枚になる 逆に任意のn≧1に対して、2^(k-1)＜n≦2^k … (★)であるとき、ちょうどk回でn枚にできる なぜならポケットを叩くと、「ポケットに入れていた枚数だけ増える」ので k-…

問題はこちら No.46 はじめのn歩 - yukicoderb/aの切り上げ int main(){ int a,b; scanf("%d%d",&a,&b); printf("%d",(b-1+a)/a); return 0; } 今回はa,b>0なので (b-1+a)/a=(b-1)/a+1 となる a; main(b){ scanf("%d%d",&a,&b); a=!printf("%d",--b/a+1); } …

問題はこちら No.45 回転寿司 - yukicoder「今の皿をとった時の最高点」「取らなかった時の最高点」をそれぞれ保存する int main(){ int n,i,p=0,q=0,t; //pがとった時、qが取らなかった時 scanf("%d",&n); while(n--){ scanf("%d",&i); t=q+i; //今の皿をと…

問題はこちら No.44 DPなすごろく - yukicoderあるマスへは、その1マス手前から来る方法と2マス手前から来る方法がある なのでフィボナッチ数列になるこれを int main(){ int a; long p=1,q=0,t; scanf("%d",&a); while(a--){ t=p+q; q=p; p=t; } printf("%l…

問題はこちら No.43 野球の試合 - yukicoder自分のチームの未消化試合は全勝すれば良さそうに見えるが、 「1位が2チームいてもその次は2位」というルールのせいで 「あえて負けることで、他チーム同士が同順位となり順位が上がる」という現象が起こる 具体的…

問題はこちら No.41 貯金箱の溜息（EASY） - yukicoder111111円に満たない金額は1円玉で払うしか無いので、全体を111111で割ることで問題は次のように読み替えられる 「floor(M/111111)円以下を、1～9円玉を使って払う方法は何通りか」 ということでDP M≦10^…

問題はこちら No.40 多項式の割り算 - yukicoder上の次数から割り算をしていくだけ 筆算を思い浮かべれば分かるように、x^3-xで割ると 最高次数の係数を2つ下の次数に足していくことになる サンプルに挙げられている例では（右が高次なことに注意） 0 -5 0 4…

問題はこちら No.39 桁の数字を入れ替え - yukicoder上位のほうにある小さい数字と下位の方にある大きい数字を入れ替えればいい int main(){ int i,j,k,m,n; char s[20]; gets(s); n=strlen(s); for(i=0;i<n;i++){ m=0; for(j=i+1;s[j];j++)if(s[j]>=m)m=s[k=j]; //同じ数字なら下位のものと入れ替えた</n;i++){>…

問題はこちら No.36 素数が嫌い！ - yukicoder要するに3個以上の素数の積になってればいい なので次のような関数fを作った long f(long x){ //この関数は、引数をその最小素因数で1回割った値を返す long i; if(x%2==0)return x/2; for(i=3;i*i<=x;i+=2)if(x…

問題はこちら No.35 タイパー高橋 - yukicoder文字数の合計と打てた文字数の合計を保存していく int main(){ int n,s=0,m=0,t,c; char a[101]; scanf("%d",&n); while(n--){ scanf("%d%s",&t,a); c=strlen(a); t=t*12/1000; s+=t>c?c:t; m+=c; } printf("%d …

問題はこちら No.32 貯金箱の憂鬱 - yukicoderこれが int main(){ int a,b,c; scanf("%d%d%d",&a,&b,&c); c+=a*100+b*25; printf("%d",c/100%10+c/25%4+c%25); return 0; } こうじゃ a,b; main(c){ a=scanf("%d%d%d",&a,&b,&c)

問題はこちら No.29 パワーアップ - yukicoderまず各アイテムが何個あるか数える 同じアイテムが2個以上あれば2個で使うのが良いので 2個ずつ使っていって、余ったものをかき集めて4個使う int main(){ int a[11]={},n,t,i,s; scanf("%d",&n); n*=3; while(n…