年も明けるというので、思いにふけって沖縄オンサイトの問題について思いを馳せます。もはや参加記のようなもので、問題の解法の助けにはならないと思いますが、問題を作るにいたった経緯とかコンテストの舞台裏みたいなことが書けたらいいと思います。
全体的な
沖縄オンサイトは参加権もあり、もし行けるなら参加するかもしれなかったのですが(とはいっても、あんまり乗り気ではなかった)、試験があったので悩む必要もなく堂々と棄権できました。棄権したのでwriter(全問！)をやりました。
実は問題は2月のSRMに出して以来全く放出する場がなく、今年生産されていた問題がいくつかたまって来ていたので、ここぞとばかりに放出してみました。ここぞとばかりに放出したら3時間では足りないようなボリュームになっていました。いやー、難度バランス調整は難しいですね。
ただ沖縄そばは食べたかったなぁ……。
今回の問題セットは問題名の頭文字がAから順になっています。
各問題の背景とか、感想とか
もう書くの飽きたので適当に書きます。詳しく聞きたい人はTwitterや会ったときに直接聞くなどしてください。
A: Automatic Map Generator
沖縄っぽい問題を出そうと思ったんですが、僕は市町村ジグソーパズルみたいなのをやるのが好きなので、真っ先に離島に目が行きました。
これをどうやって問題にしようかなと思った結果、地図を作るということにしてみました。
完全に沖縄ですね。
A問題で構成(自明ではあるけれど)ゲーを出す、というのは面白そうなので良かったと思います。
B: Beware of the Sogginess!
ここにも沖縄そばの食べたさが現れていますね。麺を伸ばすことについてなんですが、カップ麺の「5分」と書かれているところを30分くらい待ってみると、量も増えるしスープも染みるし温度もちょうど良くなる(暖かい季節の場合)のでおすすめです。時々やってみてください。
このDPは意外と難しかったそうです。確かにBに置いたのに捻ってしまった。
C: Cat versus Wolf
結構苦し紛れタイトルですね。でもゲームだしCat vs Wolfではあります。
ジェンガでだるま落としをする、もうめちゃくちゃです。
一見この問題の入力は厄介そうに見えるのですが、実はa[i][i]が'#'か'.'かを判定するだけでよくて、偶数段目、奇数段目で場合分けする必要はありません。
解説ではad-hocな構成をしましたが、これがNimであることには解いてる人を見て気がつきました！
D: Dictionary for Shiritori Game
Eより難しいと思っていたのですが、他の人がEは難しいと言ってたのと、問題名の都合で、これはDに置きました。
(これをARCのD、EをARCのCと提案して送っていました)
ゴールから考えていこうとしてBFSとなっておしまい、と思っていたけどDFSをしてしまって落ちるとかもあったそうです。
あとこれは後退解析という名前がついているらしいです。はぁ
E: Enormous XOR Rectangle
お気に入りです。しかも好評でうれしいです。でもほとんどの通した人は実験結果を眺めて貼って終了みたいな感じなのが悲しいです。
XORについていろいろ考えていたころに思いついた問題なので、SRM644のMediumと大体同じ時期にできています。644のMediumはArchiveにはないので、Arenaから探してみてください。
F: Falconry
これは確か問題を10問そろえる過程で一番最後にできた問題です。3って怪しくないですか。怪しいでしょ？って考えさせて嵌らせようとしたら、O(3^n)で通ってしまいましたというか、O(2^n n^2)がめちゃくちゃ遅かったのでどうしようもない。
カザフスタンに行くとイヌワシ(でかい！)を使って狩りをするのが伝統らしくて、そういう感じのなんらかを見ることができます。
というか普通にこれは問題名ドリブンです。
G: Gorgeous Vases
カタラン数の折り返して数えるやつを2本にすると、こうも複雑になります。(なりました)
今回のコンテストで一番難しい問題といわれていますが、確かに自分も2回ほど嘘解法にたどり着いています。
こういう数え上げ問題(非DP非データ構造で答えの数が指数オーダー)がお気に入りのタイプなので、皆さんもどうか作ってくださいお願いします。
H: Happy 2015
この問題名、明らかに強引なんですが、というかもう2016年なんですが、タイトルの元になった問題は何だか分かりますか？
そうです、2773 -- Happy 2006です。問題の中身全く違います。
問題そのものはDPの数え上げなので、多くの競技プログラマーにはなじみが深いし僕の大好きなジャンルの数え上げではないので、まあGより普通ですね。解いてる人も多めです。
そういえばこれは座標が整数だけだと思っている人が多かったです。
I: Implementation Addict
この問題文のWolf Sotheって登場人物、AOJを毎日のように埋めていくtozangezanって人に似ていませんか？
実体験をもとにした問題です。連日問題を解いているとだんだん気力が尽きてきて解ける問題が減ってくるので、そこで1日休みを入れるみたいなことを僕もやっています。
肝心の解法のほうはあんまり面白くないですね……。整数の3分探索は終了条件周りがかなり複雑なので、ある程度狭くなったらそのあたりを全部見るのがいいと思います。少なくともこういう計算量が余裕な場合は。(そもそもちゃんと3分探索ができることも調べる必要がありますが。)
J: Jungle
最初は「スーパーでうなぎが売られているので、値引きシールを貼る」みたいな設定で明らかに不自然というか、Cat Snukeがスーパーの営業妨害をしているような感じのストーリーにしかなりませんでした。
この問題は正解者は居なかったのですが、後から聞いてみるとバンバン簡単な解法は出てくるわ、EやFより簡単と言う人が現れるわ、人々こういう問題得意なんですね。感心しました。
まとめ
今年もよろしくお願いします。後で目標を書いた記事を投稿するかもしれません。
