AtCoder ARC 042 B - アリの高橋くんをテーマに弊社エンジニアで対談会

irisruneです。ようやく対談会を記事にまとめることができました。

コードがなかったりいつもとスタイルが違いますが、お付き合いいただければと思います。

問題

atcoder.jp

登場人物紹介

筆者I:irisrune

エンジニアA:AtCoderはやったことはないが周りにやっている人がいた。また、Project Eulerで問題を解いていたことがある。

エンジニアB:一時期AtCoderをやっていたが、茶色になって以降数か月AtCoderをやっていない。

対談記録

A:なるほど。問題はわかりました。

B:これABCですか？…ARCですか、なるほど。

A:とにかく垂線を下ろせれば終わりって話ですね。配点は何点でしょうか。

I:この時期の問題は難易度で分けられていなかったので、全部100点の配点です。

A:これって数学の知識あればいけますか？

I:中学校～高校くらいの数学の知識ですかね。¹

A:三角関数使えれば楽そうですが。

I:三角関数は使いますかね？解説を見ると大学レベルの知識が必要かも…ですが垂線を下ろすのがお手軽だとおもいます。²

A:なんで垂線がお手軽なんだろう…

B:うーん、今回のゴールは僕が理解できることですね（笑）

I:いくらでもネット検索とか使って大丈夫ですよ（笑）

B:そうか、最短だからどうやっても垂線になるのか。これが5角形、6角形になると…中学校の数学の知識が危うくなってきましたね。辺の数が頂点の数だけある、そこから垂線を引くことをすべての辺について試していくと。

A:例えば、三角形を考えて…

I:（ググって垂線の長さの解説や、『点と直線の距離』の公式を出す）

A:2点から直線を求める公式をググればいいんですかね。あ、三角形の垂線の長さを求めてもいいですよね。すべての辺の長さがわかっている状態ならなんとか行ける気がするんで。

B:どんな多角形でも辺はある1点と1点の2点の間にあって、高橋君がいるのはどこかの辺の間の1点で、それを繋ぐとどうやったって三角形になる？

I:それはその通りです。ただ、三角形だと逆に難しくないですか？実装はともかく発想は点と直線の方が楽だと思います。³

B:頂点の中から一番近い頂点の直線で行くということ？

I:別に全部の辺を使ってもいいですよね。

A:これ、多い場合に抑える工夫はありますか？例えばかなり $N$ がでかいときとか…

I:ぶっちゃけないですね。どうやっても全探索になるし、どうやっても $N$ になる。

A:どの垂線が短いかという判断がつかないですよね？

I:そうですね、その判断は相当難しいですね。

B: $2N$ になりますか？

I:普通に $N$ ですね。

B:まずどうやっても、全部の点と頂点の距離を求めていくことにはなりますか。

A:そうですね。あ、ヘロンの公式っていうのがありますよ。3辺の長さがわかれば面積を求められるという。面積を2倍して、各辺の長さで割ってあげれば出る！

B:ヘロンの公式！なんかやったなあ。⁴

A:数学者って本当こういうの好きだよなあ（笑）

B:三角形があるとして、1番近い点と2番目に近い点を算出して…この2点を出して、点が結んでいる線に対して垂線を下ろす、という風にするとダメですかね？

I:うーん、まあダメですね。ダメな理由は、「近い頂点」というのがかなり危険ですね。遠い頂点でも簡単にギリギリのところに通せるので。

f:id:amifiable:20190531114341p:plain — 即興で作った例

A:では3辺の長さの比率が大事になる？角度は出せますよね？頂点の距離で考えるのであればですけど。頂点で考えるのは厳しいですね。

I:頂点を使うのならば、ヘロンの公式ですね。

A:やはり点と直線の距離ですかね。

I:点と直線の距離は、えげつないことを言いますと、3点があれば求められるという公式がググれば出てくるんですよね。ヘロンの公式を使った結果を展開しても同じになりますね。

B:標準入力だとだめですね…配列で受け取れない。Javaなら行けそうですけど。

