部内コンテストのアルゴリズム

参加者は結構二分探索を使ったプログラムを書いてるんで、MAX=10000の場合は俺のプログラムではもう負けつつあるんだけどMAX=1000の場合の40という数字はなかなか難しいようだ。
まぁ授業でやったときはMAX=1000で学科トップ*1で、担当教官にも「本当に意外なほど単純なプログラム」とまで言われたから、発想だけでいえばなかなか良いもんなんだろう。
まぁプログラムはコンテストが終わってから公開するとして、考え方としては嘘をつかれた場合の影響と探索の冗長さをいかに小さくするかということに主眼をおいている。
二分探索だと探索幅は等比級数的に変化するからじゃあ加算的な方法でということで等差級数的な収束をするのを、ということで動かしてみたら、それまで100を切れなかったのが一気に60切るくらいまで行った、と。
授業の課題のときは末項(この場合初項か)は完全に経験則からMAX=1000に最適化した定数だったけど、今回はMAXと嘘率の値からそこそこ無難な数を計算で決定している。

余談だが今日の授業中に組んでたプログラムは、長さMAXの配列を使うというものすごくアレゲなもので、授業の最後に完成して実行したら見事にアルゴリズム的な無限ループにハマって一瞬でYou Loseになりましたとさ(ぉ
明日は二分探索と等差級数を素直に切り替えるようなのを書いてみよう。

しかし単純だけど意外に奥が深いゲームだなぁ。

*1:非公式には2位だったんだが