ARMERIA

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

AtCoder

HACK TO THE FUTURE 2020予選 参加記録

HACK TO THE FUTURE 2020予選 - AtCoder なんと全体10位で本戦に進むことができました! やったことを軽く書いておこうかと思います。けっこう雑な焼きなまし法なので、あまり参考になるかは分かりませんが… ビジュアライザのスクリーンショット等はexample_…

AtCoder Grand Contest 040 B - Two Contests

B - Two Contests 本番では考察不足で2ペナを出しましたが…自分の考察がある程度整理できたので書きます。 解法 公式解説にならい、それぞれのコンテストを「集合」、問題 を解ける人の範囲を「区間 」、コンテストの楽しさを「含まれる区間の共通部分の長さ…

CPSCO2019 Session1 F - Fruits in Season

お題箱より。 F - Fruits in Season 解法 最小値の最大化問題です。このタイプの問題はまず二分探索を考えてみる価値があります。 判定問題として、ある に対して「果物の美味しさの最小値を 以上にできるか?」という問題を考えます。最小値の最大化問題に…

AtCoder Beginner Contest 144 E - Gluttony

E - Gluttony 解法 この問題はいくつか考察ステップが必要なので、順に見ていきましょう。 記法などについて 簡単のため、入力として与えられる値の集合 を単に 、 を単に と書くことにします。 また、最小化すべき値である「メンバーと食べ物の組み方を決め…

Kyoto University Programming Contest 2019 E - 根付き森二人用ゲーム

お題箱より。 E - 根付き森二人用ゲーム 解法 それぞれの木を小規模なゲームとして解く スタート地点からある木に移動し、その木の葉に到達してスタート地点に戻るまでの一連の動作を考えます。このときゲームに本質的に影響するのは「次にスタート地点で手…

AtCoder Beginner Contest 143 F - Distinct Numbers

F - Distinct Numbers 解法 色々な解法があるみたいですが…この記事ではそれぞれの について独立に解きます。ある について解くときには、可能な操作回数には単調性があるので二分探索できます。 ある と操作回数 を固定したときに、操作を 回行えるかどうか…

AtCoder Regular Contest 077 E - guruguru

お題箱より。 E - guruguru 後半は公式解説と少し違う方法になっています。 解法 お気に入りで節約できる回数を定式化する ある1つの に対する から への移動を考えます。まず簡単のため、 と仮定しておきます。移動元と移動先をそれぞれ と書くことにします…

第一回日本最強プログラマー学生選手権決勝 C - Maximize Minimum

お題箱より。同じ問題に2件リクエストがありました。 C - Maximize Minimum 簡潔に飛ばし気味ではあるものの公式解説の説明が分かりやすいと思うので、流れは公式解説に沿いつつ図や行間を補って書いていきます。 解法 イチゴの最適な折り返し方 まずクエリ…

AtCoder Beginner Contest 054 D - Mixing Experiment

お題箱より。 D - Mixing Experiment 半分全列挙解法を…とのリクエストだったので、そちらを書きます。 解法 個の薬品をグループ0・グループ1に分け、それぞれについて薬品の選び方を決めたとします。これらを混ぜてちょうど混合比 になっているかどうかを判…

AtCoder Grand Contest 038 B - Sorting a Segment

B - Sorting a Segment 公式解説と少し違う方法で解いたので記録。 解法 ある長さ の区間を昇順に並び替えた時に、値が変更される最左のインデックスを 、最右のインデックスを とします。この時操作の結果は、閉区間 内の要素を昇順に並び替えたものとなり…

AtCoder Beginner Contest 141 E - Who Says a Pun?

E - Who Says a Pun? 解説で別解として紹介されている二分探索+ローリングハッシュで通したので書いておきます。 解法 条件を満たす長さで二分探索 「文字列 の連続部分文字列として位置が重ならずに2回以上出現する、長さ の文字列が存在する」ということ…

AtCoder Grand Contest 024 E - Sequence Growing Hard

E - Sequence Growing Hard 公式解説とだいたい同じ考察を辿ったんですが、最後の計算で違うことをしたので書いておきます。 解法 用語 要素を挿入して、辞書順でより大きくなる条件は 長さ の数列に1つ要素を挿入して、辞書順でより大きい長さ の数列を作る…

TTPC2019 オンライン参加記

てんぷらさんとチームpurameriaで出場しました。オンライン参加でしたが、せっかくのチーム戦だったので記事を書こうと思います。 はじまり アルメリアさんへTTPCチーム組みませんかてんぷら— てんぷら (@tempura_cpp) August 1, 2019 ご指名いただきました…

第一回日本最強プログラマー学生選手権-予選- C - Cell Inversion

C - Cell Inversion 解法 各マスの操作のされ方は、 自分より左のマスとペアになって、1つの反転操作区間の終点になる 自分より右のマスとペアになって、1つの反転操作区間の始点になる のどちらかです。そして各マスがそのどちらになるかは、実は端から順番…

「みんなのプロコン」本選 A - YahooYahooYahoo

お題箱より。 A - YahooYahooYahoo 解法 「編集距離DP」を知ろう まずは「編集距離DP」なるものを説明します。2つの文字列 の編集距離とは、文字列 に以下の操作を好きな順序で行って文字列 に一致させるための、操作回数の最小値です。 置換: の任意の1文…

