ARC152 A-C を解くための考え方
ARC152 の writer をしました、riano_ と申します。
ご参加いただいた方、またコンテスト後に問題を解いてくださった方、ありがとうございます。多くの方に取り組んでいただけるのが何より嬉しいです。
さて、ARC152 では B,C の難易度が比較的高く、苦戦された方が多かったように思います。難易度推定については（writer自身の当初の推定として）やや外してしまった部分があり、次の機会があればこの反省を活かしたいと思っています。
解法、およびその正当性は公式解説に記した通りですが、「どうやったら解ける（解法を思いつく）のか分からない」「この問題から他の問題にも通用する何らかの示唆を得たい」という声もあるようでしたので、writer 自身の考えた道筋を書いてみようと思います（この 3 問は、解法からではなく問題設定から作ったので、コンテスタントとほぼ同じ前提で解いています）。
当然ながら、思いっきりネタバレを含みますので、できれば自力で考えてみてから読んでいただけると嬉しいです。
まず、どのような座り方をしても確実に全員座れる、という表現を、出来る限り妨害しても全員座れてしまう、と言い換えます。直感的に同じとみなせる人は特に必要ないかもしれませんが、後者の言い方をすると、誰かが座れないように意地悪をするという「目的」が明確になります。目的が明確になれば、その目的を達成するための方法を構築する、といった小問題に思考を移すことができます。
次に、座れないとしたら 2 人組で、一番厳しい状況がありそうなのは最後の 2 人組である、という点がポイントになります。これ自体は比較的易しめですが、「条件を満たさなくなるとしたらどんな場合か」を考えてその性質を捉えることは、汎用的に通用する考え方ではないかと思います（実際、B も似たような考え方だと思っています）。
この問題では、第一に、二人の位置関係が二度入れ替わる必要がある、という観察が重要です。これ自体は、実験して気づいたものなのですが、実験の際に「何が不自由な点か」に着目するのがよいと思います。
仮に、すれ違いが自由だとしたら、明らかに、両者が最速で歩き続けることが最適解になります。それに対して、例えばサンプル 1 の説明通りの動かし方を考えた際、最短の時間を達成したい、という目的の障壁になっているのは、休憩所で待っている時間です。待ち時間が生じるのは、すれ違いが決められた点でしかできないからなので、そう考えると、すれ違いに着目して、その性質を洗い出したい気分になります。
このような思考は、一般化すると、「目的に対して強い制限となる箇所に注目する」あるいは雑に言うと「何がめんどくさいのかを考える」という意味で、A 問題後半の考察パターンとも近い部分があるのではないかと思います。
次に、すれ違いが 2 回あることによって、なぜ待ち時間が生じてしまっているのかを考えます。動かし方に制限を与える箇所を特定したので、次は「どう制限を与えているのか」を考えるということです。
一方、すれ違い以外はほぼ自由なので、その間は最速で動き続けることにします。これは「重要でない部分の自由度は捨ててしまう」という考え方です。重要な部分を特定できた場合、このような処理を行っておくと問題がシンプルになることが多いかもしれません。
もちろん正当性の検証は必要です。今回の場合は、どんな動きをした場合に対しても、最速で動いた後で最後に休憩所で待っているという動きに入れ替えて不都合が生じないことから、大丈夫と分かります。このように、「ある（自分で勝手に決めた）条件を満たす操作に置き換えても問題ないことを示す」というのが、問題を単純化するときの思考パターンの一つとなるかと思います。個人的な感覚としては、問題の単純化は「重要な部分を特定できている場合に他の自由度を捨ててみる」と考えて使うことが多いように感じています（仮に正当でないことが分かった場合には、新たな重要な点が見つかったということなので、それはそれで考察の助けになります）。
さて、すれ違い以外は最速で動き続けることにすると、なぜ待ち時間が生じるのかというと、どちらかが先に 2 度めのすれ違いポイントに到達してしまうからです。すると、その間の両者の移動距離（の差）を考えればよいことが分かり、解説に記したような下界が求まります。
あとは、これを達成できる方法がないかを考えればよいです。このあたりの「まずは下界（上界）を見つけ、それを実際に構築して見せることで最適性を示す」というのは、ある種の ARC 典型と呼べるものかもしれません。
この問題では、すれ違い 2 回の間の時間調整こそが本質と、ここまでの考察で分かっていますので、その片方をスタート地点にしてしまうのが最もシンプルです。ここはやや直感的ですが、本質の問題の前に、最初のすれ違いのための時間調整の問題を追加するのは明らかにめんどくさい、と考えてこの方法に思い至りました。あとは実際に手を動かして確かめてみれば、正当な解法にたどり着くことが出来ます。
■ C. Pivot
この問題では、直感的に gcd っぽいと思った人も一定数いるのではないかと思いますが、一旦その感覚は排除して考察を進めてみます（本番では、そういう直感でショートカットするのはとても大事だと思います）。
まず、よく分からない式で操作が与えられているので、実際に操作を試してみます。すると、この操作が、ある値を選んで反転させる操作であることが分かります。
これを前提として、まずは「簡単に達成できそうな値は何か」を考えてみます。数列の最大値または最小値を選ぶと、その差を d として、ちょうど d ずつ数列の最大値がずれていくことが分かり、d で割った余りによってこの操作だけで達成可能な値が変わってきそう、ということが理解できると思います。
別に最大値を選ぶ操作でなく、a_2 を選ぶ操作を考えてもよいのですが（その場合は間に最小値か最大値での操作を挟まないと永遠に行ったり来たりになるのでやや複雑です）、とにかく「ある種の操作だけで出来ることは何か」を考えてみると、逆に「他の操作で何を達成したらよいのか」が見えてくるのではないかと思います。
d で割った余りを調整する問題としてとらえてみると、あとは例えば a_2 を選んだ時に余りがどう変わるか、はすぐに計算して求めることが可能です。ここでもう一つの問題は、その操作が繰り返し行えるかどうかです。先ほど少し述べたように、単に a_2 を選び続けると、反転を繰り返すばかりなので実質的な意味のある操作になっていません。
ここを、間に最大値を選ぶことでクリアする（d で割った余りを変えずに、同じ操作を繰り返せるようにする）部分は、個人的にはややひらめきを要求しているポイントなのですが、例えば、なぜ繰り返せないか（繰り返しても意味のある操作にならないか）を考えるなどすると、中身が反転しているからだという点に気づくことができそうです。中身の反転は操作 1 回ごとに起きているので、それを元に戻すためには別の値で一回操作すればよく、d で割った余りには影響を与えてほしくないと考えると、最大値で行うのがよい、となります。
ここはある程度天下り的ですが、「こういう操作ができるとしたら解けるが、できないか」と考え、それを実現するための条件からその候補を絞っていくことで、ひらめきが要求される幅を縮めることは可能です。
こういう操作ができるとしたら解ける、の部分、すなわち今回では、余りの調整は（操作が任意回なら）gcd 単位、というのは、どちらかというといわゆる典型に分類されると思います。このような問われ方自体は例が少ないかもしれませんが、例えば、互いに素なら mod 逆元がある、というような数えきれないほど使われている事実の背景を知っていればこの部分はクリアできるはずです。
■ 最後に
試行錯誤を、恐れないでください。特に格上の問題に挑む時には、これまで述べたような手掛かりを使っても、まっすぐに正解にたどり着けない場合の方が多いと思います。しかし、何度間違った道に進んでも、たった一つ正しい道を見つけさえすれば問題を解くことは可能です（そして、多くの問題で別解というものが存在するように、正しい道自体ただ一つではありません）。トライ＆エラーのセンスを磨くことと、無心でそれを繰り返すこと、その両方が何より大切だと思っています。
長くなってしまいましたが、ここまでお読みいただきありがとうございます。
少しでもこの記事がお役に立てれば幸いです。
