O(NM^2) だと結構厳しめの制約だと思ってだいぶ悩んでいた。 問題 No.417 チューリップバブル - yukicoder 解法 O(NM^2) の木 dp をします。まず考察ですが, 最後に頂点 0 に戻ってこなければならないことから, v -> u と辺を降りた場合, 再び u -> v と戻っ…

問題 No.416 旅行会社 - yukicoder 解法 クエリを逆に読んでデータ構造をマージする一般的なテクを使えば解けます。まず消される辺についてはすべて消されてる状態にします。この際 0 と連結な頂点は答えが -1 です。で, クエリの後ろの辺から辺を追加してい…

この問題実は btk さんから相談をもらっていたんですけど時間内に解けなかった…(主に蟻本を探していた) 問題 No.409 ダイエット - yukicoder 解法 dp[i] = (i 日目に最後にドーナツを食べる際の最小体重)とします。この発想の時点で結構頭良い気がします(こ…

問題 No.408 五輪ピック - yukicoder 解法 「頂点 1 からの距離が 2 の頂点 a, b が辺でつながっていたら, 1 -> c -> a -> b -> d -> 1 みたいな感じでループにならない？」っていうのが基本的な発想です。つまり, 各頂点について「1 からの距離が 2 になり…

問題 No.404 部分門松列 - yukicoder 解法 とりあえず配列 A は座圧しておきます。そうすると, 各 A[i] を真ん中とする門松列の数は, 基本的には (i より左側にある A[i] より小さい値の数) * (i より右側にある A[i] より小さい値の数) (i より左側にある A…

初 HL 分解です。 問題 No.399 動的な領主 - yukicoder 解法 HL 分解を使います。下の記事が HL 分解については詳しいです。 math314.hateblo.jpまた, 以下で書かれていることは pekempey さんの記事でもまとめられています。 pekempey.hatenablog.com下のコ…

問題 No.399 動的な領主 - yukicoder 解法 各頂点を通った回数が数えられれば, その頂点で合計かかった金額は, (cnt+1)*cnt/2 と求められます。よって, 各頂点の通った回数を求めることを目標にします。これは tree 上で imos 法をすると解けます。この発想…

問題 No.398 ハーフパイプ(2) - yukicoder 解法 dp します。dp[i][mini][maxi][sum] = (i 番目までで最小値が mini, 最大値が maxi, 合計が sum になっているような場合の数)とします。この dp は状態が O(6*W*W*6*W) で, 遷移に O(W) かかり, 結構計算量が…

問題 No.393 2本の竹 - yukicoder 解法 想定解とはちょっと違う解法になりました。考察で, 「長さの短い竹をなるべく受け付ける方が良い」というのは変わりません。なので, 配列 A をソートしておけば, 選ばれる竹は, [0, upper) というような区間を選ぶこと…

この問題とは関係ないですが Typing War は楽しいです。 trap.tokyotech.org 問題 No.391 CODING WAR - yukicoder 解法 包除原理で解きます。N 人が M 問のいずれかに担当する場合の数は M^N 通りです。ですが, これだと N 人が M-1 種類以下の問題にしか割…

問題 No.389 ロジックパズルの組み合わせ - yukicoder 解法 sum = H1+H2+...+HK とします。すると, 塗られてないセルの数は M-sum になります。K 個の要素を分割するので, K 個の要素の間に塗られていないセルがいくつか必要です。これで合計 K-1 個の塗られ…

問題 No.387 ハンコ - yukicoder 解法 bitset を使うアレです。各色ごとに考えます。 色 i が現れる位置 pos を覚えておき, memo |= b*2^pos とすれば, memo という配列に「色 i が塗られる場所」が記録されます。これをすべての色について行えば良いです。 …

問題 No.386 貪欲な領主 - yukicoder 解法 よくある問題は, 「木に辺コストが与えられる。頂点 (u, v) が何個も与えられるので, u, v 間の距離を答えろ」みたいのがあります。これは LCA を使うと簡単に求めることができるので, 今回の問題もこれに帰着させ…

問題 No.385 カップ麺生活 - yukicoder 解法 お金が素数になるところは絶対に通る方が得です。そこで, dp[m] = (お金が m になるまでに買えるカップ麺) というのを覚えておくと, m が素数のところでは ans += dp[m] とする dp[m] が最大のところで ans += dp…

問題 No.377 背景パターン - yukicoder 解法 まず蟻本の p269 に書いてある問題を解いてみましょう。これを解いてみれば, 後は似たような話です。蟻本の問題では塗り方は一次元的ですが, 今回の問題では二次元的です。そこで, 「横に w, 縦に h だけずれる場…

問題 No.381 名声値を稼ごう Extra - yukicoder 解法 kmjp さんの解法を参考にしました。 kmjp.hatenablog.jp適当に i = 1, 2, ..., 100 で実験すると, 答えが __builtin_popcount(N) となりそうなことに気付きます。実際, (極端に) N = 2^k とすると, 単純…

問題 No.376 立方体のN等分 (2) - yukicoder 解法 最大のものについては明らかに N-1 が答えです。最小のものが問題ですが, よくわからない方法で解いてしまった感があります。まず N の約数を全列挙します。これをすべて格納した配列を div として, 後は約…

人類なので解くのが難しかった… 問題 No.374 コイン - yukicoder 解法 今回のゲームは離散的じゃないので, 動的計画法的 something は使えそうにないです。問題が解けるらしいことを考えると, (どちらかが必ず勝つための)戦略があるはずです。そこでわかんね…

問題 No.367 ナイトの転身 - yukicoder 解法 2*H*W の頂点を作って適切に辺を貼ってダイクストラすれば良いです。 int knightX[] = {2, 1, -1, -2, -2, -1, 1, 2}; int knightY[] = {1, 2, 2, 1, -1, -2, -2, -1}; int miniX[] = {1, -1, -1, 1}; int miniY[…

問題 No.359 門松行列 - yukicoder 解法 門松列は結局数同士の大小関係で定義されますが, 大小関係が逆転する可能性があるのは, この後並べようとしている竹の高さが既に配置されている竹より大きくなる時か, 小さくなる時だけと考えられます。実はあと x > …

問題 No.362 門松ナンバー - yukicoder 解法 calc(x) = (x 以下の門松ナンバーがいくつあるか) というのがある程度高速に求められたとすると, x に関する二分探索をやれば良いです。ということで, calc 関数が欲しいですが, これは桁dp をやれば良いです。dp…

問題 No.361 門松ゲーム2 - yukicoder 解法 grundy 数やるだけです。 pekempey さんの記事がわかりやすいのでそれを参考にしましょう。今回使ったのは「山が分裂する場合の Grundy 数」です。 pekempey.hatenablog.com const int MAXL = 555; int g[MAXL], D…

問題 No.355 数当てゲーム(2) - yukicoder 解法 いろんな解き方があるような気がしますが, 以下のような解き方で解きました。方針としては, 4 つの数字を確定する 4 つの数字の順列をすべて試す とします。4 つの数字は, 大きい数から順番に特定することにし…

351 が☆2 で 352 が☆3 なのか…(こっちのほうが考えやすかった) 問題 No.352 カード並べ - yukicoder 解法 順番にカードを入れていき, そのたびかかるコストの期待値を求めていきます。 カードが M 枚場に並んでいる場合, 端っこに置く確率は 2/(M+1) で 端以…

☆2 ですが個人的には一番面白いと思ったので書いておきます(解法 1 行で終わっちゃいましたが)。 問題 No.351 市松スライドパズル - yukicoder 解法 最後に左上にあるセルが, 最初にどこにあるか, というのを考えれば良いです。 char s[1000100]; int k[1000…

問題 No.348 カゴメカゴメ - yukicoder 解法 それぞれの輪について, 輪 ch が輪 v に覆われているならば, v -> ch に辺を貼る, ということをやって木グラフを作れば, 木 DP に落とし込める, というのは簡単にわかります。問題は木グラフをどう作るかなんです…

問題 No.344 ある無理数の累乗 - yukicoder 解法 r3 = sqrt(3) とします。(1+r3)^n と (1-r3)^n を足し算すると整数になります。また, この整数部分は, (1+r3)^n の整数部分の 2 倍と一致し, (1-r3)^n 部分は, 絶対値が常に 1 未満で, n が奇数の時は (1-r3)…

問題 No.340 雪の足跡 - yukicoder 解法 ある頂点から進むことのできる方向に制限ができるので, それを基に幅優先探索するのが基本です。ただ, 進むことの出来る方向を愚直に決定すると から の間で, 進む方向をメモするのに最悪 O(W) (O(H)) かかって, 入力…

問題 No.336 門松列列 - yukicoder 解法 こういう会話があったので, 包除原理で解いてみました。@mayoko_ 包除原理で解けると思います（https://t.co/GQAodcQbvS の部分問題です）— すぎむ (@sugim48) 2016, 1月 15この問題は, 下の問題の部分問題です。 may…

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