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

結果

f:id:tokumini:20190930120028p:plain

 A, Bの2完で94位。レートで見たらとても低い方だと思っていたんだけど、コンテスト前の順位表を見ていたら思っていたよりもドベ付近というわけでもなかったっぽい? まぁそれにしても100位以内は運が良かった(A問題がひねったものだったので普通の実力順とも少し違う結果になった気もする)。

A - Equal Weight

 何も考えずA問題から解き始める。しかしこれが異様に難しい。 A, Bそれぞれから差分が等しくなるようなペアを見つければ良いのかと思い、差分 d 10 ^ 6未満だから全探索できて、 O(\log{N})などで「 N要素の配列の中に差分が dとなるペアがあるか判定」ができればそれを A, Bそれぞれに適用して解けそうだという方向性で考えていた。しかし全然そんなことできそうにないし、だいたい2つ配列があってそれぞれに同じ判定問題を適用して答えを出すというのはあまり解法として美しくないなと感じていた。それなら問題を少し変えて配列一つに対して判定問題を解かせるような形にしていそうだなというAtCoderに対する信頼感。そういうことを考えつつさっぱり解法はわからなかったので、順位表を見て異様に解いた人が多いB問題へ移動。

B - Reachability

 問題文がややこしくて理解するのに時間がかかったが、理解できてしまえばやるだけ。しかし合っていると確信して出したコードがWA。めちゃくちゃ焦りながらデバッグし始めようとしたところ、CLionの環境としてVisual C++を指定していたせいかデバッグモードが使えないことが判明し、急遽Visual Studioに戻るという手間も発生して焦りが最高潮に。普段ほとんどノートパソコンで競技プログラミングをすることがないので環境の整備が全然できていなかった。せめて一日前のABCで確認しておくべきだった……。

 assertを仕込みつつ何度か提出したがどこが間違っているかわからないまま1時間ちょいが経過して、0完を覚悟しだした。死んだ目をしながらコードを眺めていたらzと書くべきところでxと書いているところがあってそこを直したらAC。一つ通せて、まぁ最低限はできたかとかなりホッとした。

 提出

A - Equal Weight

 再びA問題に戻ってくる。が、やっぱりわからなくて特に考察が進む感じもないまま数十分が経過した。残り1時間になったら一度お手洗いに行こうと少し前から決めていて、そこまでさっぱり考察が進まなかったので予定通り席を立った。

 少し歩いて気分を切り替えられたのが功を奏したのか、戻ってすぐに「これ NMが大きい場合と小さい場合で違う解法で解けるんじゃね?」という思考に至る。小さい場合は愚直に O(NM)のループを回せば良いし、大きい場合は鳩ノ巣論法からいってどこかでダブるからそれを利用して解けそうというところに気づくと、300点問題ということも加味してかなり手ごたえがある方針だと感じた。その後も思考が混乱していてやや時間もかかったが、本当に愚直なループを書けば良いだけというところまで考察が進んで上手く解けた。想定解だという自信もあったし気持ちよかった。

 提出

C - Maximize Minimum

 A問題を解いた時点で残り40分を切っていたのでもうこれ以上解けないだろうなとは思ったが、この集中力で問題に取り組める時間も貴重なので次の問題へ。C問題とF問題が同じくらいのAC数だったので、どちらも読むだけ読んで解けそうな可能性を少しだけ感じたこっちへ注力。しかし取り組んでみればどういうものが最適解になるかすらわからなくて完全にお手上げという感じだった。

 後日、解説PDFfuppy0716氏のコードを参考に(ほぼ丸写しで)通してみた。考察の一つ一つやその実装が自分にとって全く不可能な難易度とは思わないが、それらを慎重に繋いでいって全体の解法にまで構成していくのをコンテスト時間中にやるのは相当難しそうだと思う。訓練を重ねていくしかない。

 提出

感想など

  • プラチナスポンサーと謳われているYahooの影が薄かったのはやや気になった。電通の会場提供パワーが強かったのだろうか
  • トークセッションも面白かったが、わりと深刻に就活に対する興味がないなぁというつらい現実を確認する時間でもあった
  • 個人的に講評というものが好きなので簡単な各問講評があったら嬉しかったか。半分以上の問題を読んですらいない人間が講評を求めるのも変な気はするが……(よくわからん問題に対してすごい方法で「こうすると解けます」という話をほえーと思いながら聞くのが好き)
  • 懇親会での食事が豪華で良かった
  • 人々強いし自分ももう少しレート上げたいと思った