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

問題はこちら No.338 アンケート機能 - yukicoder以下では「四捨五入」「切り捨て」などはすべて「小数点以下～」のことを表す200人いれば必ず達成できる なぜなら、A+Bが100のときはそれぞれ2A人,2B人いればOK A+Bが101のときはそれぞれ(2A-1)人、(2B-1)人…

問題はこちら No.337 P versus NP - yukicoderタイトルとは裏腹に真の★1 解説は不要でしょう int main(){ int n,p; scanf("%d%d",&n,&p); puts(p==n*p?"=":"!="); return 0; } n;main(p){n=scanf("%d%d",&n,&p)>puts("!="+(p==n*p));} n;main(p){n=scanf("%d…

問題はこちら No.333 門松列を数え上げ - yukicoder場合分け (i)A<Bのとき 真ん中が最長になるしか無いので、CはBより小さく、かつ、Aとは等しくない数になる 1～B-1のうちAを除くので、結局(B-2)通り (ii)A>Bのとき 真ん中が最短になるしか無いので、CはBより大きく、かつ、Aとは等しくない数になる B+1～2*10^9のうちAを除くので、結局(2*10^9-B-1)通り int main(){ int a,b; scanf("%d%d",&a,&b);</bのとき>…

問題はこちら No.328 きれいな連立方程式 - yukicodera[n]=p*α^n+q*β^n とみればそれはもう三項間漸化式でしょう （一般項がこの形で与えられることとa[n]=s*a[n-1]+t*a[n-2]という形の線形三項間漸化式を満たすことは同値。証明は高校数学の通り「漸化式⇒一…

問題はこちら No.327 アルファベット列 - yukicoder求める文字列をf(N)とする。 一番下の文字がN mod 26できまることは明らか。2桁目以降を考えると N floor(N/26) 2桁目以降 0～25 0 (なし) 26～26*2-1 1 A 26*2～26*3-1 2 B … … … 26*26～26*27-1 26 Z 26*…

問題はこちら No.321 (P,Q)-サンタと街の子供たち - yukicoder P,Qが共に0なら自明。そうでないとする「(a,b)に移動dできるための必要十分条件は、『a,bがd:=GCD(P,Q)の倍数』かつ『【P/d,Q/dの少なくとも一方が偶数】または【a/d+b/dが偶数】』」実験すれば…

問題はこちら No.320 眠れない夜に - yukicoder正しいフィボナッチ数列をとする（indexはとなるよう取る） に対してはとおく（漸化式に従って添字を負に拡張した定義とは異なることに注意）厳密に証明しようとすると死ぬほどめんどくさいので答えだけ先に行…

問題はこちら No.316 もっと刺激的なFizzBuzzをください - yukicoder1以上N以下の整数であって、a,b,cの倍数であるものからなる集合をそれぞれA,B,Cとおくとき #(A∪B∪C)を求めるのが今回の問題 包除原理から（あるいはベン図をぐっと睨んで） #(A∪B∪C)=#A+#B…