天下一プログラマー 第3回予選
日本語なのに問題が読めないとは想定外でした。
- バイトがあったので夜9時頃から参戦。バイト先でのんびりやりました。
- 一通り問題を見てみた。どれもそれほど難しくない感じだ。
Problem 1:
- 1 から 1,000,000 までの整数を17進数で書いたとき、 "g" は何回出てきますか？
- 包除原理？とりあえず愚直なコード書いてから考えよう。
- 書いた。
- 問題を良く見たら、1つの数字に g が複数個あった場合全部数えるらしい。
- 除算と剰余算で出来そうな感じだ。
- 取り急ぎ愚直版修正。
- 何回でもsubmitできるらしいので、とりあえず愚直版をsubmitして次やろう。
Problem 2:
- 文字の載った二次元グリッドが与えられる。この上を正方形を描くように歩いて得られる文字列の中で、回文であるもののうち最長のものを答えよ。
- 全ての点について、右方向の文字列と下方向の文字列が何文字マッチするか調べる。左方向と上方向についても同様に調べる。
- すると正方形の形が決まれば回文になっているかどうかは定数時間で分かる。 O(n^3).
- ...
- 書けた。入念にデバッグしてみる。
- アルゴリズムも評価対象になるらしいので、数十分かけて入念にコメントを書いてみた。
- こんなもんでいいだろ。submit.
- ついでにClarも見てみよう。
- ・・・！
- 「正方形の右上や辺上から始まる文字列も解の候補になる」だと・・・？
- 右上はともかく、辺上は今のアルゴリズムではどうにもならない。書き直し！
- 辺上を許可すると良いアルゴリズムが思い浮かばない。
- O(n^4) で愚直に書くか・・・。
- 書いた。さっきよりも投げやりなコメントも付けた。submit.
Problem 3:
- あからさまな2次元ナップザック問題。
- サイズ的に探索っぽい。けど、残り3分切ってたので諦めました。
- 終わってみればなんともgdgdでした。
- 最近はプログラムを書くときに何も考えてない気がする。
- 明日も朝からバイトなので、とっとと帰って寝ます。
