Codeforces Round #374 (Div. 2): ABCD

http://codeforces.com/contest/721

A: One-dimensional Japanese Crossword

問題概要

連続する黒マスの個数を順に出力せよ。

解法

そのまま。ランレングス圧縮のライブラリがあると少し楽。

B: Passwords

問題概要

パスワードのリストと正しいパスワードが与えられ、文字列長の短いものからパスワードを総当りする。ただし、同じ長さであればどちらが先でも構わない。パスワードを一つ試すのに1分かかり、k回間違える毎に5分のペナルティが掛かる。正しいパスワードを入力するのに掛かる時間の最大値・最小値をそれぞれ求めよ。

解法

そのまま。

C: Journey

問題概要

DAG(閉路のない有向グラフ)が与えられる。1→Nに移動するT秒以下の経路のうち経路長最大のものを求めよ。

解法

dp[ v ][ len ]:=v→Nへの長さlenの経路の最小コストをする。答えは dp[0][len]≦T となる最大の len。今回は DAG なので DFS あるいはトポロジカルソートにより解くことができる。各辺ごとに N 回のループが回るので計算量は O(NM)。もちろんダイクストラ法でも解ける。

5000*5000 の配列は結構 MLE が怖いので、きちんと見積もっておいたほうが無難。

D: Maxim and Array

問題概要

数列が与えられる。ある要素を +x または -x するという操作を K 回行い、すべての要素の積を最小化せよ。

解法

積は負である方がいいので、積を負にすることを考える。直感的には絶対値最小の要素の符号を変えれば良さそうである。

積を負に変えられなくても絶対値最小の要素を 0 に近づけるという戦略は最善になる。というのも、a=[1,2,3,4,5],x=1を考えたとき、a[0]-- は 2*3*4*5 の減少、a[n-1]-- は 1*2*3*4 の減少となり、前者の方が減少が大きい。

積が負になったとしよう。後は積の絶対値を最大化することを考えればいい。操作が1回しかできないのであれば、絶対値最小のものを増加させるのが最も増加するので最善である。操作が複数回行える場合も貪欲にこの戦略を適用するのが最善となる。

0 の存在が厄介なので、真に負の数を奇数個に揃えるようにする。最大化パートでは 0 以上であれば +x、0未満であれば -x する。

B問題の読解に苦労した…。