F - Pond Skater 解法 1ターンに1マスの移動であればグリッド上のBFSで解けますが、今回は1ターンに マスまで動くことができます。これをそのままBFSで処理すると1つのマスから遷移可能なマスが最大 個になり、全体計算量 になって間に合いません。 具体的に…

D - Knapsack Queries on a tree Editorialと同じ解法で解いたのでそっちを書きます。クエリごとに独立に解く方法もあって、そっちで解いた人のほうが多そうな印象です。 解法 が十分大きいという前提で解説をします。また扱う重みの最大値を 、最大深さの半…

C - Range Set 解法 必要十分条件への言い換え ある01文字列が与えられた時に、それが操作によって生成可能であるかを判定することを考えます。 ここで今回のように「塗り潰す」系の操作の場合、「判定したい文字列から逆順で操作を行い、初期状態に戻せるか…

お題箱より。 D - 大ジャンプ 解法 まずは計算しやすいようにいくつか前処理をします。 ゴールまでの 軸方向それぞれの距離を で割ることで「正の方向にジャンプ○回分」という値に変換します。ここで割り切れない場合、答えは です。今後は で割った後の値を…

A - Pay to Win 公式解説、丁寧だけど英語なんですよね…だいたいそのまま訳す感じの解説になってしまいそうですが許してください。 解法 操作を限定できる形に持ち込む いきなりですが、操作を逆から考えます。 気持ちとしては、 からの操作を考えるとどの遷…

F - . (Single Dot) 解法の理解というよりは実装慣れのほうが重要な問題だと思います。末尾につけているACコード例と対応させながら読んでいくといいかもしれません。 解法 図における座標軸は問題文に従い、北を上にして図示するようにします。一般的なXY平…

E - Colorful Blocks 解法 「隣り合うブロックの組であって同じ色で塗られている組」がちょうど 個あるとして、 についてそれぞれ求めた場合の数を合計することで答えを求めます。 ブロックは全部で 個なので、ブロックが隣り合っている箇所は 箇所です。こ…

F - Bracket Sequencing 解法 「正しい括弧列」について この問題だと単に括弧列という言葉が使われていますが、どちらかと言うと「正しい括弧列」みたいな呼ばれ方をされることが多いです。 正しい括弧列の条件は、言葉で書くと 開き括弧と閉じ括弧の数が等…

AtCoder Beginner Contest 165 - AtCoder 解法 得点の計算方法が面倒で、賢い解き方はなかなか思い浮かびません。制約が小さいことに注目して全探索の方針を考えます。 制約上の最大値である で考えます。数列 としてあり得るものは、単純に見積もると 以上 …

お題箱より。 A - Dividing a String 貪欲とDPどちらを書こうか迷いましたが、貪欲解法のほうで書きたいと思います。 問題概要 文字列 が与えられる。この をできるだけ多くの部分文字列に分割したい。ただし、隣り合う2つの部分文字列が一致してはならない…

お題箱より。 F - Select Half 前置き リクエストでは「そもそもなぜDPを思いつくのか」を知りたいという声をもらったのですが…この点は非常に難しいと思っています。というのも、私の場合はDPで最終的に解けない問題であっても考察途中で「DPできないか？」…

F - path pass i 公式解説とは違う方法で、計算量は であまり良くないのですが、私が解いた解法をまとめておきます。 解説 「通らないもの」を数える 頂点数が であるとき、単純パスの総数は 個です。色 について解く時には、この総数から「色 の頂点を通ら…

F - Distributing Integers 解法 「頂点に整数を書く」だと少し図示しづらいので、代わりに「頂点番号の書いたボールを処理する順番に並べる」として考えることにします。 最初にボールを置く頂点を根付き木の根とします。まずは根を頂点 に固定して問題を解…

お題箱より。 E - Max GCD 解法の正当性について知りたいというリクエストだったので、そこをメインに解説します。 解法 操作によって全ての要素の合計は変わりません。そして操作後の の全要素が値 の倍数であるならば、 の合計値も の倍数であるはずです。…

お題箱より。 E - Second Sum 解法 まずは「数え上げの順番をひっくり返す」という発想が大事です。 全ての区間 について、その区間内で2番目に大きい値 を求め、合計する をひっくり返して、 順列内の全ての要素 について、その要素が2番手になるような区間…

