mayoko’s diary

プロコンとかいろいろ。

yukicoder

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 問題にすることが出来…

yukicoder No.298 話の伝達

はい・・・・・・・・・・・・・・・・・・・・・・・・・・・・・ 問題 No.298 話の伝達 - yukicoder 解法 割と引っかかる人多い気がするので誤解法も紹介します。 想定誤解法では, dp[i] = (i に話が伝達しない確率)として, 1-dp[N-1] を求めることを目標にします。各 i の dp[i] を求め…

yukicoder No.297 カードの数式

yukicoder に参加しました。初めて作問して出題したのですが, 想定解が間違っていて申し訳ないです… 問題 No.297 カードの数式 - yukicoder 解法 一つ巨大な数を作ってそれ以外の数をひと桁にすると最大, 最小の数が作れそうです。 ただ, マイナス演算子がひ…

yukicoder No.14 最小公倍数ソート

問題 No.14 最小公倍数ソート - yukicoder 解法 先に解法を説明してからなんでそれで良いのかを説明する感じでいきます。まず解法ですが, 最初に 各 ai の約数 div を求めていき, divs[i] という配列にその約数を入れていくと同時に, set を用意して set[div…

yukicoder No.31 悪のミックスジュース

問題 No.31 悪のミックスジュース - yukicoder 解法 まず, N >= V の場合はそれぞれのジュースを 1 リットルずつ買って適当に分配すれば良いです。 V > N の場合もとりあえずすべてのジュースを 1 リットルずつ買っておけば「使わない果物があってはいけない…

yukicoder No.291 黒い文字列

問題 No.291 黒い文字列 - yukicoder 解法 dp[n][k][u][r][o] = (n 文字目までの時点で, "K" のストックが k 個, "KU" のストックが u 個, "KUR" のストックが r 個...) の時の"KUROI" が出来た substring の数 という DP をやります。最高で 100/5 = 20 個…

yukicoder No.288 貯金箱の仕事

問題 No.288 貯金箱の仕事 - yukicoder 解法 まず, ゆきうさぎさんはまずお金を全部貯金箱さんに預けて, そのあと貯金箱さんがなるべく少ない硬貨の枚数でゆきうさぎさんに返せば良い, ということがわかります。つまり, この問題は本質的には「お金をなるべ…

yukicoder No.285〜No.287

問題 No.285 消費税2 - yukicoder No.286 Modulo Discount Store - yukicoder No.287 場合の数 - yukicoder 解法 No.285 はタネあかしすると簡単で, 元の値段に 108 を掛けたあと, それを 100 で割った商が整数部分, 100 で割った余りが少数部分になります…

yukicoder No.282 おもりと天秤(2)

問題 No.282 おもりと天秤(2) - yukicoder 解法 奇偶転置ソートというアルゴリズムを利用します。 奇偶転置ソート - Wikipedia bool cmp[505][505]; int C[505]; bool comp(int a, int b) {return cmp[a][b];} int main() { int N; cin >> N; vector<int> ans(N);</int>…

yukicoder No.281 門松と魔法(1)

問題 No.281 門松と魔法(1) - yukicoder 解法 まず d = 0 の場合は, 現在の高さの配分が上手くいってるかどうかだけで 0 か -1 かを判定できます。それ以外の場合は, 真ん中を一番高くするか, 一番低くするかで場合分けすれば良いです。 int H[3]; const ll …

yukicoder No.277 根掘り葉掘り

yukicoder に参加しました。みんな作問になんとなく「センス」があるのを感じて羨ましいなぁと思っています。 問題 No.277 根掘り葉掘り - yukicoder 解法 30 分くらい想定誤解法で考えていました。 部分木に対する木 DP の要領でやろうとすると頂点 v につ…