hotpepsiの練習帳

SRM 653

23:55

https://competitiveprogramming.info/topcoder/srm/round/16317/div/1

https://competitiveprogramming.info/topcoder/srm/round/16317/div/2

Div1 Easy (250) CountryGroupHard

問題

• 人々が一列に座っている
• 同郷の人が連続して座る
• 同郷の人の人数を聞いた結果の配列aが与えられる
• a[i]がゼロなら質問しておらず、正なら人数が入っている
• 残りの人に質問しなくても、構成が一意かどうかを求める

方針

• メモ化再帰
• [pos,N)の区間が一意かどうかを返す
• Failed System Test
• ゼロの扱いがバグっていた
• (解き直し)
• [pos,N)の区間が何通り(以上)かを返す。不可能であればゼロを返す。2通り以上あれば2を返す
• 区間内でゼロでない最初の要素を見つける。全部ゼロなら、ゼロの個数を返して終了
• その位置と値でありうるパターンを列挙する(たとえば3の場合、末尾で3のとき、真ん中のとき、先頭のとき)
• 数字が矛盾しない(333や300など)なら、左右の矛盾をチェック
• 左側の判定は左側のゼロが1個以下かどうか
• 右側の判定は再帰
• [0,N)が1かどうかが答え
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_653/CountryGroupHard.cpp

結果

x-- +1 50pts 240th/524 rating 1410 -> 1454 (+44)

場合分けの多い再帰を書いてしまった。シンプルに区間[L,R)で書くべき。

http://togetter.com/li/796268