パソコン甲子園2019予選で悪魔に襲われた話
問題1,2,3,4,5の5完(1ペナ)でした。ペナルティを避けるために、提出は後半にまとめてやる戦法で挑んだ。
問題1 柴犬の数
4つの数値が与えられるので、その和を返す。これは相方が解いた。
問題2 アスキー文字
タイトルだけ見たらびっくりするが、要するにif文による場合分け。これも相方に解いてもらった。
問題3 ２の累乗
N以下のうち最大の2の累乗を返す。2の累乗を計算していって、Nを超えるまでループを回せばよい。これも相方がさらさらっと書いてくれた。
問題4 集会所
数直線上に家が建っていて、全員が最も早く集まれる位置に集会所を設置し、そのときかかる最大の時間を出力する問題。制約がN≦1000で、座標の最大値が2000までなので、集会所をどこに置くか全探索して最適解を探す。
と思っていたが、相方が組んだプログラムでは座標の最小値と最大値の差の平均を出力していて賢いなーと思った(小並感)
問題5 ねこのあな
しっかり対策してきていれば、「ねこのあな」がいわゆる「スタック」と同じ機能を持っていることがすぐにわかるだろう。実際にシュミレーションし、既に入った猫が再び入っていないか、出られる猫と記録が一致しているか、をチェックすればよい。ここまでの問題を相方に書いてもらい、それ以降の問題を僕が実装した。
はずだった…
問題6 床
相方が問題5まで解いている間、僕は問題6以降の解法を考えていた。
問題6は、3種類に色分けされた正方形のタイルを反時計回りに設置していくとき、与えられた地点のタイルは何色か返す問題。座標の制約が10^6までなので、当然タイルの状態を事前に計算して2次元配列に保存していては間に合わない。
ここで、タイルの辺の長さに注目するとフィボナッチ数列となっていることに気付く。そこで、フィボナッチ数列をある程度の大きさまで計算しておく。そのあと、一度y軸方向への移動を無視してx軸方向への移動のみを考えたとき、中心から何番目のタイルに到達するか計算し、さらにy軸方向への移動を考えて最終的に何番目のタイルに到達したか求める。ここまでくれば、タイルの番号を3で割って調節すれば答えが求まる。
…嘘つきました。求まりませんでした。(予選終了後に考察したら解けました*1 )
いざ実装してみるとわかるが、条件分岐や区間の境界の処理など気を使うことが多すぎて、実装をバグらせてしまった。30分ほど格闘した結果、この問題は一度飛ばしたほうが良いという判断に。
問題7 アカベコ20
N人いる各メンバーには「周期」という数値が与えられており、メンバーはその周期ごとに公演に参加する。このとき公演に参加するメンバーの組み合わせ数を計算せよ、という問題。
制約がN≦20と異様に小さいことに気付き、各メンバーが参加する・しないという2^N通りの組み合わせをbit全探索を用いて全探索する方針に。すぐさまbit全探索を書く。しかし、全探索した後に何をするべきかがわからなかった。今思い返せば、しっかり考察してから実装するべきだった。何を当たり前のことを
このあたりから、チーム内に不穏な空気が漂い始める。この時点で、残り時間は40分。確かな焦りが自分を襲っていた。
問題8 矢印
左右どちらかを向いた駒が一直線上に配置されている。駒が向いている方向に駒を進めると＋１点、反対方向に進めるとー１点となるとき、獲得できる点数を最大化する問題。
ここで自分の不調の原因が判明する。お昼ご飯をまともに食べていなかったのだ。脳に栄養が回らず、普段ならできるはずの考察すらせず実装に移るというアホムーブをかましてしまったのもこの、空腹のせいだと感じる。良いこのみんなはご飯をいっぱい食べようね。
この問題の考察でも、空腹の悪魔はイタズラをしかけてきた。
『全部の駒を左端か右端に寄せればいいんじゃね？』
頭が回っていない僕には、その言葉は神のささやきにも感じ取られた。脳死で実装する。もちろん間違っている、いわゆる嘘解法である。5秒考えれば、入力例1の時点で矛盾していることに気付けたはずだ。このとき僕は軽くパニックになっていた。何故通らない…！
提出
ここで、ためていたソースコードを提出することに。問題1~5までのソースを提出してしばらく待つと、問題4だけ「不正解」の文字が浮かぶ。あれ？
チェックしてみると、最大値・最小値を持つための変数を初期化していなかった。書いたのは確かに相方だが、最終チェックをして「ヨシ！」と言ったのは僕だ。ここでも空腹が効いていた。すぐさま修正して提出する。正解。この時点で残り時間は20分ほどだった。
問題9 天空の城ツルガ
ここからの問題は解けていないので、予選中の考察をそのまま載せておく。
天空の城ツルガが作り出す影は、太陽の高さとツルガの高さから地上に投影可能である。あとは「与えられた座標が多角形に含まれるか」というクエリを高速に処理するだけだが…その方法は分からなかった。この問題は無理だと判断し捨てる。
問題10 トーナメントの記録
トーナメントの記録が矛盾しないように並び替える方法は何通りあるか求める問題。敗者はそれ以降の対戦記録に登場しないこと、敗者の中にいない人物が唯一の優勝者であることを考えると、優勝者が勝者となっている記録を数え、そのうちの一つを最後の記録とし、その記録の敗者が勝者となっている記録を数え…とやっていけばうまくいきそうだと感じた。感じただけなので実装はしなかった。
問題11 イワシロの祈り
全くわからなかった。接尾辞配列を使いそうだと思ったけど書き換えるクエリの処理方法がよくわからず、パス。
問題12 ダンジョン3
タイトルしか読んでいない。ダンジョン好きすぎだろ。
終了
いろいろと終わった。最終結果としては、相方が5完1ペナ、僕が0完だった。
ご飯はしっかり食べようね！0完お兄さんとの約束だぞ！！
