帰ってきたお誕生日コンテスト 解説・講評
コンテストサイト: http://kcs.miz-miz.biz/contest/1009/
参加してくださった皆様、ありがとうございました。皆様の貴重な時間をこのようなコンテストに割いて下さったこと、感謝してもしきれません。
このコンテストは発案から開催までの準備期間が 10 日しかなかったので様々なところがガバガバなのは許してください！！！何でもはしません！！！！！！
というわけで、出題された全 26 問の解説・講評です！
括弧内は発案者です。時間を浪費された方々につきましては、各問題の発案者を恨んで頂ければと思います。
A: Introduction to ESP (JAPLJ)
入力を出力するだけの簡単なお仕事です。ただし改行文字、空白文字、ヌル文字などが容赦なく襲いかかるので注意しましょう。
発案者コメント「優しい問題にするつもりだった。ここまで意地悪になるとは考えていなかった。反省していない。後悔していない。」
B: 19-Year-Old A + B (kagamiz)
A + B を計算するだけの簡単なお仕事です。ただし「1 ≦ A, B ≦ 10」は「1 ≦ A かつ B ≦ 10」という意味なので、A, B はそれぞれ超でかくなったり超小さくなったりします。
多倍長がある言語を使うと何も気にせず解けます。
発案者コメント「当初は|a + b| <= 10 という制約で問題を出そうとしていましたが, writer の J 氏の助言を受けてこの制約になりました. LL は便利ですね.」
C: Pro (kyuridenamida)
プロと言われたら趣味と返すだけの簡単なお仕事です。「shumi」「syumi」「hobby」などが出力に含まれていれば OK です。
発案者コメント「意味不明な悪しき風習である内輪ネタを出題しました。まさか寝る前の謎ツイート群を見て韓国の人が通してくれると思いませんでした。彼はプロです。」
D: 810 (kyuridenamida)
同じ入力から異なる 2 通りの出力を得るために乱数や process id などを使いましょう。乱数を時間をシードに初期化する場合、time(NULL) 等では秒数単位になってしまうので気をつけましょう。
発案者コメント「ACの期待値4回なので出しました。主な想定解はsleepとか乱数とかそのへんですが、pidを使う方法と書き込む方法(これは禁止したつもりだったんだけどな)がありました。」
E: 2014 (JAPLJ)
PKU 2014 を解いてください。サンプル入出力でググれば普通にヒットします。
発案者コメント「結構わかりやすいと思ったけど意外と解かれていなくてびっくりしています。まずググるのは基本、はっきりわかんだね。」
F: カズマ予想 (kyuridenamida)
N を素因数分解した時の素因数を小さい方から順に並べて出力してください。正統派エスパーですね。
発案者コメント「これ思いついた後、この操作を繰り返したらどれくらいの長さになるのかなと思いました。まさかと思って直前にOEIS見たらOEISにあって泡吹きました。」
G: Format Table (kagamiz)
入力を a, b, c として、a から始まる b × c 個の整数が素数かどうかを Y/N で示すテーブルを出力してください。値はけっこうでかいので適当にやると TLE します。
発案者コメント「最初は最後のサンプルが無かったのですが, writer の MKM さんが瞬殺で解いていたので区間篩が必要な理不尽問題になりました」
きゅうりコメント「普通に憤りを覚えました(怒並感)。同時に爆笑してたけど。文章が「くさい」ということはあまりないがこれは最高にくさかった」
H: Picture The First (kyuridenamida)
円を囲う凸領域の周の長さの最小値を求めてください。絵のとおりですね。
既出問なので解き方は色々有りますが、円を正 1,000 角形だと思って凸包する、とかが楽だと思います。
発案者コメント「エスパーコンテストと言えば絵だろ！と思って描きました。エスパー部は簡単ですが、ガンギマリのwriter陣によって半径という概念が追加され円凸包になってしまいました。下の問題とリンクしています。ちなみに円包法は適当に円周点を全部追加して点凸包でOKです。誤差ガバガバです。」
I: Picture Relinquish (kyuridenamida)
H とほぼ同じですが、木（植物）ではなく木（グラフ理論）です。まず、木でないグラフは無視してください。
半径は与えられないので、半径（グラフ理論）をかわりに使う必要があります。ある頂点 v から最も遠い頂点への距離を e(v) として、e(v) の最小値がそのグラフの半径です。
発案者コメント「ガンギマった人が、「木(グラフ理論)を囲んでる絵だったら面白そう」とか言い出したので描いてみたら面白かったので半径(グラフ理論)を導入しました。座標はさすがに遠心性(グラフ理論)とか意味不明なので素直に与えました。」
かがみずコメント「気合入ってるとおもった(小並感)」
J: Picture+ (kagamiz)
与えられた x の関数のグラフを描いてください。サンプルからだと原点が分からないですが、原点は + です。
eval のある言語を使うと楽でしょう。
発案者コメント「原点がサンプルに無いのは writer が意図しておらず, タイトルにヒントを盛り込んでみました」
K: EP (kyuridenamida)
3x3 のスライドパズルで、0 を空白だと思った時、入力があり得る盤面かどうかを判定してください。
注意点として、ありえない場合に出力するのは「Impossible」ではなく「lmpossible」です！（最初の文字は小文字のエル）
発案者コメント「高専プロコンの影響で、息抜きにスライドパズルで遊んでいたので・・・。コンテスト1時間前に作りました。テストケース間違ってました。ごめんなさい。」
L: わけがわからないよ (kagamiz)
Grass の派生言語「ほむほむ」（http://yuroyoro.hatenablog.com/entry/20110601/1306908421）が書かれています。解読すると a+b と a-b と a*b と a/b の XOR をとって出力すればいいことがわかります。
発案者コメント「みなさん Esolang すきなんですね... Grass 派生言語なので一度お調べ下さい.」
M: マタイによる福音書 第七章 (JAPLJ)
欲しいものは何ですか？
「AC」「Accept」「Accepted」と出力してください。
発案者コメント「これ解ける人頭おかしいんじゃないの」
きゅうりコメント「 "give me ac"をACにしない理不尽なアウトプットチェッカーを許すな」
N: 問題 (kagamiz)
入力された文字列が「過去に IOI (国際情報オリンピック) で出題された問題のタイトルかどうか」を判定してください。
注意点として、入力ファイルは CRLF になっています。\r はきちんと除きましょう。
発案者コメント「本当にすまないと思っている.」
O: Third Eye (JAPLJ)
白い文字は罠です。HTMLのソースを見ると問題が書いてあります。
発案者コメント「白文字問題文に騙される人が多くてホクホクです、皆さん騙されてくれてありがとうございました。」
Q: クイズ (JAPLJ)
クイズに答えてください。注意すべき点は
- unique_ptr には std:: をつける必要はありません。
- アルジェリアは algeria で十分です。
- 「今、何問目？」は 8 ではなくて 17 (この問題は Q 問題です！) です。
あたりです。
発案者コメント「「今、何問目？」ってのが出そう、っていうツイートを見て作りました。衆議院議員のアレは許してくれ頼む。」
R: 著名程序员 (kyuridenamida)
入力されたユーザの TopCoder と Codeforces のレーティングの和を出力してください。
テストケースは tourist, Egor, Petr, ACRush, rng_58 しかなくて優しい……と思いきや、りんごさんは TopCoder では現在非アクティブユーザになっていてランキング等に出てこないので注意しましょう。
発案者コメント「リアルタイム変更も覚悟していました。テストケースは"Petr,ACRush,rng_58"です。rng_58を追加したのはjapljです。悪意要素は(当初は)ない予定でした。」
S: 単一始点最短経路問題 (JAPLJ)
N ≦ 50,000,000 (最大ケースがあるとは言っていない)
実際には 10 万頂点 20 万辺ぐらいの普通のグラフしか来ません。ダイクストラしましょう。
発案者コメント「ガバガバ制約は JOI が既にやってる（http://www.ioi-jp.org/joi/2005/2006-m1-prob_and_sol/2006-m1-t4.html）から多少はね？」
T: トラスト・ミー (JAPLJ)
本当に本当です。そのまま解いてください。
発案者コメント「参加者の皆様が心優しい人達ということが分かって良かったです。そんな心優しい人達が、問題の出来が悪いぐらいのことで怒らないって僕信じてますよ。」
U: なんだこの数列！？（驚愕） (JAPLJ)
OEIS では「seq:114 seq:514 seq:810」という検索クエリで「114, 514, 810 をどこかに含む数列」が検索できます。「114,__,514,__,810」とかも良いです。
出てきた数列を計算してください。n がでかいので、ちゃんと計算するなり埋め込むなりしてください。
発案者コメント「オンライン整数列大辞典は神」
V: バー (JAPLJ)
入力を縦にのばすと……うわあ……これはバーコードですね……、なんだこれは……たまげたなあ。
このページ（http://piyajk.com/archives/321）とかが参考になります。check digit が合ってない場合に INVALID と出力してください。
発案者コメント「プログラミング要素はありません、っていうコンテストにしたくなかったので、実装ゲーみたいなのもありだよね、みたいな。」
W: 極めて普通な教科書的ナップサック問題 (JAPLJ)
極めて普通な教科書的ナップサック問題です。ただし、入力の大きさに応じて
- O(NW) の DP
- O(N 2N/2) の半分全列挙
を使い分けてください。
発案者コメント「O(N × (価値の和)) の DP を入れなかったのは怠慢です。」
X: 【規則性がわかったらIQ86以上】 (JAPLJ)
A = 51, B = 13, M = 100 の線形合同法 (X[n+1] = (A * X[n] + B) % M) です。
とはいえ、線形合同法に気づかなくても入出力例から規則性を見出して解くことができます。
発案者コメント「線形合同法せずに、普通に規則性を見出していた人達が多くてびっくりしています。」
Y: Travelling Salesman Problem (kagamiz)
入力は木か、それに1本辺を足したものしかありません。基本的には、サイクルなら辺の重みの和が答え、それ以外は -1 です。
ただし、孤立点のみからなるグラフの場合だけは答えは 0 になるというコーナーケースがあります。
発案者コメント「入力で使われたグラフはすべて pseudo tree というものになっています. ところで皆さんはunicyclic graph のことをなんと読んでいますか?」
Z: The legend of ESP (JAPLJ)
入力を reverse して出力してください。
発案者コメント「解いた人はキチガイ」
かがみずコメント「僕がwriterなら, A ~ Z 問題のサンプルに通し番号を付けて、番号に対応するサンプルを出力する問題にしてました」
