KCS Irregular Contest #002 のwriterをしていました。各問題について解説とか余談とかをいろいろまとめておきます。
優勝はuseridさん(5点、01:07:15)でした！
A: Prime Slash
解法：
dp[i]: iだけ存在するところから全部きったときの期待値 で配るDPする。iを小さい順にまわす。
配る先はi*2, i*3, i*4, ... 。等確率なので配られた先で(配られた個数/2)で割れば当該の期待値になる。
(ただし、i*iのときだけ1回余分に足す)
計算量は 1/1 + 1/2 + 1/3 + 1/4 + ... + 1/n = O(log n)になることを利用してO(n log n)
実数の計算とかで結構つらいのでO(n^1.5)の自明なDPは落ちると思います。
余談：
元ネタはもちろんprime smashです。りんごさんにrejectされた理由は「素数という時点で自明だと思う」
(りんごさんは今回見たことがない問題だけ解くという参加スタイルをしています。)
First Acceptance: userid (00:10:36)
B: Like POJ Monthly Style
解法：
足すクエリがsublinearで数列の値を求めるクエリがO(1)でできるようにしたい。
ということで平方分割
という想定だったのですが、yosupoさんとかがBITで通していました。出題ミス。
余談：
この問題はCMS Test Contestに出そうとしたが結局コンテストそのものが無くなったのでここに出しました。
やっぱりlogで落とすのは難しいなあ…とくにBITはlogと言っても軽すぎるのでだいぶ大変。
Time Limitもっと厳しくしたらよかったんかなあ…。
First Acceptance: userid (00:33:28)
C: Wolves and _|~|_
解法：
まず、オオカミごとに独立で、特定の1部屋を選んだとしてよい。
それぞれに対して、
dp[i][j]: i番目のオオカミまででその特定の部屋を選んだオオカミの強さの合計がjとなる確率
でDP。計算量はO(NM Sum(A[i]))
余談：
この問題はりんごさんに「独立」と言われrejectされました。
First Acceptance: mamekin (00:18:07)
D: Food Ticket 2
解法：
フロー。二部グラフのソース→片方、もう片方→シンクの容量が入力であたえられる値で、片方→もう片方の全部の辺に容量1で張る。
greedy解があるらしい。知らない。
余談：
①ぜひともFood Ticketの解説スライド読みましょう。
②問題文を反転させてみましょう。
First Acceptance: mamekin (00:10:55)
E: NU-STYLE ESPer GAME
解法： これだけ解説がまともに必要そうなので書いておきます。
この問題はほかの問題の解法とか実装量を知っている必要はないです。
まず、参考URLのブログを読みましょう。知るべきことは「writerは変数の名前がおかしい(予測に使えない)」「writerはscanfとprintfを使っている」の二つ。
ここから変数とかを考慮しない方法を考えましょう。一番不確定要素が少なそうなのは入出力という気がしてくる。
各問題の入出力形式を考えましょう。
A) 入力: 2つの整数 出力: 実数
B) 入力: 1つの整数+4つの整数の塊 出力: 64bit整数
C) 入力: 2つの整数+結構な数の整数 出力: 実数
D) 入力: 2つの整数+結構な数の整数+結構な数の整数 出力: 32bit整数
E) 入力: 文字列 出力: 文字
それから、入出力例からwriterは実数を小数点以下10桁出力していることを確認しましょう。
まず、Eだけ判別します。ここだけ少しエスパーします。2つの方法を考えました。
①A～Dに全く文字列を扱う問題はないので、charとかstringの個数で判別する。
②場合わけ問題なのでprintfが多そう。printfの個数で判別する。
次に判別すべきはB。%d%d%dが含まれていたら確定です。
残った中でDだけ%.10fが含まれていないので、それがDです。
A,Cは判別しづらいように見えますが、Aはscanf1つで済むのに対し、Cはscanfを2つ以上使うように見えます。
こんな感じで全問が仕分けられます。
余談：
参加者の解法は、printfなどの特徴から察するほかに、ソースコードの長さを大量にsubmitすることにより解析し、
コードが短そうな順にソートして文字を出力というものがありました。大変そうでした。
エスパーゲーは出そうかなと思っていたのですが、なんかこういうの無機化学の定性分析っぽくて面白そう、
と思って出題しました。実際はどうでしたか。
First Acceptance: userid (01:07:15)
２発正解賞: HIR180