AtCoder Beginner Contest 135 D - Digits Parade

お題箱より。 D - Digits Parade 「与えられた条件に従って各桁の数字を決められる」「出来上がる整数のうち、余りが特定の条件を満たすものを数える」という、是非とも押さえておきたい問題パターンの入門としてぴったりです。いつも以上に丁寧めに書きたい…

AtCoder Beginner Contest 138 F - Coincidence

F - Coincidence 解法 考察も実装もそこそこ重い問題です。順に考えていきましょう。 記法について 剰余演算を記号 、XOR演算を記号 で表すことにします。 またこの記事では数え上げの対象である2数のペアを ではなく の順番で記載しています。 ビットだけの…

CODE THANKS FESTIVAL 2017 H - Union Sets (並列二分探索解法)

お題箱より。 H - Union Sets 「公式解説で省略されている並列二分探索について知りたい」というリクエストだったのですが、私も実装したことがなかったので調べて書いてみました。私にとっても勉強になりました。 参考資料 参考にしました。 Parallel Binar…

AtCoder Beginner Contest 136 D - Gathering Children

D - Gathering Children 私の解法をTwitterに流したらわりと好評だったので記事にまとめておきます。 解法 ある程度動きをシミュレーションしてみると、十分に時間が経った後は全ての子供が RL の2マスで振動するということが分かります。最終状態を求めるた…

AtCoder Beginner Contest 136 F - Enclosed Points

F - Enclosed Points 解説 数え上げの軸を変える 個の部分集合それぞれについて、その集合に対応する長方形に 個の点のうちいくつ含まれるかを考え、それを全て合計したものを求めよ。 という問題です。部分集合の数が多すぎますね。まともに列挙するのは到…

AtCoder Beginner Contest 051 B - Sum of Three Integers

お題箱より。 B - Sum of Three Integers 計算量の考え方に入門するのにとてもいい問題です。 解法について知りたい…というリクエストだったので、色々な計算量で解く方法を解説してみました。 解法 全ての基本、全探索です。 を満たす を全て試します。和が…

AtCoder Beginner Contest 135 E - Golf

E - Golf 解法 コの字の作り方を考えてみる まずは考えやすい&実装しやすいように座標変換をします。 に負の値がある場合、符号反転させて両方とも非負としておきます。 始点 から終点 までボールが移動する軌道は、長さの総和が の倍数になっている必要が…

AtCoder Beginner Contest 134 F - Permutation Oddness

F - Permutation Oddness ※問題文で与えられている は小文字ですが、 を添え字として使いたいので本記事では と表記します。 解法 順列のDP 順列の場合の数を求める問題です。何か条件を満たす数列の個数を求める問題として「左からDP」というのはメジャーな…

AtCoder Regular Contest 052 D - 9

D - 9 公式Editorialと違う解法で解いたので記録。 計算量多めのゴリ押し解法なのでRuby・PyPyでは通りませんでした… 解法 まず桁DPを考えました。以下のように状態を考えることができます。 上から 桁目までの数字まで決めて、そこまで決めた値を で割った…

CPSCO2019 Session2 E - Mogu Mogu Gummi

お題箱より。 E - Mogu Mogu Gummi 解法 木DPを考えてみる 「連結成分の個数」よりも「切った辺の本数」のほうが遷移を組みやすいので、そっちで考えます。連結成分の個数は切った辺の本数に1を足したものです。 シンプルなグラフを例にして考えてみましょう…

天下一プログラマーコンテスト2016予選A B - PackDrop

お題箱より。 B - PackDrop 解法 まずは問題をシンプルに みたいなのがややこしいですね。まずは問題をシンプルに言い換えましょう。 ネットワーク全体は機器を頂点、その間を接続する経路を辺とするグラフとみなせます。より具体的には機器0を根とする根付…

AtCoder Beginner Contest 133 F - Colorful Tree

F - Colorful Tree 解法 木の2点間距離たくさん→LCA 長さの変更についていったん無視すると、この問題は「木の2点間距離をたくさん求めてください」というものです。これはLCA(最小共通祖先)というものを用いると効率的に求めることができます。 根付き木…

AtCoder Regular Contest 085 E - MUL

お題箱より。 E - MUL 解法 私自身、この問題は解説を読んで衝撃を受けた記憶があります。知らないと自力で思いつくのは相当難しいので、テクニックとして覚えてしまいましょう。 先人の知恵 競プロでは俗称「燃やす埋める問題」と言われている問題カテゴリ…

AtCoder Beginner Contest 130 E - Common Subsequence

E - Common Subsequence 公式解説とほとんど同じだけど、二次元累積和が出てこないようなDPで解いたので記録しておきます。 解法 記法について 数列 を単に 、数列 を単に と書くことにします。 与えられた数列は1-indexedで扱い、「0要素目」として空の要素…

AtCoder Beginner Contest 130 F - Minimum Bounding Box

F - Minimum Bounding Box 解法 各座標軸ごとに、動きのイメージをつかむ 時刻を文字 で表し、 に依存する変数を のように表します。 まず、 座標を分けて考えてみます。 座標だけに注目すると、それぞれの点は以下の3つにグループ分けできます。 グループ1…