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

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

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

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

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

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

問題はこちら 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; } 最初の値を読み飛ばすことと、最後の値を引くことに気をつけて縮め…

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

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

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

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

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

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

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

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

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

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

問題はこちら 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は積分定数、対数…

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

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

問題はこちら No.344 ある無理数の累乗 - yukicoderDashboard - Round 1A 2008 - Google Code Jamの類題 この問題は、自分がまだプログラミングを知らなかった頃に見つけて、自力で数学的な答えにたどり着いた思い出深い問題。α=1+√3、β=1-√3とし、a[n]:=α^n…

問題はこちら No.341 沈黙の期間 - yukicoderまず「……」とだけ書いたテキストをUTF-8で保存してバイナリエディタで開くと 00000000: EF BB BF E2 80 A6 E2 80 A6 となった。多分「E2 80 A6」が「…」なんだろうけどじゃあ「EF BB BF」ってなんだよとググった…

問題はこちら No.339 何人が回答したのか - yukicoderM人が回答し、選択肢iを選んだ人数をm[i]人とする。 m[i]たちの公約数が2以上なら、全体をそれで割ることでMを小さくできるので、m[i]たちは互いに素（setwise coprime）であるとしてよい。 m[i]/M*100=A…