問題 codeforces.com 解法 問題設定がこの問題に非常に似ています。 mayokoex.hatenablog.comまず大雑把に解法を説明します。dp[i][j] = (i 番目までの数を分割した時, 最後の数は j 桁であるような場合の数) とします。また, dpSum[i][j] = (i 番目までの数…

問題 codeforces.com 解法 長いですが, 大事なことは 「長方形区間から飛び出すタイルは右側か下側にしかないので計算量は O(Q(W+H))」ということだけです。タイルの埋め方は, (y, x) と (y+1, x) を覆うようにタイルを埋める(下方向に埋める)か, (y, x) と …

問題 TopCoder Statistics - Problem Statement 解法 ある状態において, ぷよを全消しにするためにあと必要な最低限のぷよの個数を考えます。 例えば, 今の状態が RRBBR とかだったら, 全消しにするためには, RRBR とすれば良いので, この状態では必要なぷよ…

div2 med のほうが難しい説ある。 問題 TopCoder Statistics - Problem Statement 解法 0, 2, 5, 7 を決めると, それ以外の頂点は 隣り合った要素と別ので Y ならどんな色を使っても OK です。よって, 0, 2, 5, 7 の色について全探索して, 残りの色が何通り…

問題 codeforces.com 解法 c(a) の値について二分探索します。c(a) dp[i] = (i 番目の要素を固定するとして, i 番目以下の数のうち値を変更しなければならない要素の数の最小値) とします。 これがわかると, (dp[i]+(n-i-1)) の最小値が K 以下なら c(a) = 1…

問題 codeforces.com 解法 配列 a の j 番目の数が i 番目のクエリの時点で +k されているとしましょう。この時, j を含む区間 [l, r] において最大値が d になっているというヒントが与えられたとすると, j 番目の数は d-k 以下になっていなければなりませ…

問題 TopCoder Statistics - Problem Statement 解法 二乗した数はたかだか 18 桁で, 各数字は 最大 9 なので, 数字の和は 162 以下です。 なので, 二乗する前の数字の各桁の和は 12 以下でないとダメです。ということで, 桁の和が 12 より大きくなったら枝…

問題 TopCoder Statistics - Problem Statement 解法 各カードについて, あり得る数字がどれだけあるかを列挙することを考えます。 m = colors.size() としましょう。で, ok1[i][j] = (i 番目のカードが j という値をとる可能性があるかを 0 〜 i 番目のカー…

問題 TopCoder Statistics - Problem Statement 解法 区間 dp っぽく解くことが出来ます。まず前処理で, 各頂点間の最短距離を覚えておきましょう。この時, 頂点 0 と cities のどこかの頂点の距離が INF (要するに辿りつけない) だったらその頂点を調べるの…

学校の別のコースの人の授業でやった問題らしいので軽い気持ちでやってみたけど, 全然わからなかった… 問題 最小コストソート | アルゴリズムとデータ構造 | Aizu Online Judge 解法 まず基本的な考察をします。例えば 10 7 8 9 といった数列を考えると, 最…

問題 TopCoder Statistics - Problem Statement 解法 辺の重みの付け方は 2^(n-1) 通りしかないので, 雰囲気としては dp[v][d] = (頂点 v を root とする部分木で, 直径は d 以下である場合の数) とすれば, 直径が d である確率は, (dp[0][d] - dp[0][d-1]) …

SRM 677 に参加しました。easy かなり苦しかったけど通してレートが少し上がりました。最近 easy が解けなくてレート下がってたし, システムテスト通った時めっちゃ興奮しました。やっぱいいですね。 問題 整数の組 (a, b) および (newA, newB) が与えられる…

問題 No.332 数列をプレゼントに - yukicoder 解法 という制約により, 数列 の中に 50000 という数字は 20 個ちょっとしかありません。また, 50000 以下の数であれば, dp[n][sum] = (数列内の n 個の数字を使う際に, 和を sum にすることが出来るか)という d…

問題 No.331 CodeRunnerでやれ - yukicoder 解法 深さ優先探索をする要領で探索すれば良いです。 bool visit[50][50]; const int B = 25; int dir = 0; void dfs(int y, int x) { visit[y+B][x+B] = true; int odir = dir; string s; cin >> s; for (int k =…

問題 codeforces.com 解法 まず少し観察します。 例えば 1 1 4 5 1 4 という数列を考えると, 例えば 1 1 4 5 1 4 -> 4 5 1 4 -> 4 1 4 -> 終わり というようなものが考えられます。これを考えると, 数列の部分数列(連続でなくて良い)の中でいかに上手く回文…

Codeforces Round #336 に参加しました。相変わらず D が解けないおじさん。 問題 codeforces.com 解法 右から r 個の ビーコンを消す時, 残りのビーコンのうち何個のビーコンが破壊されずに残るのかが分かれば, 最高でビーコンがいくつ残るのかがわかります…

問題 No.330 Eigenvalue Decomposition - yukicoder 解法 行列 A の (ak, bk) 成分及び (bk, ak) 成分が 0 のとき, 頂点 ak と bk の間に辺を結ぶ, ということをすると, この問題の答えは, グラフ上の連結成分の個数になります。証明については以下が参考に…

問題 No.329 全射 - yukicoder 解法 集合 から集合 への生きている全射がある条件は, あるパス が存在して, そのパスに含まれる数 a がすべて を満たすことです。これは, 要するにパスに含まれる数字について, の最小値 (これを とする) が 以上であるという…

さっき解いた問題が貯金箱シリーズに似てたのでいけると思った(いけなかった)。貯金箱シリーズ, 上手いこと SRM のバージョンとは差をつけていて, 上手いなぁと思います。 問題 No.137 貯金箱の焦り - yukicoder 解法 「硬貨 A[i] をいくらでも使って良い」…

問題 TopCoder Statistics - Problem Statement 解法 ここに書く解法は, topcoder の解説を参考にして書いてます。 http://apps.topcoder.com/wiki/display/tc/SRM+527 こっちのほうが証明とかいろいろ丁寧です。英語面倒ですがこっち読むほうがオススメです…

あんまり競プロっぽくないけどお祭りみたいなもんだし良いかなと思っていましたが, ちょっとアレな方法で通されてしまったのでマズかったかな… 問題 No.328 きれいな連立方程式 - yukicoder 解法 基本的にはここに書いたとおりです。 http://yukicoder.me/pr…

問題 TopCoder Statistics - Problem Statement 解法 k が小さければ, このゲームは grundy 数を使った Nim にすることが出来ます。 grundy[k][i][j] = (あと k 回動かすことが出来て座標が (i, j) であるような場合の grundy 数) というのを, メモ化再帰で…

問題 TopCoder Statistics - Problem Statement 解法 辞書順最小の matrix を求めたいので, 左上の ? で 0 に出来るならなるべくそこから 0 にしていきたいです。つまり貪欲ですね。rows の (r, c) 成分が ? であったとしましょう。この時, ? を 0 にして良…

SRM 527 の練習会に参加しました。 easy med 解いてドヤ顔したと思ったら easy 間違えててダメでした。 問題 TopCoder Statistics - Problem Statement 解法 頂点数 n の木は, すべての頂点が次数 1 以上 n-1 以下, 次数の合計が 2n-2 という条件を満たせば…

SRM 676 には寝坊したので不参加です。easy 楽勝だったので出ればレート上がったよな… 問題 TopCoder Statistics - Problem Statement 解法 R について二分探索すれば良いです。簡単すぎない？ bool ok(double R, const vi& t, const vi& x, int C) { int n …

問題 No.325 マンハッタン距離2 - yukicoder 解法 落ち着いて場合分けをします。頂点の数え方としては, (第一象限の点の数) + (第二象限の点の数) + (第三象限の点の数) + (第四象限の点の数) - (x 軸の点の数) - (y 軸の点の数) + (原点の点の数) という数…

問題 No.324 落ちてた閉路グラフ - yukicoder 解法 輪になっているのは, とりあえず直線にするのが典型です。去年のこどふぇす本戦の F 問題とかがそうですね。輪を直線にするために, 「最初の頂点を選ぶか, 選ばないか」で場合分けをします。 で, 後は dp[n…

問題 No.323 yuki国 - yukicoder 解法 done[size][y][x] = (雪玉の大きさが size で, 座標が (y, x) にあるような場合があるか) というのを, 幅優先探索すれば良いです。 struct State { int size; int y; int x; State() {} State(int size, int y, int x) …

問題 arc046.contest.atcoder.jp 解法 完全に解説がわかりやすいのでそちらを見ましょう。 AtCoder Regular Contest 046 from AtCoder Inc. www.slideshare.net const ll MOD = 1e9+7; ll fact[1000100]; ll rfact[1000100]; // extgcd ll extgcd(ll a, ll b…

問題 No.322 Geometry Dash - yukicoder 解法 見た目が貪欲法で解けそうなので, 貪欲法で考えてみます。 貪欲法のアルゴリズムを考える際, よく p 番目に (Tp, Dp), q 番目に (Tq, Dq) を配置した際どのようにするとスコアが大きくなるか, ということを考え…