メモ

yukicoderでゆるふわgolf

yukicoder No.441 和か積

問題はこちら No.441 和か積 - yukicoder場合分けをすれば簡単に分かる。 必要ならAとBを入れ替えることでA≦Bと仮定して良い ・Aが0のとき Bも0なら'E'、さもなくば'S' ・Aが1のとき 必ず'S' ・Aが2のとき Bも2なら'E'、さもなくば'P' ・Aが3以上のとき 必ず…

yukicoder No.437 cwwゲーム

No.437 cwwゲーム - yukicoderdfsするだけ Nの桁数は高々13なので、適当にやってもどうにかなる #define max(p,q)p<q?p=q:0 char s[99]; //今まで使った数を引数とし、残りの数で作れる最大の値を返す関数 int f(used){ int i,j,k,t,m=0; for(i=0;s[i];i++)for(j=i+1;s[j];j++)for(k=j+1;s[k];k++){ if(used>>i&1||used>>j&1||used>>k&1||s[i]=='0'||s[i]==s[j]||s[j]!=s[k])continue; //…</q?p=q:0>

yukicoder No.436 ccw

問題はこちら No.436 ccw - yukicoderやるだけ cが2個以上かつwが1個以上あることがccwが存在するための必要十分条件なので、cを1個以下にするかwをすべて消すか。 つまり「cの個数-1」「wの個数」のminが答え #define min(p,q)(p

yukicoder No.78 クジ付きアイスバー

