A. Robot Program

到達したい (x, y) において、x \( \le \) y とします。(x, x) までは 2x 回で到達できて、残りは 2(y-x) - 1 回かかります。x = y の時は注意です。

B. Toy Blocks

B にしては難しくて焦りました。まず、条件を満たすような数列の条件を考えていきます。明らかに、数列の総和が N-1 の倍数である必要があります。さらに、数列の要素の最大値が、(総和) / (N-1) 以下である必要もあります。これが必要十分条件で、これを満たすような最小の総和、を見つければ良いです。

C. Two Brackets

B を通した時点で、1000 人以上 C を通していたので、簡単なんだなと思いながら問題を見ました。すると貪欲に対応する括弧をマッチングしていけばいいと書いてあるので、やります。

D. Radio Towers

これすき。まず、求めるものは確率ですが、2ⁿ 通りの全事象のうち条件を満たす電波塔の並べ方がいくつあるかを数え上げれば良いです。次に、条件を満たすように電波塔を並べていきます。座標の小さい方から順番に電波塔を配置していくのが自然でしょうか。座標 1~i の範囲は既にカバーされているとします。ここから、座標 1~i の位置に電波塔を配置することはあり得ません。i+1 を必ずカバーしなければいけないことと、i を重複してカバーしてはいけないことを考えると、電波塔の置き方は、 i+1 に強さ 1 のものを置く、i+2 に強さ 2 のものを置く…、i+k に強さ k のものを置く、という置き方に限られることがわかります。少し見方を変えて ( 貰うDP を意識する感じ? ) 、1~i をカバーするような電波塔の配置の仕方は 1~i-1 までがカバーされている置き方に対して、i に強さ 1 の電波塔を置くパターンと、1~i-3 までがカバーされている置き方に対して、i-1 に強さ 2 の電波塔を置くパターン…となります。ここで、
DP[i] := (座標 1~i がぴったりカバーされているような電波塔の並べ方の総数)
とすれば、
DP[i] = DP[i-1] + DP[i-3] + ... = \( \sum_{k = 1}^{i - (2k - 1) = 0 or 1} DP[i - (2k - 1)] \)
となります。和のパートはテーブルを作っておいて順に更新していけば良いです。
こんな雰囲気のDPを最近よく見る気がします。

E. Two Editorials

解けなかったので、解説 AC しました。それぞれの参加者に対して、どちらの editorial を見るかを決めれば、editorial がカバーする範囲を全探索して解くことができます。ナイーブには、それぞれの参加者がどちらの editorial を見るかの決め方は 2^m 通りあるので到底間に合わないですが、実は意味のある決め方は m 通り程度に抑えることができます。例えば、2 つの editorial がカバーする範囲を決めてしまうと、それぞれの参加者が見るべき editorial が決まります。具体的には、editorial のカバーする範囲の中心と、参加者が見たい範囲の中心の距離が小さくなる方の editorial を選べば良いことがわかります。つまり、参加者を、見たい範囲の中心位置でソートすると、参加者を前と後ろで 2 分割してしまう方法が意味のある決め方になっていることになります。あとは、
pre[i] := ( 前から i 番目の参加者までが 1 つめのeditorial を見るとしたときの、( editorial のカバーする範囲を動かした中での ) 参加者がeditorail を受けられる task の最大値 )
suf[i] := ( 前から i 番目の参加者から、m 番目の参加者までが 2 つめのeditorial を見るとしたときの、( editorial のカバーする範囲を動かした中での ) 参加者がeditorail を受けられる task の最大値 )
とすれば、答えは pre[i] + suf[i+1] の最大値 ( 0 \( \le i \le \) m ) です。
言われてみればそうだけど、難しい…。

感想

B を落ち着いて解けたのと、D を瞬殺できたのは良かったです。

現代の量子力学

主に精進の様子を記録する日記帳です

Educational Codeforces Round 98 (Rated for Div. 2) A~E メモ

A. Robot Program

B. Toy Blocks

C. Two Brackets

D. Radio Towers

E. Two Editorials

感想