キーエンス プログラミング コンテスト 2021

風呂の時計は10分進んでいるんですね~と思ってゆっくり風呂に入っていたら知らない間に風呂の時計が直っていて、10分遅刻(は?)

 

A

aとbの累積maxの積?

 i \leqq jより、 c_i \neqq c_{i-1} となるのはb_iを使う場合のみ

→aの累積maxを持ってDP

 

B

小さい数からバケツに積んでいくことを考える

なるべく標高が高い山を多く作れればよいので、貪欲

 

C

各盤面についての経路の総和=各経路についての盤面の総和(主客転倒)

経路を定めると、経路に含まれる未決定のマスの数がわかり、対応する盤面の数もわかる

経路数はDPで求められる

経路数のDP遷移で、到達しないことが確定するマスが増えるたびに、3^(到達しないマスの増加分)を二次元累積和で掛けておけばよい

 

3^(到達しないマスの数)=3^(k-到達するマスの数)として、初期値を1 -> 3^k、未決定のマスに到達するたびに(2/3)を掛けると楽

 

D

N=2までは簡単に構築できる

N=3以降が難しい、二冪なので再帰的&対称的な構造を考えたくなる

 

形の対称性と二冪であることより正方行列で考えたい

N=2の場合を作り、行として0000を加えて観察すると、上下半分、左右半分がそれぞれ同じ形or反転した形になっていることがわかる

0000 c

0110 x

0011 x

0101 c

c c x x

 

整理すると、

0000 c

0101 c

0011 x

0110 x

c c x x

 

再帰的構造が見えるようになった

 

最小操作回数なので下界を求めに行くべきだったかも?

毎回ある人と同じグループになる人が 2^{N-1}-1人増えていくことと、どの人ともn回同グループになることより (2^{N-1}-1)x = n(2^N -1)、ここから下界が求まる

 

E

すぬけくんが取る飴は(条件に矛盾しない範囲で)後でまとめて取ることにしてよい

dp[蟻の左側のid][蟻の右側のid][蟻が取った個数-すぬけくんが取った個数+1]とすると、蟻のスタート位置ごとにO(N^4)でできる

スタート位置に関わらず最終状態は同じになる

→dpのグラフが木状になっている様子をイメージすると、操作順を逆にしてDPができることに気が付く

→O(N^3)になる

 

 

(すぬけくんが取った個数+1)>=(蟻が取った個数)と、蟻は大きい方を取ることを満たすように遷移する

操作順を逆にして考えていることに注意

 

メモ化再帰でやると"操作順を逆に~"の考察パートがskipできてよさそう