UTPC2009 参戦記【ラノベ部祭り】

http://www.utpc.jp/2009/

10080 ねこかわいがり

やるだけです。

10081 平安京ウォーキング

定番です。

10082 カードゲーム

next_permutationは偉大です。

10083 単位変換器

しねばいいのに やるだけです。




主に単位変換器でむだに時間をくってしまいました。（1時間経過、4完）。
で、ここで諸事情により1時間ほど離脱しました。（2時間経過、変わらず4完）

この段階で、トップとは2完差がついていたような気がします。

10084 足し算ゲーム

いかなる戦略をとっても結果が変わらないことに気づくだけです。読んでから10分かかりませんでした。速攻。


自分は、こういうゲームっぽい問題が、他のジャンルにくらべてわりあい得意な気がします。

10085 天使の階段

逆から辿ると、最後の1音を除いて分岐せずに戻れることに気づくだけです。


……が、なぜか逆から辿っても分岐しまくって解けないという結論に至ってしまい、ためしにかなり怪しいアルゴリズムを2回ほど投げてTLEをくらいました。そして、諦めていったん飛ばしました。


いちど証明できたと思い込んでしまったことを、後から覆すのはたいへん難しいです。思い込みの魔力。
今日一番の反省点です。

10086 挨拶の多い本屋さん

Y秒硬直をX/Yターン休みに変換して、あとは実際にシミュレーションしました。


無限ループの判定でちょっとつまりましたが、「Nターン後がうるさかったら無限ループ」で（TLEもせずに）いける気がしたので、ためしに投げてみたら、通りました。


証明が適当でも、通れば正義です。




で、G以前とH以降では明らかに難易度に差がありそうだったので、ここで天使の階段に戻りました。

10085 天使の階段

ようやく過ちに気づいて通します。
わりとスムーズに解き進めているようでいて、その実この段階で4時間も経過しています。遅いです。




ここでいったん落ち着いて、残る5問に目を通します。

10087 あみだくじ

涼宮ハルヒの陰謀 (角川スニーカー文庫)

↑を読んでいれば誰だって思いつく問題設定です。
当然、ラノベ部兼作問部である自分がこの設定を考えたことがないはずがないのです。


ないのですが。


http://d.hatena.ne.jp/jellies/20070611


どうみてもオーダーが1段階下です。本当にありがとうございました。

10088 夏への扉

夏への扉 (ハヤカワ文庫 SF (345))

ラノベ部的に、大好きな問題です。
中途半端なパロディ（適当に原作をもじったタイトルをつけただけ、とか、登場人物の名前が同じだけ、とか）は嫌いな自分ですが、これは原作設定をうまく取り入れた良問だと思います。


12問中ゆいいつ、猫設定であることが自然な問題。さすがは猫小説です。


ちなみに、夏への扉を開けたとしても外は冬であることを知っていると、レノン君のためにわざわざ問題を解いてあげる気が失せてきます。
原作を知っていることが、マイナスにはたらく珍しい例です。

10089 ねこ泥棒と金曜日のお屋敷

n=14なので、O(n^2 * 2^n)でセールスマンする問題なのでしょう。たぶん。
見即捨。

10090 Cat Numbers!

数学科しか解いていませんでした。
即捨。

10091 シャノワール

狼と香辛料 (電撃文庫)

H×Wマスの正方グリッドであらわされる麦畑がある。各マスには、麦が実っているor何も実っていない。
豊作の神であるあなたは、麦に宿って移動する。1ターンに1度、上下左右の麦のあるマスに移動できる。
一方、この畑の持ち主は、麦に宿った神を見分ける不思議な力を持っている。1ターンに1度、任意のマスの麦を刈り取ることで、豊作の神を自分の畑に閉じ込めておきたいと思っている。ただし、この村には、豊作の神が現在宿っているマスの麦を刈ってしまうと、狼に乗り移られてしまうという伝説があるため、それは避けたい。
おたがい交互に最善手をつくすとき、畑の外まで逃げられるかどうかを判定せよ。


↑という設定を考えたことは、まあ当然のごとくあるわけですが、まあ当然のごとく最終防衛ラインになるような問題を自分が解けるわけがなく。


とはいえ、一度考えて分からなかった経験がある問題なので、今ちょっと考えたところで分からないだろうという推測はできます。その意味では、ラノベ部の経験が役に立ったといえるかもしれません。




というわけで、残る5問のうちどれを解くかという問題は、谷川流、ロバート・A・ハインライン、支倉凍砂（敬称略）のうち、誰を一番愛しているかという問題に帰着されました。


たいしたSF読みではない自分は、ハインラインの作品なんて数本しか読んだことがないので論外です。一方、残りの2人の作品はちゃんと全部読んでいるので、最低限の必要条件はみたします。
とはいえ、葉隠 支倉先生の作品（1シリーズしかないけど）は、イマイチ自分とはそりが合わないので却下です。


というわけで必然、残る時間はあみだくじに費やされることになりました。






まあ、結局解けませんでしたけどね！


最終結果：7完（順位不明）