問題のリンク E - + Graph 考察 一つの頂点に数を書き込んだらあとは一意に決まる。とりあえず頂点1 にx と書き込んでみる。すると他の頂点の数はx を含む式で書き表せる。 サンプル2 頂点に書き込める数字は正の整数なので、1 <= x <= 3 が答えになりうる。…

問題のリンク D - Modulo Operations 考察 少し自分の手で操作をしてみて気づくことは、S[i] < S[j] を満たすとき、S[i]、S[j] の順番に取り除くと、S[i]をとり除いた後、黒板に書かれた数はS[i] 未満になっているので、S[j] を取り除いても黒板の数は変わら…

問題のリンク C - Best-of-(2n-1) 考察 期待値DPがしたい E[i][j] := 高橋くんがi 回、青木くんがj 回勝っている状態からどちらかがN回勝つまでに行われるゲームの回数の期待値。 とすると、期待値DPの通常の手続きで解ける、がO(N ) は通らない。 タイトル…

問題のリンク D - 11 考察 ほとんどの要素が異なるので、異なる場所から取り出した部分列は大体異なる。同じになるパターンを数えるのが速そう。 同じになるパターンに関係してくるのはa[i] = a[j] ( i j ) を満たすもの。そのようなi, j と他の要素を区別し…

問題のリンク E - Tak and Hotels 考察 1 日でいけるところまでいく、を繰り返すのが最善。x[i] から1 日でいける最も右にあるホテルの位置は、二分探索で簡単に求まる。 サンプル1 はこんな感じになる。（0 - indexed） クエリ1 個目のホテル0 からホテル7 …

問題のリンク E - Change a Little Bit 考察 こういう問題はそれぞれの要素が合計何回足されるかを調べれば良さそう。 コストの和を最小にするためには、Si Ti を満たすようなi のうち、c[i] が小さい順に変更していくのが最適であるとすぐにわかる。 さて、…

問題のリンク C - Closed Rooms 考察 操作は、 1. 最大Kマス進む 2. 最大K個'#' を'.' に変える ゴールするのは操作1 をした直後であるので、1→2 という操作を考える代わりに2→1 と考えたほうが見通しが良さそう。 2→1 という操作を考えると、1 で進むKマス…

問題のリンク B - Hamiltonish Path 連結な単純無向グラフが与えられる。以下の3条件を満たすパスを見つけなさい。 2個以上の頂点を通る 同じ頂点を2度以上通らない パスの少なくとも一方の端点と直接辺で結ばれている頂点は、必ずパスに含まれる 考察 解説A…

負の香り高さを持つイワシ、どんな臭いがするのでしょうか 問題のリンク E - ∙ (Bullet) 考察 それぞれのイワシについて、仲が悪いイワシの数を数えることはまさにこれ keke.hatenadiary.com 今回の条件は なのでちょっと変形して、 にすれば、数々の過去問…

基礎的な数え上げの範疇です。 部分集合の数を数え上げたい 要素がK個（以下サイズがKという）の集合Sの部分集合の数は、 である（空集合を含む）。これはそれぞれの要素について、その要素が部分集合に入るか？入らないか？の2 通りあり、その選び方は他の…

どういうことか 問題 整数列a = { } が与えられる。a[i] = a[j] ( i < j ) となるような(i, j) の組の数を求めてください。 (i, j) の組を全探索すると当然求められるが、 でTLEしてしまう。 そこで、片方を固定することを考えてみる。j を固定して、i < j …

期待値の問題を解きたかったので 問題のリンク E - デフレゲーム 考察 とりあえず小さいn で実験。 ・n = 2 サンプル1 通り、0.25 * 1 + 0.25 * 2 + 0.5 * 3 = 2.25。 ここで、3を1+2 と見て、(0.25 + 0.5) * 1 + (0.25 + 0.5) * 2 = 2.25 と見る。これは、 …

声に出して読みたい問題名、他にはMatch Matching 問題のリンク E - Meaningful Mean 考察 半開区間[l, r) の部分列{ } の要素の算術平均は、累積和（ ）を用いて、 と表せるので、問題の条件は、次のように言い換えられる。 簡単な変形によって、この式は …

久しぶりにこどふぉしました。それもこれもDeepLの翻訳のおかげです。 問題のリンク Problem - D - Codeforces 問題の概要 ・数列a が与えられる。以下の操作を繰り返して数列の全ての要素をk にできるか？ （操作） 数列aから連続した部分列Sを選択し、Sの…

方針ガチャ、成功！ 問題のリンク E - Colorful Blocks コンテスト中の思考過程 DP？ ・dp[i][j] := 前からi 個目のブロックまで見て、今まで同色で塗られた隣り合うブロックの組がj 個ある場合のブロックの並べ方の数。 ・これはO(NK) でTLE。この方針で高…

はじめに ありがとう、ミカミくん 問題のリンク D - Teleporter コンテスト中の思考過程 ・これは最近見たことある！延々と辞書を引かされ続けるミカミくんだ！！ D - へんてこ辞書 ・ありがとう、ミカミくん 解法１ : ループを見つけて周期性を利用する ・…

問題のリンク I - Coins 思考過程 ・N枚全てのコインを振って、表がx 枚となる確率P(x) を0 <= x <= N について求めたらよい。 ・独立な試行とDPは非常に相性が良い。 DP table というわけでDP。 ・dp[i][j] := i枚目までのコインを振って、表がj 枚出るとい…

はじめに ABC164Eで拡張ダイクストラが出題され、解けなかった。 拡張ダイクストラを実装するときに迷わないように手続きをまとめておく。 拡張ダイクストラとは ・頂点を増やしてダイクストラをすること。 僕のダイクストラ実装 //************************…

解いた問題を忘れているので思い出そうキャンペーン 問題のリンク E - Payment 思考過程 ・めっちゃ桁DPしたい制約。 ・とりあえず、Nの桁数より2桁多い金額を支払うのは無駄。 ・桁ごとに払う金額と紙幣の枚数を決めていきたい。繰り下がりを考えないといけ…

問題のリンク Q - Flowers 思考過程 ・LIS（最長増加部分列）問題の拡張版。重み付きLIS。 ・いわゆるインラインDPというやつ。DP table を1次元にして、セグ木にのせる。 ・セグ木版LISを重み付きで行う。逆に、LISは全重みが1のFlowersであると言える。 ・…

EDPC ・順次追加していくよ A Frog 1 B Frog 2 C Vacation D Knapsack 1 E Knapsack 2 F LCS G Longest Path H Grid 1 I Coins J Sushi K Stones L Deque M Candies N Slimes O Matching P Independent Set Q Flowers R Walk S Digit Sum T Permutation U Gr…

僕はAGC好きですよ、じっくり問題が解けるので 問題のリンク D - We Like AGC 思考過程 ・禁止されたパターンがあるタイプの数えあげDP。EDPCのC。 ・禁止された状態は以下の5つ。（Xはワイルドカード） 1. AGC 2. ACG 3. CAG 4. AGXC 5. AXGC ・前の3つまで…