OBOG合宿を終えて

反省

とりあえずこのOBOG合宿でわかったことは

  1. 本の最後のほうに出てくるようなアルゴリズム問題
  2. 幾何問題
  3. 数学問題

がうちらは弱いってこと。


1.については、さすがに最近は聞いたこともないというようなのは減ってきたけれど、実際に問題に出会ったことがなくて使ったことがないというようなのはまだまだある。最大流量とかはアジア大会には出ないかなとか思ってやってなかったけど、やっぱ解き方わかってるのに実装できないというのは悔しいのでちょっとマジで勉強してみようと思う。


2.については、さすがに幾何問題解くくらいの数学力はあると信じて、ライブラリを整えておきたい。宝ライブラリをもらったのでそれを理解して、自分たちが使えるようにしておこうと思う。


3.については数学力ないのはもう今さら感がただようので、後ろ向きに、数学の公式集を本番もってくことにしたい・・・。
正直あの東大一年の力には勝てる気がしない。なんたってうちらが誰一人解けなかった問題を全員がしっかり計算して解いてるんだから、もう笑うしかない。

探索問題について

逆に今回プラス方面でわかったことは、普通の探索問題、最短経路問題はもうそろそろ普通に解けるということだ。最近良く書いていたのでその成果は出た気がする。

やっぱり自分が探索問題というものを理解したかなと思えるようになったひとつのきっかけはOBOG会の模擬国内予選のKarakuri Dollだった気がする。
一瞬複雑と思えるようなものでも、しっかり状態遷移として意識すればそんな難しくないことがわかってきた。

  1. それぞれの状態を区別するのには何が必要か考えて、それを内部変数として持つクラスを定義する
  2. 初期状態を作る。
  3. 終了状態を考えてその条件を書く。
  4. (枝刈り条件を書く。)
  5. 状態の遷移条件と遷移方法を書く。

といったことをすればどんな問題も解けてしまうということがようやくわかった。stack,queue,priority_queueのどのコンテナでループで回すかを考えればできる。もちろん再帰で書く方法もあるけど。

DP問題でメモ化探索しなきゃいけない時でも、状態遷移が頭に描けていれば、何度も同じ状態にくることがわかるので状態保存が必要なことがわかることが多いので、最初DPだと思わなくても結構いけたりする。まぁDPだって広い意味では枝刈りだろうし。

チームとして

結構一人で間違えずに解く力もついてきたので、時間を有効に使うためにも一人で解く問題を増やしたほうがいいかもしれない。特に、方針が立った問題は、最後までペアプログラミングしていないで途中でnobuに任せようかと思う。
いままでは、これをやるとNoが返ってきた時に悪循環に陥るという恐怖があったが、自分がnobuのコードを読む力が大分ついてきているのでNoくらった瞬間からコード読んでも間違いに気づけるような気がする。


後は、うちらは数学力が必要な問題は捨てて、他の東大、京大チームが果敢に幾何に挑んでいる時にうちらはそんなものには見向きもせずに必死に実装問題を実装するというのが正解な気がする。
実装問題の訓練でもするかなぁ。