問題はこちら No.78 クジ付きアイスバー - yukicoder制約が大きいので愚直にシミュレーションすると通らない……はずなのだけど、Cは速いからギリギリ通っちゃうんだなこれが char box[60]; int n,k,cost,stock,p; int main(){ scanf("%d%d%s",&n,&k,box); whi…

yukicoder No.181 A↑↑N mod M

問題はこちら No.181 A↑↑N mod M - yukicoderよく考えればそんなに難しくなくない…?と最初は思ったけれど、考えれば考えるほど泥沼になるタイプの問題だったm=1のとき、及び、n≦2のときは明らか。そうでないとする。 a↑↑nを返す関数をtetra(a,n)、a↑↑n mod …

yukicoder No.291 黒い文字列

問題はこちら No.291 黒い文字列 - yukicoderDPの状態遷移を考えるのに2時間くらいかかってしまった……dp[i][a][b][c][d]=(i文字目まで見て、Kがa個、内KUがb個、内KURがc個、内KUROがd個あるときのKUROIの内数) として配るDPを考える K,U,R,O,Iの各文字がき…

yukicoder No.372 It's automatic

問題はこちら No.372 It's automatic - yukicoderdp[i][j]を「i文字目までを使って作れる数の内、mod Mでjであり、先頭が0(0のみを含む)でなく、空文字列でもないものの個数」として配るDPを考える (i+1)文字目の数をcとすると、dp[i+1]は次のように作られる…

yukicoder No.432 占い(Easy)

問題はこちら No.432 占い(Easy) - yukicoder問題文のとおりに操作をすれば良い char s[1010]; int main(){ int i; gets(s); for(;gets(s);){ while(strlen(s)>1){ for(i=0;i<strlen(s)-1;i++){ s[i]+=s[i+1]-'0'; if(s[i]>'9')s[i]-=9; } s[i]='\0'; } puts(s); } return 0; } まず何の工夫もなく縮めて c</strlen(s)-1;i++){>…

yukicoder No.435 占い(Extra)

問題はこちら No.435 占い(Extra) - yukicoderyukicoder No.434 占い - メモと全く同じ x,a,b,m,n,i,t,ans,c,c3; inv9[]={0,1,5,0,7,2,0,4,8}; f3(n){int i=0;for(;n&&n%3==0;n/=3)i++;return i;} g3(n){for(;n&&n%3==0;n/=3);return n;} main(){ for(gets(&…

yukicoder No.434 占い

問題はこちら No.434 占い - yukicoder い 手順3の「できた数が2桁なら十の位と一の位を足す」という操作は9での剰余を求めることとほぼ等しいことに注意すれば、途中で行われる操作が加算のみであることから、これは最後にまとめてすれば良い。 よって(Σs[i…

yukicoder No.431 死亡フラグ

問題はこちら No.431 死亡フラグ - yukicoderやるだけ 生存するのは、死亡フラグの合計が2未満or生存フラグが1 int main(){ int a,b,c,d; scanf("%d%d%d%d",&a,&b,&c,&d); puts(a+b+c<2|d?"SURVIVED":"DEAD"); return 0; } 少し読み替えて、フラグの合計が2…

yukicoder No.425 ジャンケンの必勝法

問題はこちら No.425 ジャンケンの必勝法 - yukicoder1回目: 勝ち→1/3 負け→1/3 あいこ→1/3なので「前回があいこで、今回必勝法を使う確率がpのときに勝つ確率」をf(p)とすると、求めるべきは当然 1/3+1/3*f(p) となる。前回があいこで、今回必勝法を使う確…

yukicoder No.420 mod2漸化式

問題はこちら No.420 mod2漸化式 - yukicoder/2と%2が並んでいるところを見るといかにも2進法っぽい。 ということで、2進法化した数をfに放り込んだところを想像すると、結局fはbitpop数を数える関数であることが分かる ・個数 0bit目から30bit目までのどのb…

yukicoder No.428 小数から逃げる夢

問題はこちら No.428 小数から逃げる夢 - yukicoderCではたとえ整数でも190桁の数をそのまま扱うことはできないので工夫が必要 幸いNが小さいので、多倍長の乗算のためのなにがしかを持ち出さなくても1桁ごとに筆算していけば良い int main(){ char ans[999…

yukicoder No.427 テレビ

問題はこちら No.427 テレビ - yukicoder H:Wは3:4か4:3なので、大小関係をチェックするだけでよい x;main(y){x=scanf("%d%d",&x,&y)>puts(x

yukicoder No.423 ハムスター語初級(数詞)

問題はこちら No.423 ハムスター語初級(数詞) - yukicoder入力の末尾に"ham"をつけるだけ……ではない 入力が0のとき、かつその時に限り、入力をそのまま出力することになる char s[99]; main(){ gets(s); printf(strcmp(s,"ham")?"%sham":"%s",s); return 0…

yukicoder No.406 鴨等間隔の法則

問題はこちら No.406 鴨等間隔の法則 - yukicoder定義どおりやるだけ ソートして、その間隔が一定かつ0でないことを確かめれば良い c(int*a,int*b){return *a-*b;} int main(){ int x,a[1<<17],s,i,n,f; scanf("%d",&n); for(i=0;i

yukicoder No.415 ぴょん

問題はこちら No.415 ぴょん - yukicoderindexを1ずらして0-basedとする 一度スタートすると同じ方向に進み続けるしかないのでi回目の移動先はi*D%N よって求めるべきはi*D%Nが0となる最小の非負整数iから1引いたもの(実際に移動できる回数なので) 即ちi*D…

yukicoder No.414 衝動

問題はこちら No.414 衝動 - yukicoder素数判定するだけ Mが2や3のときも気にしなくて良い int main(){ long m,i; scanf("%ld",&m); for(i=2;i*i<=m;i++)if(m%i==0)break; if(m%i==0)printf("%ld %ld",m/i,i); else printf("%ld 1",m); return 0; } 出力をい…

yukicoder No.405 ローマ数字の腕時計

問題はこちら No.405 ローマ数字の腕時計 - yukicoder 負の数の剰余にだけ注意すれば良い char a[][5]={"I","II","III","IIII","V","VI","VII","VIII","IX","X","XI","XII"},b[]; i; main(x){ for(scanf("%s%d",b,&x);strcmp(b,a[i++]);); i=!puts(a[(x+i+11…

yukicoder No.419 直角三角形

問題はこちら No.419 直角三角形 - yukicoder必要ならaとbを入れ替えることでa≦bとする 当然、斜辺は他の2辺より長いことに注意する a≠bのとき、bを斜辺とすることで最後の一辺は√(b*b-a*a)となる a=bのとき、a,bを斜辺にすることは出来ないので、最後の一…

yukicoder No.418 ミンミンゼミ

問題はこちら No.418 ミンミンゼミ - yukicoderSはミーン文字列の結合であり、ミーン文字列には'n'がちょうど1つ含まれることから、nの個数を数えれば良い int main(){ char c[110]; int i,s=0; gets(c); for(i=0;c[i];i++)if(c[i]=='n')s++; printf("%d",s)…

yukicoder No.410 出会い

問題はこちら No.410 出会い - yukicoderマンハッタン距離÷2するだけ a,b,c; main(d){a=scanf("%d%d%d%d",&a,&b,&c,&d)>printf("%f",(abs(a-c)+abs(b-d))/2.);} 83B

yukicoder No.61 リベリオン

問題はこちら No.61 リベリオン - yukicoder格子点を「通過」する判定はめんどくさいので、弾の速度をgcd(Vx,Vy)で割り、制限時間をその分伸ばすことにする 反射を考えるのは面倒なので、x軸y軸の各方向を2倍にしてループしていると考えるいつものやつ 格子…

yukicoder No.411 昇順昇順ソート

問題はこちら No.411 昇順昇順ソート - yukicoderが昇順昇順列である 定義よりはそれぞれ昇順列であることに注意せよ1~Nの置換である昇順昇順列のうち、であるものの個数を求めよ、という問題である条件をみたすような昇順昇順列をとる を満たすjをとり、と…

yukicoder No.402 最も海から遠い場所

問題はこちら No.402 最も海から遠い場所 - yukicoder初見では解説の「無駄解法」と同じことしか思いつけなかったので、解説を見て回答陸の部分からなる最大の正方形を見つける問題と同値になる #define max(p,q)(p>q?p:q) #define min(p,q,r)(p

yukicoder No.403 2^2^2

問題はこちら No.403 2^2^2 - yukicoderフェルマーの小定理を使ってpowmodするだけ ……と見せかけて、「AがPの倍数かつBがP-1の倍数」に気をつける必要がある (剰余をとってから累乗を計算すると0^0となるが、0を返すのか1を返すのか)先日ライブラリ化したp…

yukicoder No.401 数字の渦巻き

問題はこちら No.401 数字の渦巻き - yukicoder えっと、2次元配列を作って、その上を指定の順番に移動していって…… ええい面倒くさい。(x,y)の位置にある数を一発で求めればそんな面倒な事をしなくて済むぞ 例えばn=6のとき下図のようになる(x,yの座標は0-…

yukicoder No.400 鏡

問題はこちら No.400 鏡 - yukicoder後ろから順に左右を逆にして出力 int main(){ char s[99]; int n,i; gets(s); n=strlen(s); for(i=n;i--;)putchar(s[i]=='<'?'>':'<'); return 0; } '>'と' char s[];i;main(){for(i=strlen(gets(s));i--;putchar(s[i]^2)…

yukicoder No.398 ハーフパイプ(2)

問題はこちら No.398 ハーフパイプ(2) - yukicoder2通りの解がある ・DP解 dp[人数][最低点][最高点][合計点]でDPしてΣ{dp[6][m][M][s]|s=X*4+m+M}を求める #define min(a,b)(a<b?a:b) #define max(a,b)(a>b?a:b) long d[7][101][101][601],a; i,m,M,s,k; int main(){ R(m,0)d[1][m][m][</b?a:b)>…

yukicoder No.391 CODING WAR

問題はこちら No.391 CODING WAR - yukicoder包除原理で殴るだけ i(≦M)問以下にしか割り当てられないようなパターンは i問の選び方が、割り当て方がi^Nある。 よって求めるべきは (もちろんシグマはi=0からでも構わない)コンビネーションは、前から何度も…

yukicoder No.390 最長の数列

問題はこちら No.390 最長の数列 - yukicoderコンテスト中にはO(N^2)解しか思いつかずに撃沈。解説を見た (以下maxφ=0とする) ・O(N^2)解 xiが小さい方から順に、dp[i]=1+max{dp[j]|xjはxiの約数}としてmax{dp[i]}が答え 配るDPに書き換えて、iが小さい方…

yukicoder No.397 NO MORE KADOMATSU

問題はこちら No.397 NO MORE KADOMATSU - yukicoderソートするだけ int main(){ int n,i,j,s,a[110],b[5000]={}; for(scanf("%d",&n);i<n;i++)scanf("%d",a+i); for(i=0;i<n;i++)for(j=1;j<n;j++)if(a[j-1]>a[j]){ b[s++]=j; a[j]^=a[j-1]^=a[j]^=a[j-1]; } printf("%d\n",s); for(i=0;i</n;i++)scanf("%d",a+i);>

yukicoder No.396 クラス替え

問題はこちら No.396 クラス替え - yukicoder折り返しまで込めて周期は2M 以下、手順2を「行き」、手順3を「帰り」と呼ぶことにする。 ・2人が共に「行き」または共に「帰り」で同じクラスに割り振られることと X≡Y mod 2M は同値 ・1回目の「行き」と1回目…

yukicoder No.395 永遠の17歳

問題はこちら No.395 永遠の17歳 - yukicodern進法で17と表される数はn+7。 7が使われているので基数は8以上。 このことからAが14以下なら-1を出力、15以上ならn-7のみが解になることが分かる。 n;main(){n=scanf("%d",&n)>printf("%d",n>14?n-7:-1);} 52B

yukicoder No.394 ハーフパイプ(1)

問題はこちら No.394 ハーフパイプ(1) - yukicoderソートして真ん中4個の平均 int c(int*a,int*b){return*a-*b;} int main(){ int a[1000],i; for(i=0;i<6;i++)scanf("%d",a+i); qsort(a,6,4,c); printf("%.2f",(a[1]+a[2]+a[3]+a[4])/4.); return 0; } ソー…

yukicoder No.392 2分木をたどれ

問題はこちら No.392 2分木をたどれ - yukicodern+1に対してyukicoder No.104 国道 - メモの逆をするだけ 具体的には、n+1を2進数表示して最上位の1を落とした物を、1→R、0→Lと変換したものを出力する出力を逆にするのは再帰と相性が良い i; f(n){n&&f(~-n/2…

yukicoder No.389 ロジックパズルの組み合わせ

問題はこちら No.389 ロジックパズルの組み合わせ - yukicoderヒントが0のみだった場合は1通り。これだけ例外処理 k-1+ΣHi>MのときNAになるのは明らか。 そうでないとき、必要な分(=黒マスとその間の白1マス)だけ先に並べると、残った(M-(k-1+ΣHi))個の白…

yukicoder No.388 階段 (1)

問題はこちら No.388 階段 (1) - yukicoderやるだけ だいたいN/Kっぽい何かをすればいい。 切り捨てなのか切り上げなのか、1足したり引いたりしなくていいのか、といったことはサンプルを見れば分かる n; main(k){ scanf("%d%d",&n,&k); n=!printf("%d",n/k+…

yukicoder No.385 カップ麺生活

問題はこちら No.385 カップ麺生活 - yukicoderまずは「ちょうどk円で買えるカップ麺の最大個数」を求める。 これは要するに「Ci円玉でちょうどk円払う時、最大で何枚の硬貨が使えるか」なので、DPでできる。 (c.f.yukicoder No.247 線形計画問題もどき - …

yukicoder No.384 マス埋めゲーム2

問題はこちら No.384 マス埋めゲーム2 - yukicoderyukicoder No.166 マス埋めゲーム - メモよりも少し頭を使う。 全てのマスが埋まった⇔「全ての列が選択された」または「全ての行が選択された」 となる また、「選択されていない列の数+選択されていない行…

yukicoder No.383 レーティング

問題はこちら No.383 レーティング - yukicoderやるだけ int main(){ int n,k; scanf("%d%d",&n,&k); if(k-n>0)printf("+"); printf("%d",k-n); return 0; } ところでprintfには %+d という便利なフォーマットがあって、値が正の時には頭に+を付けてくれる。…

yukicoder No.366 ロボットソート

問題はこちら No.366 ロボットソート - yukicoder幅kのバブルソートをする 普通のバブルソートで for(i=0;i<n;i++)for(j=0;j+1<n;j++)if(x[j]>x[j+1])swap(x[j],x[j+1]); とするところを for(i=0;i<n;i++)for(j=0;j+k<n;j++)if(x[j]>x[j+k])swap(x[j],x[j+k]); とすればよい (あとで縮める都合上、普通のバブルソートより定数倍</n;i++)for(j=0;j+k<n;j++)if(x[j]></n;i++)for(j=0;j+1<n;j++)if(x[j]>…

yukicoder No.190 Dry Wet Moist

問題はこちら No.190 Dry Wet Moist - yukicoder全体をソートしておく まずDry(和が負になるペア)を探すことを考える。 負の数は、絶対値が大きな方から貪欲に使うとして良い(和を負にしたいので、絶対値が大きな負の数を使わない理由はない) 負の数を1つ…

yukicoder No.325 マンハッタン距離2

問題はこちら No.325 マンハッタン距離2 - yukicoderショートコード以前に、普通に通すだけでめちゃくちゃ難しかった。与えられた長方形をに属する格子点を、各象限ごとに求めて合計するという方針で考えた。このとき、軸上の点を重複カウントしないように、…

yukicoder No.334 門松ゲーム

問題はこちら No.334 門松ゲーム - yukicoderDFSするだけ メモ化して高速化しないとだめかと思ったけど、しなくても大丈夫らしい int a[20],I,J,K,n; int f(int x){ //すでに使った竹の情報をbitで保存したものを引数とする int i,j,k; for(i=0;i<n;i++)for(j=i;++j<n;)for(k=j;++k<n;){ //3本の竹を選ぶ if(~x&1<<i && ~x&1<<j && ~x&1<<k && (a[i]-a[j])*(a[k]-a[j])>0 && !f(x^1<</n;i++)for(j=i;++j<n;)for(k=j;++k<n;){>

yukicoder No.9 モンスターのレベル上げ

問題はこちら No.9 モンスターのレベル上げ - yukicoder各戦闘でこちらが出すのがモンスターは「レベルが最小のもの」→「そのうち戦闘回数が最小のもの」なので、これは「(レベル×(大きな数)+戦闘回数)が最小のもの」と考えることが出来る。 戦闘回数は高…

yukicoder No.379 五円硬貨

問題はこちら No.379 五円硬貨 - yukicoderやるだけ n/5は切り捨てにしないといけないので、doubleに変換するタイミングに注意する n,g;main(v){n=scanf("%d%d%d",&n,&g,&v)>printf("%.12f",n/5*1.*g/v);} 67B 誤差が10^-12なので、%.9fなどとごまかすとWA

yukicoder No.378 名声値を稼ごう

問題はこちら No.378 名声値を稼ごう - yukicoderスキルを使わない場合にk回目のクリアで得られるポイントをa[k]とする。 a[k+1]≦a[k]/2であることから帰納的にa[k]≦N/2^(k-1)とわかる。 よってとなる。 これより帰納的に、1回目にスキルを使うのが最適であ…

yukicoder No.144 エラトステネスのざる

問題はこちら No.144 エラトステネスのざる - yukicoder問題文中で「下線部の処理」とされている部分のことを、以下「消去」と呼ぶ kが素数と判定される確率をf(k)とおくと期待値の線形性からΣf(k)が求める答えとなるのでf(k)を求めることを考える kがリスト…