E - Majority of Balls 解法 キーとなるのは以下の2つの気付きです。 に対する質問の答えと に対する質問の答えは必ず異なる。片方が Red であればもう片方は Blue である。 もし「赤青が半々ずつ」ということが分かっている 個のボールの集合が得られたとす…

F - Sugoroku 解法 個の連続するゲームオーバーマスがある場合はゴール不可能なので、そうでないことを仮定します。「最小ターン数」と「辞書順最小」、それぞれに注目します。 ゴールするための最小ターン数はDP等で求めることができます（後で具体的に説明…

お題箱より。 F - Xor Sum 3 線形代数を用いた解法の正当性について理解したい…というリクエストだったので、そこを重点的に書きます。 前段の考察 を表すビット桁を 桁目と表記することにします。一番下が0桁目です。 各ビット桁ごとに、 のうち 桁目が立っ…

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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