読者です 読者をやめる 読者になる 読者になる

メモ

yukicoderで遊んでいる競プロゆるふわ勢

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がリスト…

yukicoder No.376 立方体のN等分 (2)

問題はこちら No.376 立方体のN等分 (2) - yukicoder基本的な考え方はyukicoder No.375 立方体のN等分 (1) - メモに同じ ただし、制約が大きいのであんな愚直な全探索では通らない 約数を求めてその組み合わせを試して~~としても良いが、先に思いついたの…

yukicoder No.375 立方体のN等分 (1)

問題はこちら No.375 立方体のN等分 (1) - yukicoder1回切るとブロックの数は1以上増えるので、N-1回切ればN個以上になる。実際、同じ方向に切り続ければN-1回でN個にすることができるので、最大値はN-1。 最小値を考える。 縦・横・高さ方向に各a,b,c回切っ…

yukicoder No.374 コイン

問題はこちら No.374 コイン - yukicodera<bなら初手が置けないので後手の勝ち そうでない時、先手は初手を中心に置き、以降は後手が置いた位置の点対称な位置に置いていけば必ず勝てる つまりa<bか否かだけで決まる int main(){ long a,b; scanf("%ld%ld",&a,&b) puts(a<b?"K":"S"); return 0; } 縮める long a,b;main(){a=scanf("%ld%ld",&a,&b)>puts(a</bなら初手が置けないので後手の勝ち>

yukicoder No.373 かけ算と割った余り

問題はこちら No.373 かけ算と割った余り - yukicoderやるだけ……と思わせて罠がある 「a*b*c%d」とやると、a*b*cが最大で10^27になるので64bitですら収まらない 2数の積なら10^18で64bitに収まるので、そこで一旦dでの剰余を取る int main(){ long a,b,c,d; …

yukicoder No.139 交差点

問題はこちら No.139 交差点 - yukicoderスタートしてからの経過時間をsとおく 交差点の信号は周期2*T[i]なので、s%(2*T[i])で場合分けすれば良さそう 信号を最後まで渡り切るためには時刻0~(T[i]-W[i])の間に渡り始めることは必要十分 さもなくば次の青信…

yukicoder No.365 ジェンガソート

問題はこちら No.365 ジェンガソート - yukicoder後ろから見て、大きい方から順にN~i+1までは順番に並んでいて、iはそうでないとする。 このとき、iをi+1より左に動かすために最低1回の操作が必要 更にこの直後、1~i-1はiより右にあるので、これらをiより…

yukicoder No.152 貯金箱の消失

問題はこちら No.152 貯金箱の消失 - yukicoder3数の和がL/4以下であるような原始ピタゴラス数を探す問題 ピタゴラスの定理 - Wikipediaなどに書かれている式によれば、原始ピタゴラス数は、互いに素で偶奇が異なる正整数n<mの組と(2mn, m^2−n^2, m^2+n^2)…

yukicoder No.232 めぐるはめぐる (2)

問題はこちら No.232 めぐるはめぐる (2) - yukicoder右方向を第一軸(x軸)、上方向を第ニ軸(y軸)とする座標で表す 目的地の座標は(B,A)である(逆になっていることに注意(1WA)) まずYES,NOを判別する (x,y)にt回"以下"の移動で辿りつけない⇔t<x or t<y …

yukicoder No.250 atetubouのzetubou

問題はこちら No.250 atetubouのzetubou - yukicoder互いに区別されるD個の箱に、ちょうどX個の玉をいれる場合の数に等しい これは重複組合せで求める事ができ となる ところで最後の式の後ろからi項の部分積はもちろんなので整数であることから、整数の範囲…

yukicoder No.360 増加門松列

問題はこちら No.360 増加門松列 - yukicoderCにはnext_permutationはないので場合分けして考察 7箇所の位置を順にa~gとすると、各門松が(左端<右端)であるという条件から a

yukicoder No.103 素因数ゲーム リターンズ

問題はこちら No.103 素因数ゲーム リターンズ - yukicoderこのゲームが本質的には山崩し(Nim)と同じであることはyukicoder No.2 素因数ゲーム - メモで説明した 前回との違いは、割れる回数が2回までになっていることのみ よって(N言っちゃだめゲームと同…

yukicoder No.371 ぼく悪いプライムじゃないよ

問題はこちら No.371 ぼく悪いプライムじゃないよ - yukicoderL~Hのすべての数の最小素因数を求めているとTLE そこで、「pを最小素因数とする合成数がL~Hの中にあるか」を調べていく 合成数Nの最小素因数がpならp*p≦Nなので、そのような素数pの候補は√H=10…

yukicoder No.370 道路の掃除

問題はこちら No.370 道路の掃除 - yukicoderゴミの位置をソートしておく ゴミは連続したM個を拾うのが最短。 なぜなら両端にあるゴミを拾うために、その間にあるゴミの前を必ず通過するからである。 ということで左からi番目~i+M-1番目のゴミを拾うと考え…

yukicoder No.369 足し間違い

問題はこちら No.369 足し間違い - yukicoder足して引く int main(){ int s=0,n,v; scanf("%d",&n); while(n--){ scanf("%d",&v); s+=v; } scanf("%d",&v); printf("%d",s-v); return 0; } 最初の値を読み飛ばすことと、最後の値を引くことに気をつけて縮め…

yukicoder No.368 LCM of K-products

問題はこちら No.368 LCM of K-products - yukicoderまずLCMについて考える 一般に、と素因数分解される数に対して となる ここでであることから求めるべきは となる。ただしmaxは#I=KとなるようなI全体を動く は明らかに「の大きい方からK個の和」となるの…

yukicoder No.358 も~っと!門松列

問題はこちら No.358 も~っと!門松列 - yukicoderp>max(A[i])に対して、A[i]はmod pで不変なので、A[i]が元から門松列なら無限個、そうでないならA[i] mod pが門松列になるようなものはp≦max(A[i])の時に限り、特に有限個となる。 max(A[i])≦1000なので、…

yukicoder No.357 品物の並び替え (Middle)

問題はこちら No.357 品物の並び替え (Middle) - yukicoderyukicoder No.90 品物の並び替え - メモ これと全く同じなのでそちらを参考のこと d['~~'],s[14][14],i,j,u,x=16384; main(v){ for(gets(&v);~scanf("%d%d%d",&i,&j,&u)?s[i][j]=u:x&!!j--<

yukicoder No.356 円周上を回る3つの動点の一致

問題はこちら No.356 円周上を回る3つの動点の一致 - yukicoderyukicoder No.229 線分上を往復する3つの動点の一致 - メモ これの類題。というかむしろこれより簡単なのでコピペして適当に書き換えればOK long gcd(long p,long q){return q?gcd(q,p%q):p;} i…

yukicoder No.354 メルセンヌ素数

問題はこちら No.354 メルセンヌ素数 - yukicoder2進数表記の意味がわかっていれば自明 int main(){ int p; scanf("%d",&p); printf("%d",p); return 0; } 文字列として読み込む a;main(){a=!puts(gets(&a));} 28B

yukicoder No.353 ヘイトプラス

問題はこちら No.353 ヘイトプラス - yukicoderA-(-B)するだけだと気づくのに20分以上かかりましてですね…… int main(){ int a,b; scanf("%d%d",&a,&b); printf("%d",a-(-b)); return 0; } ぎゅ a; main(b){ scanf("%d%d",&a,&b); a=!printf("%d",a- -b); } …

yukicoder No.352 カード並べ

問題はこちら No.352 カード並べ - yukicoder期待値の線形性から、kのカードを置くときのコストの期待値Xkをそれぞれ求め、それらを合計すれば良い k=1,2のとき1となるのはあきらか k≧3のカードを並べるとき、i,j<kのカードが隣り合っている確率は2*(k-2)!/…

yukicoder No.351 市松スライドパズル

問題はこちら No.351 市松スライドパズル - yukicoder盤面が大きいので、盤面全体を愚直にシミュレーションするとTLEする。 ということで、逆シミュレーションする。 つまり、「最後に(x,y)にいるタイルは、最初にどこにいたか」を調べる ある時点で(x,y)に…

yukicoder No.350 d=vt

問題はこちら No.350 d=vt - yukicoder int main(){ int t; double v; scanf("%lf%d",&v,&t); t=t*v; //int型に代入して切り捨て printf("%d",t); return 0; } とやると誤差で死ぬので、vを10000倍して整数とする int main(){ int t,v; scanf("0.%d%d",&v,&t…

yukicoder No.349 干支の置き物

問題はこちら No.349 干支の置き物 - yukicoderだいたい「過半数を占めるようなやつがあると無理」っぽい感じ Nが偶数なら確かにそうだが、奇数の時は例えば●○●○●と並べることで(N+1)/2まではセーフ ここでNが偶数の時floor((N+1)/2)=N/2となることから floo…

yukicoder No.347 微分と積分

問題はこちら No.347 微分と積分 - yukicoder微分と積分の計算の仕方さえ知っていればただの計算問題 一般に、実定数rに対して x^rをxで微分するとr*x^(r-1) xで積分すると、rが-1でないときx^(r+1)/(r+1)+C、rが-1のときlog(x)+Cとなる (Cは積分定数、対数…

yukicoder No.346 チワワ数え上げ問題

問題はこちら No.346 チワワ数え上げ問題 - yukicoder前の問題と微妙にチワワ列の定義が違う 今回求めるものは「'c'ごとにそれより後ろにある'w'を2つ選ぶ場合の数を求め、その合計」となる。 ただしSのサイズが大きいので「前から見ていって、'c'を見つける…

yukicoder No.345 最小チワワ問題

問題はこちら No.345 最小チワワ問題 - yukicodercを見つける毎にその後ろにwを2つ探して、その長さを調べていけば良い int main(){ int i,j,m=1000,t; //存在すれば最小値は必ず100以下 char s[110]; gets(s); for(i=0;s[i];i++){ if(s[i]!='c')continue; /…