メモ

yukicoderでゆるふわgolf

yukicoder No.555 世界史のレポート

問題はこちら No.555 世界史のレポート - yukicoderDP解法との賢い数学解法がある・DP解 N文字以上を作る最小コスト=min{ちょうどK文字を作る最小コスト|K≧N} K文字を作る際には、その過程で必ずK/2文字以上の状態を経由するので、Kの上限は2Nとしてよい。 …

yukicoder No.566 だいたい完全二分木

問題はこちら No.566 だいたい完全二分木 - yukicoder○激ヤバ解法 シャッフルすれば高確率で通る○まじめな解法 普通に完全二分木をつくると高さはK-1になる。そこで適当にいじって高さをKにする ・方針1 完全二分木を作る過程で、2と3を入れ替える。 そうす…

yukicoder No.567 コンプリート

問題はこちら No.567 コンプリート - yukicoder包除原理やるだけ(説明は後述) main(n){ scanf("%d",&n); printf("%.9f", 1 - 6*pow(5/6.,n) +15*pow(4/6.,n) -20*pow(3/6.,n) +15*pow(2/6.,n) - 6*pow(1/6.,n) ); } 事象A1,…,A6を、 A1:1が出ない … A6:6…

yukicoder No.564 背の順

問題はこちら No.564 背の順 - yukicoder最初は1位で、高い人が現れるたびに順位は1つ下がる h,n,t,S; main(){ scanf("%d%d",&h,&n); S=1; for(int i=1;i<n;i++){ scanf("%d",&t); if(t>h)S++; } printf("%d",S); if(S%10==1)puts("st"); else if(S%10==2)puts("nd"); else if(S%10==3)puts</n;i++){>…

yukicoder No.549 素材合成システム

問題はこちら No.549 素材合成システム - yukicoder合成素材の側の経験値の最終的な寄与度は高々floor(a/2) 実際に、一番経験値が高い奴をベースにし、残りを素材として順次合成していくことで最大になる。 c(int*a,int*b){return*b-*a;} a[100010],n,S; mai…

yukicoder No.561 東京と京都

問題はこちら No.561 東京と京都 - yukicoderDPやるだけ(といいつつ、後ろから見る方法しか思いつかなかったので要反省)(i-1)日目が終了した時点で東京にいるときの最大利益をT、京都にいるときの最大利益をKとおく。 i日目に東京でt、京都でk得られる場合…

yukicoder No.537 ユーザーID

問題はこちら No.537 ユーザーID - yukicoder2つの数A,Bを連結するのは、文字列として処理するのでも良いが、Cだと面倒なので計算をする 数Bの桁数はで得られるので、AとBをこの順で連結したものはで求められるNが大きいので1~√Nまでを調べる long n,s[2000…

yukicoder No.560 ふしぎなナップサック

問題はこちら No.560 ふしぎなナップサック - yukicoder算数やるだけ ナップサックの中にM円入っているとき、1回叩いた後は (2M+(M+1)+0)*1/3=M+1/3 より(M+1/3)円になる。 これはMに依らないのでこの操作をN回行うとM+N/3円になる。 (写像f(M)=M+1/3をN回…

yukicoder No.559 swapAB列

問題はこちら No.559 swapAB列 - yukicoder求めるものは転倒数と同値 先頭から見ていってAが登場する度に、それ以前に登場したBの個数を数えれば良い char s[99]; b,ans,n; main(){ gets(s); n=strlen(s); for(int i=0;i

yukicoder No.558 575検出するやつ

問題はこちら No.558 575検出するやつ - yukicoderstrstrするだけ char s[110]; main(){ gets(s); puts(strstr(s,"575")?"YES":"NO"); } 100文字をintに読み込んでも幸いREにはならず a;main(){puts(strstr(gets(&a),"575")?"YES":"NO");} 50B aをmain引数に…

yukicoder No.305 鍵(2)

問題はこちら No.305 鍵(2) - yukicoderwriter解と同じ発想 ある桁の数字を変えた時、当たり数が大きくなれば新しい方が当たり、小さくなれば古い方が当たり。これを繰り返して上の桁から順に調べていく char s[]="0000000000"; n,k,i; main(){ puts(s); ffl…

yukicoder No.557 点対称

問題はこちら No.557 点対称 - yukicoder回文と同様、上半分を決めると下半分は自動的に決まる ・n=1のとき 1,8の2通り ・nが偶数のとき 上位n/2桁を決めると、下位は自動的に決まる 先頭の位に使えるのは1,6,8,9の4通り それ以外は0,1,6,8,9の5通り よって4…

yukicoder No.554 recurrence formula

問題はこちら No.554 recurrence formula - yukicoderとする このとき よりとなりの漸化式が得られる でありなので、これにより計算できる long s[100100]; n,ans,m=1e9+7; main(){ scanf("%d",&n); if(n==1)ans=1; else{ s[1]=1; for(int i=2;i<=n;i++)s[i]…

yukicoder No.552 十分簡単な星1の問題

問題はこちら No.552 十分簡単な星1の問題 - yukicoder値が大きいので文字列として読み込む。 0のときはそのまま出力し、それ以外のときは末尾に0をつける char s[99]; main(){ gets(s); if(strcmp(s,"0")==0)puts("0"); else printf("%s0",s); } 20文字くら…

yukicoder No.548 国士無双

問題はこちら No.548 国士無双 - yukicoder「a~mのうち、いずれか1種を2つ、残りの12種を1つ含む」というのは「a~mのうち、13種いずれもを1つ以上含み、これら以外を含まない」と同値 よって、与えられた13文字にa~mを加えたものが条件をみたすかをチェッ…

yukicoder No.547 未知の言語

問題はこちら No.547 未知の言語 - yukicoderscanfを使うと空白区切りで読み込めるのでstrcmpで比較するだけ char s[11][22]; char t[11][22]; main(){ int n; scanf("%d",&n); for(int i=0;i

yukicoder No.533 Mysterious Stairs

問題はこちら No.533 Mysterious Stairs - yukicoder初期値にちょっと気をつける必要があるがDPやるだけ。 dp[昇った段数合計][直前に段数]=場合の数 dp[1000010][4];n; mod=1000000007; main(){ dp[1][1]=1; dp[2][2]=1; dp[3][1]=dp[3][2]=dp[3][3]=1; sca…

yukicoder No.538 N.G.S.

問題はこちら No.538 N.G.S. - yukicoder数学するだけ連立方程式 を解き を得る。求める答えはであるからこれに代入して となる。 は最大10^5なので2乗すると32bitの範囲に収まらないことに注意する long a,b,c; main(){ scanf("%ld%ld%ld",&a,&b,&c); print…

yukicoder No.544 Delete 7

問題はこちら No.544 Delete 7 - yukicoderCで文字列処理をするのはつらいので数値として扱う。 下の位から順に見ていって、7であるようなところは6と1に分解する。それ以外はそのまま。 例えば72727なら62626+10101にする int s,n,i; main(){ scanf("%d",&n…

yukicoder No.543 命題

問題はこちら No.543 命題 - yukicoder問題文をよく読むと、入力「a b」に対しては「b a」を出力すれば良いことがわかる main(){ char a,b; scanf("%c %c",&a,&b); printf("%c %c",b,a); } 1行まるごとひっくり返せばよい 頭から読んでお尻から出力→main再帰…

yukicoder No.542 1円玉と5円玉

問題はこちら No.542 1円玉と5円玉 - yukicoder5*b+4円以下の範囲については1円玉を5枚以上使うことなく作れるので、その範囲については2重ループ それ以上は5円玉を全て使った上で1円玉で調整する main(){ int a,b; scanf("%d%d",&a,&b); for(int i=0;i<=…

yukicoder No.536 人工知能

問題はこちら No.536 人工知能 - yukicoder後ろ2文字が"ai"かどうかで分ける char s[99]; int n; main(){ gets(s); n=strlen(s); if(s[n-2]=='a'&&s[n-1]=='i'){ s[n-2]='A'; s[n-1]='I'; }else{ s[n]='-'; s[n+1]='A'; s[n+2]='I'; } puts(s); } で、この方…

yukicoder No.532 Possible or Impossible

問題はこちら No.532 Possible or Impossible - yukicoderM+0*(残り) の形が作れれば十分 ●M≧4のとき M+(3-2-1)*(残り) ●M=3のとき ・N=3のとき:3*(2-1) ・N=4のとき:4+2-1*3 ・N≧5のとき:3+(5-4-1)*(残り) ●M=2のとき ・N=2のとき:2*1 ・N=3のとき:3-2…

yukicoder No.531 エヌスクミ島の平和協定

問題はこちら No.531 エヌスクミ島の平和協定 - yukicoderm≧nなら全員で船に乗れば1日で移動できる。そうでないとする。 1回目の移動で船に乗るグループと乗らないグループに分けると、これはどちらも非空集合なので、動物1が船に乗り、動物2が船に乗らない…

yukicoder No.530 年齢って毎年変わるし覚えるの難しいよね

問題はこちら No.530 年齢って毎年変わるし覚えるの難しいよね - yukicoder日付を気にしなくていいので、簡単 y; main(){ scanf("%d",&y); printf("%d",2017-y); } ぎゅ n;main(){printf("%d",2017-atoi(gets(&n)));} 43B

yukicoder No.527 ナップサック容量問題

問題はこちら No.527 ナップサック容量問題 - yukicoderまずは普通に01ナップサック問題を解く必要があるが、そのときのDPのやりかたとして2通り考えられる。1つ目は、問題文の表にあるように、d[i]に「重さi以内で得られる価値の最大値」を保存する方法 #d…

yukicoder No.526 フィボナッチ数列の第N項をMで割った余りを求める

問題はこちら No.526 フィボナッチ数列の第N項をMで割った余りを求める - yukicoder普段より丁寧めに解説。 一般的なフィボナッチ数列とはindexが1つずれていることに注意 ・漸化式に従って再帰的に計算する 詳細は省くがO(φ^N)となりTLE fib(n,m){ if(n==1)…

yukicoder No.525 二度寝の季節

問題はこちら No.525 二度寝の季節 - yukicoder入出力に少し気をつける必要があるが、それ以外は前見た問題とほぼ同じ yukicoder No.296 n度寝 - メモ main(x,y){scanf("%d:%d",&x,&y);printf("%02d:%02d",(x+y/60)%24,(y+=5)%60);} 74B

yukicoder No.524 コインゲーム

問題はこちら No.524 コインゲーム - yukicoderNimなので問題は「1~Nまでxorをとったものが0か否か判定せよ」と読み替えられる。(このことの証明は以前した:yukicoder No.2 素因数ゲーム - メモ) 以下では「1~Nまでのxorをとったもの」をxor和と呼ぶこ…

yukicoder No.523 LED

問題はこちら No.523 LED - yukicoder1~Nを2個ずつ並べる重複順列なので(2N)!/2^N mod Pでの階乗やべき乗、逆元を計算する関数を持っているならこれをそのまま投げても良いでしょう #define ll long long ll pom(ll a,ll n,int m){ll x=1;for(a%=m;n;n/=2)n…