D - Merge Triplets 解法 操作の説明で登場する長さ の数列たちを「ミニ数列」と呼ぶことにします。 結果的にできる順列にどのような特徴があるかを考える上で、まず一番大きな値に注目すると良いと思います。 最大値 は、 が存在しているミニ数列以外の要素…

お題箱より。 D - Ki 様々な木の問題を解く上で基本となるような実装なので、実装も含めて解説します。 解法 1回の操作のイメージを図にすると以下のようになります。 実際には大量の操作があるので、これを1つ1つ処理していくことはできません。ではどうす…

E - Payment 上から派と下から派がいたようですが、私は上からで解いたのでそちらで書きます。 解法 上の桁から見ていって、その桁までで支払う＆お釣りとして受け取る硬貨の枚数をなるべく小さくすることを考えます。 例えば 円だったとして、 の位の桁まで…

D - Pairs ※正直、これがABC-Dとして出るのはここ最近の傾向からすると異常です。じっくり解説を読んで理解するか、どうしても分からなければ温めておくのも手でしょう。 解法 二分探索に落とし込む 与えられた数列などに対して大量の数を計算し、その 番目…

お題箱より。 E - Children and Candies 部分点解法から満点解法へのステップアップについて重点的に書きます。 解法 部分点解法 部分点解法は公式解説にもしっかり書かれているので軽く。各 について なので、ある1つの組 に対してだけ を求めてください、…

E - Increasing Numbers 公式解説と少し違う方法で解いたので記録しておきます。 解法 十進法の桁を、一番下の桁を 桁目とするように表記します。 桁目は に対応する桁です。 「各桁から を引く回数」の条件への言い換え 非負整数が増加的であることは、「1…

F - Monochromization 解説放送を観て解いたので、その方針をベースに書きます。 解法 まずは判定問題 まず、ある盤面が初期盤面から操作を繰り返した後の最終状態として作れるかどうかの判定方法を考えます。 ある最終状態の盤面から操作を逆回しして考えま…

E - Span Covering 本番中実装しきれなかったけど、公式解説と違う方法で解いたので記録。 解法 包除原理の適用 土地を 個のマスが並んだものとして扱います。このマスのうち0個以上のマスを選んだ集合 について、 に含まれるマスだけに全てのシートを置く（…

C - Cookie Distribution 解法 式変形と言い換え 全てのクッキーの配り方の集合を 、答えを とします。答えは の期待値に全ての配り方の通り数を掛けたものなので、 を全ての配り方について合計したもの、つまり以下のように表現できます。 実際には各 は配…

D - Arrangement 公式解説の読解がちょっとつらいので、それよりは分かりやすい解法になっているはず… 解法 まずは貪欲に作ってみる 「カード の右隣のカードがカード であってはならない」という条件は、そんなに厳しい条件ではないように思います。なので…

お題箱より。 F - Count Permutations Many Times 難しめの（とはいえ上級者には比較的知名度が高い）テクニックを複数使いこなす必要がある問題です。公式解説では多項式の係数に対応させて解いていますが、そうではない方法で説明しようと思います。 解法 …

お題箱より。 A - 1D Matching 解法 まずはケーブルの長さの合計が最小になる条件を考えましょう。 座標点を数直線上に並べて、小さい方（左）から見ていくことを考えましょう。このとき各点について「保留して、それより右側の座標点と繋ぐことにする」か「…

オンサイト本戦に参加し、その1で8位、その2で10位のダブル入賞でした！ ネタになるエピソードとか写真とかは特にないので、マジメにコンテストについて書こうと思います。 本戦1 A - 千の木 問題を理解し、正の得点を得る提出をするまで49分。ここまでのハ…

お題箱より。 E - Grouping 解法 グループを作れる条件がなかなか扱いづらいことや制約の小ささからDPの線を考えます。 上手くDPを組むコツは「覚えておくべき情報を減らす」、逆に言うと「状態を忘れられるようにする」ことです。例えばこの問題において、…

お題箱より。 F - Laminate 解法 問題で最小化すべき値である「塗る操作の回数」を「コスト」と呼ぶことにします。また各 の値を「高さ」と呼ぶことにします。 説明をやりやすくするため、0列目に である列が存在すると考えます。 の値が確定した後、コスト…