キーエンスプログラミングコンテスト 2021参加記（～C問題）

300-400(1)-500-0(1)-0-0で1ペナ3完1200点。

A - Two Sequences 2

全ての組を見ると $O(N^2)$ かかりTLEする。
$c_n$ を求めるには、 $a_n, b_n$ までの要素を見ればよい。さらに $c_n$ を求める際、数列 $b$ から $b_n$ を選ぶか選ばないかで2通りに場合分けできる。

$b_n$ を選ばない場合

このとき、 $i\le j$ という制約から、 $a_n$ も選ぶことができない。つまりどちらの数列からも $n-1$ 番目までの要素から選ぶことになり、この答えは $c_{n-1}$ に一致する。

$b_n$ を選ぶ場合

このとき、 $a_1$ から $a_n$ までの要素のどれを選んでもよい。正の数同士の乗算なので、貪欲に最大値を選ぶのが最適である。

まとめると、 $a_1$ から $a_n$ までの要素の最大値を $a_{\max}$ とおいて、
$c_n=\max(a_{\max}\times b_n, \ c_{n-1})$
が答えとなる。一つ前の答えが必要なので前から順に計算していく。

計算量は、 $O(N)$ 。

数列 $a$ の中に、 $\{0, 1, 2, \dots , P\}$ があるときこれらをすべて使って $P+1$ 点を得られる。この時、 $P+1$ も $a$ の中に含まれているなら、 $\{0, 1, 2, \dots , P, P+1\}$ とすることで $P+2$ 点得られる。一般に、 $P$ 点得るには $P$ 個の数が必要なので、最高で $P$ 点得ることが可能なら貪欲に $P$ 個の数を使って $P$ 点得た方が良い。
あとは、数列 $a$ のなかにそれぞれの数が何個含まれているかをカウントし、数が大きい方から見て貪欲に作っていく。最高で $K$ 回までしか得点を得られないことに気を付ける（1WA）。

計算量は、 $O(N\log N)$ 。

C - Robot on Grid

全てのマスに文字が書き込まれているなら、 $O(HW)$ のDPで解くことができる。配るDPで書くと、
dp[i][j]:=(マス(i, j)に行く経路の数)
と定義して、マス(i, j)が右方向に進めるならdp[i][j+1]+=dp[i][j]とすればよい。下方向も同じくdp[i+1][j]+=dp[i][j]となる。最初のマス(1, 1)にいるロボットは $1$ 体なので、dp[1][1]=1である。

ここで、 $C=HW-K$ とおく（何も書かれていないマスの数を表す）。マスへの書き込み方は $3^C$ 通りあるので、マス(1, 1)に $3^C$ 体のロボットをおいて、すべてのロボットが異なる動きをすると仮定して考える。このとき、何も書かれていないマスに到達したロボットのうち、 $\dfrac{1}{3}$ は「R」、 $\dfrac{1}{3}$ は「D」、 $\dfrac{1}{3}$ は「X」であり、右に進めるのはマスに「R」か「X」が書かれていた場合のみである。よって、動的計画法の遷移は
dp[i][j+1]+=dp[i][j] * 2 / 3
となる。下に進む場合も同様である。計算時は、常にMODを取って計算することを忘れないようにする。また、割り算のMODは逆元を用いて計算できる。