会津大学競技プログラミング合宿2013 Day 3
3日目の作問を @k_operafan さんとしたのでメモ。
主に自分の作問について。
解説は無いのであしからず…。
自分が作った問題の解説を挙げました。
https://www.dropbox.com/sh/ingo41xpnd6fuoi/5-8HaPoOhK/aizu_camp_2013
全く推敲していませんので、多分適当に更新します。
（最終更新 2013/09/21 23:10）
作問にあたって
とりあえず、今までに思いついた問題アイデアから面白そうな問題を見繕っていった。
ICPC WF中に思いついた問題が多め。
目標は、「問題がシンプル」（細かい設定が不要）とか「変な問題にする」とか。
結果、自分の問題は解法がAd-hocなものが増えた。
というか、冷静に見ると、後半は全部Ad-hocに見える。
F、G、J、Lは結構気に入っていて、1チーム以上が通してくれたので満足。
（Jはあるある問題なのでそこまででもない）
あと、幾何は苦手なので、難しそうに見えて簡単な問題がいいなあと思っていた。
ストーリーと問題文を分けたのは、分かりやすいストーリー入りの問題文を作るのが難しかったから。
ストーリーはかなり破天荒なものにして、問題文はかなりドライな（必要最低限）文章になるようにした。
ストーリーは見なかったことにして下さい。
ストーリーは見なかったことにして下さい。
ストーリーは見なかったことにして下さい。
コンテスト中
序盤は問題が簡単なので、物凄いスピードでACを重ねられていった。
オンサイトでは全チーム3AC以上していた（はず）。
あんまり風船が少ないと寂しいのでこうなってくれてよかった。
とはいえ、開始1時間で4~6問ACしたチームが多く出たため、結構不安になる。
だが、そこから難しい問題になるため、思惑通り、提出のスピードが遅くなる。
また、Fからは問題を解く順番がバラバラになり、どの問題に手を付けるかが重要に。
Standingsがちょっと傾くとそこにドカッとなだれ込んでいたので面白かった。
オンサイトではmiterudakeとEviField162がかなりの接戦だった。
Clarは1回だけしか来なかった。
しおたさんの視線を感じた。
対応も易しいものだったので、問題の意図が誤解無く伝わっていれば幸いである。
終了20分前、L問題がついにfacepalmpartyによってACされ、誰も解いていない問題が無くなる。
これは全完が出るのでは、と思ったが出なかった。
最後の最後では「通れ通れ」といわんばかりに、沢山の提出が来た。
主にJ・K。
が、しかしACは無かった。
1位は2位に差をつけ11完。
（別に全完を出したくないわけじゃないけど）辛うじてI問題で足止めを食らわすことが出来た。
以下、自分が作問した問題の振り返り。
B: Time Complexity
簡単な問題が少なかったので即興で考えた問題。
多項式が文字列で与えられる、といっても、"n^k"を"+"でつないだだけなので、構文解析は物凄く簡単。
整数型でのオーバーフローが相次いでいたので、サンプルをもう少し丁寧にするべきだったと反省。
「logは定数のようなもの」とかあるが、FはO(NlogN)でTLEする（はず）。
D: Change
ICPC WFにて空港で両替した時に何故か両替結果が色々と違っていたのでそこに着想を得た。
最初は100*100ループだったが、証明を頑張ると数式1つで出るのが面白かった。
（しかも多くの人がそれだったので凄く驚いた。）
ただ、そのせいで問題としてはあんまり面白く無いかも。
数式がややこしいだけで、結局解答は短いのだが、苦戦する人は相当苦戦していた。
これもサンプルを沢山入れるべきだった。
DarseinさんがFAを決めていてプライドを感じた。
E: Pie Chart is as easy as pie.
円グラフには沢山の（闇）テクニックがあるので、そこから考えた。
（ちょっと遅れた）時事ネタ。
自分の解法は、飛び出たり凹んだりするケースをccwで場合分けするものだったが、
符号付き三角形で鮮やかに解くコードをk_operafanさんが書いていたので驚愕。
Jで出てくるグラフはCircle graphと呼ばれるけど、パイチャートも円グラフと呼ぶ。
F: MLE
空間計算量はあんまり出てこないので、空間計算量がネックになる問題を作りたかった。
つまり、ストリームアルゴリズムのようなもの。
最初は求めるものを他の指標にしていたが、中々うまいものがみつからなかったので、順序統計量にした。
入力もどうしようかと長いこと考えていたが、標準入力だとそれだけでTLEするので、乱数生成器をコードで与えることにした。
Xorshift 64はシンプルで速いので、これだ、と思った。
結局、MLEを防ぐためにはTLEとの戦いになる。
10^8なのにTL 2秒なのは、logつけたら弾かれて欲しかったから。
大体がバケットに分割していたが、様々な工夫が見れて面白かった。
コーナーケースのせいもあって、WA、TLE、MLE、REと沢山のエラーが出た問題になった。
komiyaさんと被っていた。（実は他の方とも…）
以下climpetさんからの指摘。
G: Get Lost
ロシアの街並みや地図を見て迷子になったら死ぬなあと思ってそこから考えた。
逆から考えたところがいくらかあったみたいだが、想定解法はシミュレーション。
最初は自分も座標毎にDPのようなことをしようと思っていたが、調べる座標が物凄く小さいことに気づいてマップのサイズを大きくした。
これで座標圧縮を事実上封じたことに。
4方向を開始方向にしなければいけないが、マップ全体を回転させているところもあった。
精確に実装すればACする（TLEしない）ので、提出が沢山来るんじゃないかと思ったけど、提出数は思いの外低かった。
実装がLの次に重い位なので、そのせいかなあ。
AC率は後半の問題では高め。
残り時間と実装方針が大事かな？
J: Avant-garde Art
Cycle graphを調べようとして、間違えてCircle graphとググったら発見した問題。
Wikipediaの最大クリークの項（英語版）に実は載っている。
さらに、そのまんまの論文があり、知っている人にとっては一瞬なので、どうなるかなあと思った。
kはブラフだけど、20以下制限のせいで一瞬ひよるかもしれない。
逆に丸腰で解ける人はすごいと思う。
自分には無理。
後半の問題では思った以上に提出が多く、他の問題が分からなかった人はこの問題に流れ込んでいた。
Standingsの流れかなあ。とおもったが、皆すぐにLISに帰着していて驚いた。
実装は超簡単なので、最後の最後まで挑戦していたチームも。
計算時間はN^2logNだけど、Nはn/2なので、8000^2×logはヤバくね？と思ったチームや、"n/2-c"を"n-c"と書いてWAしていたチームがあった。これは予想外。
Intersection graphは他にも沢山あるので色々と調べたい。
実は、N^3位の計算時間でも通せる。
どうするかというと、分割する位置をシャッフルする。
もし、最大クリークのサイズがそれなりに大きいなら、適当に調べても高確率で最大クリークが出てくる。
逆に最大クリークが小さい場合には、全体的にグラフは「疎」になる。
だから、LISの計算がかなり速くなる。
時間制限まで頑張った後に、頑張った結果を出力すれば、大体通る。
このせいで、今まで出されなかったのかなあ…。
L: The Return of FizzBuzz
去年のJAG合宿で自分が考案した"FizzBuzz"を逆にした問題。
問題文もほとんどそれからパクっているので「何か見たことある」という会話でニヨニヨしていた。
一応似た問題があることは知っていたが、mod 15のお陰でコーナーケースだらけになったので、出題することに。
作問中、仮の想定解法が全探索により撃墜されて驚いた。このケースは中々思いつかない。
多くのチームは敬遠していたっぽい。
サンプルの最後2つが結構やばさをかもしだしていたからかしら。
コンテスト中は、初提出がWAだったので、想定解が間違っているのでは無いかと物凄く焦ってジャッジ解と比較していた。
最終的に挑戦したのは1チームだけで、7回のWAの後ACだった（終了20分前）。
そのチームは11完1位だったので、1位チームを足止めさせるにはそこそこ頑張ったかなあと。
こういう意味不明問題を作れるようにしたい。
謝辞
合宿にて問題提供の機会を下さったzukkyさん・会津大学の皆様、AOJ上の問題設定等をして下さった渡部有隆さん、コンテストに参加して頂いた方に御礼申し上げます。
