方針 N本のボトルを運ぶときの最小の本数==Nの立っているビットの数 なので、ビットカウントをしてそれがKより少なければ運ぶことができる。これを1本ずつ足していって調べてみればよい。 足す本数は、多く見積もっても2^k ビットカウントにO(logn)掛かると…

問題 整数nが与えられる。 0,1,...,n-1行にそれぞれn-1,n-2,...1個のスペースがあるとし、左詰めで箱を詰める。 ただし、i行目の箱の数a_はa_i>a_j(i 方針 要は下に行くほど少なくなっていけばよい。 n-1行は0個か1個なので dp[0][0] = 1; dp[0][1] = 1; と…

結果 o--(+0/-0) 157.5pts 461st(Div.1)レートは 1221->1256(+35) 何とか年越しを青で迎えることができました。 250 うなぎ切るよ！ 10nな長さのうなぎはn-1回切ると長さ10のうなぎがn本取れるのでお得、なので 長さが10の倍数のものを小さい順に、そうでな…

結果 oo- (+0/-0) 478.37pts 105th(Div.2) 1190->1221(+31)Div1復帰しました。 250 MagicStonesStore ゴールドバッハ予想を使うとちょっと楽になるらしい。 sieveしてから全探索、引数nに対して2*n個というのを初め忘れていて提出が遅れた。Passed System Te…

久々にDPを全部自力で解けた。 問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0232 方針 dp[i][j] := i-thマスに得点jで来る確率 としてDP。 マスに止まる確率のみだと期待値が計算できないので、得点をDPテーブルに 入れるという発想が出…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0230 方針 nが割と小さいのでDFSで間に合う。 これまでの最小値を保持しておいてそれが更新される場合 そこから再帰的に最小値を更新していく。グラフを作って最短経路問題にも落とせる気が…

結果 ooxo- 2576pts, 447th(Div2)レートは 1583->1547(-36) 内容 A,Bはまぁやるだけ C 数列{a_n}のいずれか1つを任意の数に変更して(変更しなければならない) ソートしたときのk番目の値としてとりうる値の最小値を全てのkについて求めよ。基本的には初めに…

[使い方] -単一始点の最短経路とその経路長 -重みが負のedgeがあると使えないvoid dijkstra(int s,vector &cost, vector &prev, vector > edges); s:始点ノードの番号(0-index) cost[i]:sからi-thノードまでの距離を入れるvectorを渡す。 prev[i]:sからの最…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0155 方針 1 すべてのビル間の距離を計算して50以下ならedgeを張ってdijkstraすればよい。前々からdijkstraは書いておきたいなと思いつつも 下手なライブラリ書いて使っていくことにためらい…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0203 方針 配るDP。貰うDPでも書けなくはないと思う。 下から二段目にジャンプ台がある場合に注意。以下ソースコード #include <iostream> #include <cstring> #include <algorithm> using namespace std; int dw[3] = {-1,</algorithm></cstring></iostream>…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0221 方針 シミュレートする。 (Fizz || Buzz || FizzBuzz)でないときの処理を自前tointに任せていると文字列のときにうまくいかないのに気づかず数回WAした。基本的にはやるだけ。以下ソー…