競技プログラムというとアルゴリズムである。アルゴリズムの基本と言えば二分探索だ。何事も基礎からコツコツと、というのは一般論ではあるが、二分探索は並んだ列が左の方が小さく右の方が大きい場合にど真ん中を取ってみて、それより小さければ左半分を取ってその真ん中、大きければ右半分を取ってその真ん中を取るのである。
このアルゴリズムを大人になってからの勉強に割り当てると、まず真ん中を探さなくてはいけない。何がどの真ん中なのか。とりあえずAtCoderのランクの中で真ん中くらいの問題を解いてみた。サッパリ解けん。
1週間前に長期試験に参加をして、そして週末には並行してアルゴリズムの試験も受けた。そうすると、長期試験の方がレートは高いが、参加者が少ないからだと思われるのと、アルゴリズム試験では最初の問題でつまずいてレートが8万位台であることが分かった。
それでも、用意されたプログラムの実習は簡単すぎる。アルゴリズム過去問の100点問題を解いてみて、200点問題で詰まるということが1週間かかって分かったのだ。
それで今朝はアルゴリズムの200点問題に取り掛かり、午前丸々使って解いたのであった。道中、まずPythonの文法からコンパイルエラーに戻り値エラーなどのトライエンドエラーを繰り返し、そうしてついに答えが出そうだと思ったら、送信したソースコードがサーバーで長時間処理されて時間オーバーとなった。
タバコを吸った。
そう、アルゴリズムというのは同じ問題をより早く解くための手法だといえる。俺はクソコードと言われながらも少なくともコンパイラを通して問題を解いてきたのだ。ただ、その方法において総当たり的であるがために計算機をよりハイスペックにして、電気代を使って、時間もかけて問題に当たってきた。
ああ、ここがまさにアルゴリズムなるものの効果が発揮される局面、そういうことを試す問題集なのだなと思った。
そう考えると、どんどんプログラムしてデバッグするのではなく、しばし考える。
もっと簡単に解く手はないか。結果、二重のループをひとつのループで解いてしまう方法が浮かんだ。問題のタイトルにもヒントがあった。
結果、見事に200点を獲得したのであった。そうすると、200点問題をもういくつか解いてみると400点問題になり800点問題になり1600点まで3ステップ。レート2から1999はえらく遠く感じていたが、もう1週くらい頑張ってみて、あらためて距離を確かめようと思った。
