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

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

問題はこちら 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;){>

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

問題はこちら 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

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

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

問題はこちら No.376 立方体のN等分 (2) - yukicoder※他の方の解説とは違い、因数分解を用いない回答です基本的な考え方はyukicoder No.375 立方体のN等分 (1) - メモに同じ ただし、制約が大きいのであんな愚直な全探索では通らない 約数を求めてその組み合…

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

問題はこちら 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なら初手が置けないので後手の勝ち>

問題はこちら 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; …

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

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

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

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