ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

AtCoder

AtCoder LibraryのLazy Segtreeのチートシート

AtCoder LibraryのLazy Segtreeの使い方 - ARMERIA こちらの記事でAtCoder LibraryのLazy Segtreeの使い方を説明しましたが、コンテスト中に読んでられっか!みたいな時のためにコピペで使えるチートシートをまとめます。整数列に対する、以下の組み合わせ6…

AtCoder LibraryのLazy Segtreeの使い方

AtCoder Libraryが遅延伝播機能を持つセグメント木 atcoder::lazy_segtree を提供しているものの、何か渡すものいっぱいあるしドキュメントは数学用語だらけだしよく分からん!みたいな人向けの記事です。 問題を解いていて、セグメント木に必要な機能(区間…

キーエンス プログラミング コンテスト 2020 D - Swap and Flip

お題箱より。 D - Swap and Flip 解法 この問題のように「操作する場所を選んで、決められたルールに従って操作する」ということを繰り返す問題では、1回目の操作の選択、2回目の操作の選択…といった分岐パターンを直接探索していくのは非常に大変です。操作…

AtCoder Beginner Contest 178 F - Contrast

F - Contrast 解法が色々ある問題。シンプルで実装も楽な解法1と、私が本番で解いた解法2を証明付きで紹介します。前者のほうが断然オススメ。 解法1 まず 合計で 個を超える値が存在する場合、どのように並べても となる箇所が存在してしまいます。この場合…

AtCoder Library Practice Contest I - Number of Substrings

お題箱より。 I - Number of Substrings 解法 ※この問題における文字列 の部分文字列とは、 の連続な部分を取り出した文字列であることに注意してください。慣習的に、「部分列」と書くと連続とは限らない取り出し方、「部分文字列」と書くと連続な取り出し…

AtCoder Regular Contest 092 C - 2D Plane 2N Points

お題箱より。 C - 2D Plane 2N Points 以前の自分が解法の正当性を理解するのにすごく悩んだ問題で、印象深いです。 解法 考察 2次元の座標点を扱う際には「平面走査」というテクニックがよく使われます。これは座標点をある一方の座標、例えば 座標でソート…

DDCC 2016 本選 C - 特別講演「括弧列と塗り分け」

お題箱より。 C - 特別講演「括弧列と塗り分け」 解法 この問題を考えるにあたって重要なのが、正しい括弧列を根付き木と対応づけることです。 それぞれの括弧1組ずつを頂点とみなします。そしてその括弧の1つ外側を囲っている括弧を親とみなすように辺を張…

AtCoder Beginner Contest 170 E - Smart Infants

お題箱より。実装方法に関するリクエストだったので実装中心で書きます。 E - Smart Infants 解法 解法としてはシミュレーションです。園児が移動したときに、どのようなデータを管理しておけば効率的に答えを更新できるかを考えます。 今回は以下のようなデ…

CPSCO2019 Session3 F - Flexible Permutation O(N^2)解法

お題箱より。 解法が知りたいというリクエストだったので考えてみました。 F - Flexible Permutation 解法 後に扱うDPの都合上、個人的にはインデックスよりも値に注目したほうが理解しやすいので、条件を値中心の言葉に言い換えます。 であるような値 を「…

エイシング プログラミング コンテスト 2020 F - Two Snuke

F - Two Snuke 公式解説とは違う解法です。 解法 のときは答えは なので、 とします。 まずは 解法を まず答えを で求める方法を考えます。 の値を として、これを全通り試しましょう。そうすると、この を つに分ける分け方が 通りあります。 個並んだボー…

AtCoder Grand Contest 043 C - Giant Graph

お題箱より。 C - Giant Graph この問題は数ヶ月前に「なぜこの発想を思いつけるのか分からない」というリクエストをもらっていて、私にも分からなかったので記事を書けずにいました。でしたが、(同じ人が違う人かは分かりませんが)2つ目のリクエストをも…

Introduction to Heuristics Contest 参加記録

Introduction to Heuristics Contest - AtCoder 33位でした。 戦略 焼きなまし法を選択しました。 理由は、問題の性質として解の局所改善がやりやすく、スコアの差分計算を高速化して大量に回せそうだと考えたからです。対して、1手の変更がその後の展開を大…

AtCoder Beginner Contest 171 F - Strivore

F - Strivore 解法 文字列 の長さを とします。また最終的に出来上がる文字列を と表記します。 の長さは になります。そのうち元々あった文字と追加した文字の場所の割り当て方が 通りで、追加した文字の種類が 通りで…とやりたくなりますが、これでは最終…

AtCoder Grand Contest 046 C - Shift

C - Shift 解法 に含まれる 0 の個数を 、1 の個数を と書くことにします。 を、0 で区切られた 個のエリアに分割します。 図に示すように、エリア に含まれる 1 の個数を とし、エリア を含むそれ以前に含まれる 1 の個数を とします。 本問題の操作は、1 …

AtCoder Grand Contest 046 B - Extension

B - Extension 解法 まず以下のようなDPを考えてみましょう。 本問題の操作によって、縦 行、横 列になるまで操作してできる盤面の数 このDPで「上側に行を足し、その1つを黒く塗る」遷移と「右側に列を足し、その1つを黒く塗る」遷移をすれば良さそうですが…

AtCoder Beginner Contest 170 F - Pond Skater

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

東京海上日動 プログラミングコンテスト2020 D - Knapsack Queries on a tree

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

AtCoder Grand Contest 045 C - Range Set

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

AtCoder Beginner Contest 011 D - 大ジャンプ

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

AtCoder Grand Contest 044 A - Pay to Win

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

AtCoder Beginner Contest 168 F - . (Single Dot)

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

AtCoder Beginner Contest 167 E - Colorful Blocks

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

AtCoder Beginner Contest 167 F - Bracket Sequencing

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

AtCoder Beginner Contest 165 C - Many Requirements

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

AtCoder Grand Contest 037 A - Dividing a String

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

AtCoder Beginner Contest 162 F - Select Half

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

AtCoder Beginner Contest 163 F - path pass i(マージテク解法)

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

AtCoder Beginner Contest 160 F - Distributing Integers

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

AtCoder Beginner Contest 136 E - Max GCD

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

AtCoder Beginner Contest 140 E - Second Sum

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