読者です 読者をやめる 読者になる 読者になる

mayoko’s diary

プロコンとかいろいろ。

yukicoder

yukicoder No.417 チューリップバブル

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

yukicoder No.416 旅行会社

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

yukicoder No.409 ダイエット

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

yukicoder No.408 五輪ピック

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

yukicoder No.404 部分門松列

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

yukicoder No.399 動的な領主(その2)

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

yukicoder No.399 動的な領主

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

yukicoder No.398 ハーフパイプ(2)

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

yukicoder No.393 2本の竹

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

yukicoder No.391 CODING WAR

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

yukicoder No.389 ロジックパズルの組み合わせ

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

yukicoder No.387 ハンコ

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

yukicoder No.386 貪欲な領主

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

yukicoder No.385 カップ麺生活

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

yukicoder No.377 背景パターン

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

yukicoder No.381 名声値を稼ごう Extra

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

yukicoder No.376 立方体のN等分 (2)

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

yukicoder No.374 コイン

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

yukicoder No.367 ナイトの転身

問題 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[…

yukicoder No.359 門松行列

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

yukicoder No.362 門松ナンバー

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

yukicoder No.361 門松ゲーム2

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

yukicoder No.355 数当てゲーム(2)

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

yukicoder No.352 カード並べ

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

yukicoder No.351 市松スライドパズル

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

yukicoder No.348 カゴメカゴメ

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

yukicoder No.344 ある無理数の累乗

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

yukicoder No.340 雪の足跡

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

yukicoder No.336 門松列列

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

yukicoder No.332 数列をプレゼントに

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

yukicoder No.331 CodeRunnerでやれ

問題 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 =…

yukicoder No.330 Eigenvalue Decomposition

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

yukicoder No.329 全射

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

yukicoder No.137 貯金箱の焦り

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

yukicoder No.328 きれいな連立方程式

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

yukicoder No.325 マンハッタン距離2

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

yukicoder No.324 落ちてた閉路グラフ

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

yukicoder No.322 Geometry Dash

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

yukicoder No.321 (P,Q)-サンタと街の子供たち

すごく好きなタイプの問題です。 問題 No.321 (P,Q)-サンタと街の子供たち - yukicoder 解法 a*P + b*Q は, P と Q の最大公約数 G に関して, c*G (c は整数) という整数値すべてを取ることはよく知られています。 今回も似たようなことが出来ますが, (c*G, …

yukicoder No.320 眠れない夜に

問題 No.320 眠れない夜に - yukicoder 解法 フィボナッチ数列の第 n 項を fib[n] とします。 を計算する際に間違えて -1 したとすると, そのマイナスの影響は, 第 m+n 項には fib[n] になって帰ってきます。なので, やることとしては, 第 N 項の数をフィボ…

yukicoder No.318 学学学学学

問題 No.318 学学学学学 - yukicoder 解法 解法はこの問題に似ている気がします。 mayokoex.hatenablog.com大きい数が最後に挟み撃ちするということは, 要するに大きい数のほうが優先的に採用されるということなので, 大きい数から順番に数を決定していきま…

yukicoder No.317 辺の追加

いろいろ勉強になりました。良い問題。 問題 No.317 辺の追加 - yukicoder 解法 よくある計算量の短縮で, 「 が に収束する」というのがあります。今回はこれを利用しましょう。まず UnionFind を使ってグラフ上の連結成分, およびその連結成分の頂点数を求…

yukicoder No.315 世界のなんとか3.5

問題 No.315 世界のなんとか3.5 - yukicoder 解法 まずよくある桁 DP っぽく考えると, dp[n][big][exist3][mod3][modP] = (n 桁目で元の数が今作ってる数より大きくなっているフラグが big で 3 が数字に含まれているフラグが exist3 で 3 で割った余りが mo…

yukicoder No.309 シャイな人たち (1)

問題 No.309 シャイな人たち (1) - yukicoder 解法 この問題に考え方が非常に似ています。mayokoex.hatenablog.com各行について「手をあげる人の集合」を考えると, これは別の場合と独立に考えることができるので happy ということです。 具体的には, dp[r][…

yukicoder No.308 素数は通れません

問題 No.308 素数は通れません - yukicoder 解法 w = 1, 2, 3, ... と調べていくとわかるのですが, w = 7 までは, 素数に囲まれて 20 程度までしか辿り着けません。 一方で, w = 8 になると, n が 32 以上になれば必ず 8m+2, 8m+4, 8m+6, 8m+8 の列にたどり…

yukicoder No.307 最近色塗る問題多くない?

問題 No.307 最近色塗る問題多くない? - yukicoder 解法 すべての盤面が一色になるまでは各クエリごとに幅優先探索をして愚直に色を変えていき, すべての盤面が一色になったら各クエリごとに全体の色が変わることを O(1) で記憶しておけば良いです。計算量…

yukicoder No.301 サイコロで確率問題 (1)

問題 No.301 サイコロで確率問題 (1) - yukicoder 解法 N が十分大きい時は N+(5/3) に収束します。 他の場合は No.75 と同じです。mayokoex.hatenablog.comが, 別の方法で解きました。 各 dp[i] は dp[0] の線形で書けるので, dp[0] = a0 * dp[0] + b0 とい…

yukicoder No.75 回数の期待値の問題

問題 No.75 回数の期待値の問題 - yukicoder 解法 冷静に漸化式を立てます。dp[i] = (今のマスが i の時にゴールするために必要なサイコロをふる回数の期待値)とすると, dp[i] = 1/6 * dp[i+1] + ... + 1/6 * dp[i+6]とします。求めたいのは dp[0] ですね。…

yukicoder No.42 貯金箱の溜息

問題 No.42 貯金箱の溜息 - yukicoder 解法 持っている硬貨をそれぞれ C[0] = 1, C[1] = 5, ..., C[5] = 500 とします。普通の dp で解こうとすると, dp[x][M] = (C[x] 円以下の硬貨で M 円を支払う場合の数)となりますが, この dp はdp[x][M] = dp[x-1][M] …

yukicoder No.41 貯金箱の溜息(EASY)

問題 No.41 貯金箱の溜息(EASY) - yukicoder 解法 1 円玉を除けば, 六並び国では 111111 円の倍数のお金しか支払うことが出来ません。よって, M 円を 111111 円で割った商を 1, 2, ..., 9 の和で何通り表すことができるか, という dp 問題にすることが出来…