I:（Pythonの）標準入力見てみましょうか。でもPython書くとなるとわからないので、書くならGoですね。⁵

A:公式に従ってやっていけばいいだけですよね。あれ、この問題ってインプットは何ですか？順番に点って与えられてるんですか？

I:（条件の部分を見せる）⁶

A:多角形が保証されていないと大変ですけど、それならいいですね。

B:保証されていないとどうなるんですか？

A:要は、頂点がランダムで与えられたときに構成される多角形って…

f:id:amifiable:20190531114414p:plain — 数字の順番に点が与えられたときのイメージ

A:どの点とどの点の間の辺なのかというのを特定しなければいけなくなると。

I:解こうと思えば解けますけど、難易度がかなり上がりますね。ARCでB（ABCでD）でもおかしくなくなるかな。今の状態だと300点あるか怪しいのが、400点くらいにはなりそうですね。

A:これってどのくらいの時間で解くんですか？

I:目指すレート帯にもよりますね。10分くらいで解ければ1200は目指せるでしょうか。

A:調べながらで、入出力がわかっていればまずまずいける範囲だと。

I:他の人の解答を見てみましょう。

A:まあそうなりますよね。あとは言語によって癖ありますよね。

B:やるべきことは何かを的確に見抜けること、その数式を実装できることが求められる。算数ができるかということですかね。

I:算数できなくても、調べる力があるというのが大事ですね。点と直線の公式というのを覚えていないと調べようがないかもしれませんが。

A:点と直線という単語を使わなくても、垂線を下ろすというのがわかればいけそうですね。実装自体はそんなに難しくないですね。

I:サンプルで試せば間違いは出てくるので、数式打ち間違えてもわかりますね。許容の誤差もありますし。

A:ルート取って割り算するだけだから、誤差も出ないですよね。2点間の距離があまりにも小さいとやばいかもしれない？

I:その場合も、相対誤差でいけるのでは。さっき答え見ちゃいましたけど、公式の解説も見てみましょうか。急に回転し始めましたね。（笑）

A:回転って、ローテーションめんどくさいイメージしかないですけど。

I:確かに普通にめんどい。平行移動まですると明らかに難易度跳ね上がってますよね。

A:嘘だろー、難しくなってるけど大丈夫か？

I:複素平面を用いると回転が楽になると。これは大学の知識ですね。解説が妙に難しいですね。

A:初見でこれ思いつく人って相当ですよ。問題に対してオーバースキルでは？でも計算量が抑えられるんですかね。

I:計算量は変わらないけど、記述量は抑えられますね。Rubyで複素平面を使った解答なんかはかなり短いですね。速さはあまり変わらなさそう。この問題についてはこんなところですかね。

A:ポイントは垂線を下ろすということに気付くかどうか。

I:全部の辺に対してというところ、全探索に気付くかどうか。あと最後の条件（凸多角形が保証される）は見落としても凹多角形でもいいかも…？⁷

（各人の感想）

A:細かい条件がわかっていないと解けるものも解けなくなるということ実感しました。あとなんだかんだ数学の知識がないと大変な時もあるのかなと。

B:競プロを解くって、（プログラミング知識があっても）競プロの脳みそにもっていくのが難しいなと。普段全く使わない方向に脳みそのベクトルを持っていかなくてはいけないのが辛い。楽しいといえば楽しいけど。自分も茶色に行くまでには6ヶ月かかったんで、何も考えてないない人間がやろうとするとそのくらいかかりますね。

I:今回アルゴリズムは難しくないものを議題に選んだので、早めに終わるかと思いましたが、考察詰めていくと結構時間がかかるなと思いました。⁸思い付きで走りがちなんですが、話し合うと注目するポイントも多いんだなという感想です。

A:慣れてくれば情報の取捨選択が速くなりますね。

I:逆に条件を見落とすこともありますけどね。例えば制約として $N=10^5$ が多いんですが、この問題は $N=10$ だから色々なやり方ができる。 $N=10$ だと、 $2^{10}$ もいけますし、（言語や処理内容によっては） $10^8$ とかもいけますね。