Tenka1 Programmer Contest

今回は順位表を見ながらやった。自分にとってはARCと同等のコンテストだけど、企業コンということで心理的ハードルが下がったところにつけこむ。見てもそこから下がる一方なので見たくないんだけど、なんとかして選択肢を増やしていきたい。実際に見る必要があることは少ないだろうけど、自分の動きを自由にしておく。
あと服。コンテスト前に36.7度と微妙な感じだった。寒くないように着ておいて、コンテスト中に体が熱くなってきたら脱ぐ、寒くなってきたら着るという、こう書くと当たり前みたいだけど、そういうのをきっちりやることで、持っている力がちゃんと出せた。面白い問題ばかりだったけど、それを面白いと感じることができた。

C - Align

まず、これの答えを自分が知らないことに驚く。いいところを突いてくる。第一感は、9,1,7,2,6,5みたいなの。だんだん振れ幅が小さくなっていくジグザグ。証明はできないし正しいかもわからないけど、とりあえずこれで書いてみる。違ってる可能性は高いけど、そんなに離れた答えにはならないと思うから書いて損にはならない。するとサンプルが通らない。親切だなと思ったが、今になって考えると、それも思い込みだったなと。さて400点なのだから確かにこんな簡単な答えではないはず。しかし、何も方針が思い浮かばない。順位表を見てもほとんど解かれてないし、めちゃくちゃ難しいのでは?
まあもう少し考えてみる。なぜサンプルが通らなかったのか、具体的に手計算する。すると、サンプル出力は中央値付近の値との差で稼いでいる。なるほど普通に間違ってた。これを1個ローテートするだけでもいいか?ジグザグの幅が大きい順に真ん中から左右に振り分けていくか。実装きつそうだな。しかも、証明ができてない。そもそも差の個数ってO(N^2)あるし隣り合わせにする制約もきついし見当がつかない。ちょっとCの得体が知れないので一旦Dへ行く。
戻ってきた。やはりそれ以外のやり方がより優れているとは思えない。真ん中から配置する実装重いのをやろうとしたが、思ったより重く、またループの1か所を除くイメージで中央値同士の差さえ避ければ全体の和は変わらないと思ったので、最初に書いたコードから1ローテートさせただけのものを提出した。もう時間が時間なのでね。なんとかAC。解説を聞くと、ちゃんと証明できる方法があった。端っこだけ寄与が少なくなるのは、これだけ考えて得た感覚とも一致する。まさかそんな原始的に思える方法が僕の意識の外にあるとは。

D - Crossing

すぐには意味がわからない。よく読むと、各部分集合のサイズはばらばらでいい。条件から空集合はありえないし、kは1以上となる。そのうえで条件を満たしていればいい。さて、1つ目の条件から、k個の部分集合のサイズの和は2Nになる。たとえばNが素数なら、サイズ2の部分集合がN個みたいなやつしかありえないようにも思える。なんかNが大きい数だとして、決まるところから決めてみよう。1,2,3、けっこう制約はきつそうだ。しかし4以上の配置は決まらない。そもそも構成ができない。N=4ができないならN=5でどうだ。星の絵を描き、どうもこれは無理そう。「どの2つの集合をとっても」という条件は、2つの選び方がO(N^2)と多いのでかなりきつい条件になっている。これはN>3では無理なんじゃないか?しかしそんな問題を出すだろうか。さすがにつまらなすぎる。もう少し考える。(もう当時の気持ちは忘れてしまったが)kがNなら絶対無理みたいな雰囲気の。で、証明できたと思った。証明できたなら、これは提出できる。「証明せずに提出したもの勝ち」ではなく「素早く証明できた人が先に提出できる問題」だ。んで提出してWA。
半分くらいWAだったので、構成できる大きいNがたくさんあることがわかる。これは大きなヒントだ。k(k-1)/2=Nならいける可能性があるじゃないか!そして、その場合は(部分集合同士を結ぶ)辺に1からNの番号を振れば構成できる。実装でやや迷うが、考えた通りで押してAC。解説を聞いて、kを先に決めてそこからどのようなNが作れるかという方向が、自分は思いつかなかったもの。きつい条件だと気づいたときの自分の気持ちからはずいぶん遠い場所だ。
証明してから提出するという方針であれを提出してしまったのがつらい。脳みそぐにゃぐにゃすぎて誰からも信用されない人間であることを見せつけられてしまった。

E - Equilateral

図を描いてみる。1つの点から出発して同じ距離を移動しながら戻ってくると考えると、全体の移動距離は2の倍数である必要がある。3点がグリッドに沿った長方形に乗っているとする。1点は角(かど)にある。長方形の周の長さが3の倍数である必要がある。それ以外にはないとして考察を進めた。解説を聞くと、3点をx座標順に並べた場合のy座標の変化で場合分けすると、それ以外ないとわかる。すごい。
角にある1点と残りの2点、どっちを基準に考えるか。1点から見ると残りの2点のパターンは多すぎて散らばりすぎてダメに思える。2点から見るのは(コインの数をNとして)O(N^2)かかるのでダメっぽ。なんかうまいこと重なるんじゃないかと色々考えたが。長方形を横に伸ばしたときの振る舞い。なんか2点が1とか2とか動く。縦にも伸ばさんといかんしまとめられる気がしない。
解説を聞くと、2点が45度の位置関係(雑な表現だな)にあるらしい。ああ、なぜそんな基本的なことに気づかなかった!長方形ぐるぐるのイメージから、更に踏み込んで具体的に考えるべきだったなあ。そういう距離が入ってるんだから円を描いてみろよとも思うが、それを思いつかずとも具体的な座標を計算することで45度に気づくほうが大事な気がする。やっても気づかない可能性が高いとは思うが。そして実装が自分の実力だときつそう。今からやってどれだけかかるだろう。ていうか計算量がO(max(H,W)^3)みたいな微妙なラインなので、いやそんな雰囲気は感じてたんだけど、見えないよなあ。ほんと作問者が天才すぎる。