キーエンス プログラミング コンテスト 2021 A,B,C,D,E問題メモ

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

A - Two Sequences 2

• 長さ $N$ の2つの数列 $A_1,A_2,...,A_N$ と $B_1,B_2,...,B_N$
• 次の操作で生成される数列 $C_1,C_2,...,C_N$ を求めよ
• 操作
  • $C_k$ は、$1 \le i \le j \le k$ を満たす $(i,j)$ の組についての $A_i \times B_j$ の最大値
• $1 \le N \le 2 \times 10^5$
• $A_i,B_i$ は正

まず、$i=1$ の時は $A_1 \times B_1$ しかない。

次に $C_{i-1}$ までが求まっているとして、$C_i$ を考える。

$B_i$ を使うか使わないかで分けて考えると、

• 使うとき
  • $A$ は $A_1～A_i$ から好きなのを選べる。当然、最大の値を使うのがよいので $A_{max} \times B_i$ が候補となる
• 使わないとき
  • $A_i$ も使えなくなる。よって、$C_{i-1}$ と変わらない

この2つを比較して、大きい方を $C_i$ とすればよい。

Python3

B - Mex Boxes

• ボールが $N$ 個あり、それぞれ非負整数 $a_1,a_2,...,a_N$ が書かれている
• これを $K$ 個の空箱に好きなように分けて入れる
  • 入れた後も空の箱があってもよい
• 各箱のMEXの総和としてあり得る最大値を求めよ
  • MEXとは、その箱に入っていない非負整数の中で最小の値
  • Mex_(mathematics)
• $1 \le N \le 3 \times 10^5$

例えば $0,1,2$ が入って $3$ が入っていない箱があったら、後はどれだけ大きい数字を入れようとその箱のMEXは $3$ である。

次のようにイメージするとよい。

ボールを値別にカウントした状態
ai
5:  oooooooo
4:  
3:  ooo
2:  ooooooooooo
1:  ooooo
0:  oooooooo

ここで、同じ値のボールを1つの箱に入れたり、たとえば3を0,1,2の入っていない箱に入れるのは無駄。
よって、値ごとに左詰にして、縦の1列が1つの箱に入れるボールと考えて問題ない。

すると、MEXを大きくするのに意味のあるボールは結局、小さい方から最小値をとっていった以下のようになる。

5:  
4:  
3:  ooo
2:  ooooo
1:  ooooo
0:  oooooooo

以下の手順を実装するとよい。

• $a_i$ を値別にカウントして、$a_i=k$ のボールの個数を $c_k$ とする
• MEXがまだ確定していない箱の個数 $X = \min(K,c_0)$ で初期化する
• $k=1,2,...$ について、順に処理する
  • MEXが $k$ となる箱は $X - \min(X,c_k)$ 個
    • 答えに $(X - \min(X,c_k)) \times k$ を加算
  • $X ← \min(X,c_k)$ に更新
  • 更新後に $X=0$ だったらおわり

Python3

C - Robot on Grid

• $H \times W$ のグリッドに 'R','D','X' を書き込む
• 既に $K$ マスについては書き込まれていて、その情報は与えられる
• 残りのマスへの書き込み方は $3^{HW-K}$ 通りある
• この書き込み方全てについて、以下を求め、その総和を $\mod{998244353}$ で求めよ
• 求める値
  • 左上 $(1,1)$ から右下 $(H,W)$ まで、右か下へ1マスの移動を繰り返して到達する経路数
  • ただし、'R' の書かれたマスでは右、'D' の書かれたマスでは下にしか移動できない
  • 'X' はどちらにでも移動できる
• $2 \le H,W \le 5000$

DPだけど、通らない空白マスは何でもよい、というのをどう扱うか。

まず、'R','D' などの変な制約のない経路数を求める時の定石として、上と左を足していく以下のDPはよく使われる。

• $DP[i][j]=(1,1)$ から $(i,j)$ への経路数 $= DP[i-1][j]+DP[i][j-1]$

これを踏まえて今回の制約を含めて経路数を考える。例えば右移動を考える（下移動も同様に考えられる）。

なんとなくのイメージとして、以下のようなことを行えばうまくいきそう。

■遷移元の文字が明らかなとき: 移動できるならそのまま, 移動できないなら0。

遷移元のマス
文字/経路数
   R/20     →   20
   D/20     →    0
   X/20     →   20

■遷移元が空白の時、右に移動できるのは'R','X'の2文字なので、2倍して遷移。（下移動も同様）

   _/20     →   40

しかし、このままでは「ある経路において通過しなかった空白マスは、何の文字でもよい」ことが考慮されていない。
答えに反映する際には経路数を $3^{通らなかった空白マス数}$ 倍する必要がある。

だが通過しなかった空白マス数は経路によって異なる一方、上記のDPではいろんな経路が混ざってしまっているので、うまく求められない。

逆に、答えとなる値を直接求めるようなDPを組むとよい。つまり、以下のDPを定義する。

• $DP[i][j]=$ 全書き込み方における、$(1,1)$ から $(i,j)$ への経路数の総和

$DP[1][1]=3^{HW-K}$ としておく。

遷移元の文字が明らかなときはさっきと一緒。

遷移元が空白の時、その遷移ができる文字の種類数は $3→2$ になるので、$2/3$ 倍して遷移する。

   _/60     →   40

こうすると、うまく求められる。

$\mod{}$ が素数なので、$3^{-1} \times 2$ はあらかじめ求めておくとよい。

Python3

D - Choosing Up Sides

• $2^N$ 人を、ちょうど半分ずつ2グループに分ける、という操作を繰り返す
• 以下の条件をともに満たすように1回以上操作したい
  • 「人 $i$ と $j$ が同じグループに入った回数」が、全ての2人の組 $(i,j)$ について同じ
  • 「人 $i$ と $j$ が違うグループに入った回数」が、全ての2人の組 $(i,j)$ について同じ
• 最小手数で実現するようなグループ分けの仕方を1例、構築せよ
• $1 \le N \le 8$

ひらめき系？ 構築方法自体は何かの過去問にあったような気もする。

条件は2つあるが、「全操作回数 ー 同じグループに入った回数 ＝ 違うグループに入った回数」なので、 一方が満たされればもう一方も満たされるので、実質1個と考えてよい。

操作回数の下限を考える。

以下のような表で同じグループに入った回数を数えることを考えると

i\j  1  2  3  4
1    -
2    -  -
3    -  -  -
4    -  -  -  -

• 同じ数で埋めるべきマスは $C=\dfrac{2^N(2^N-1)}{2}$ 個
• 1回の操作で+1されるマスは $D=\dfrac{2^{N-1}(2^{N-1}-1)}{2} \times 2$ 個
• 操作を何回か繰り返して $C$ の倍数と $D$ の倍数が同じにならなければならない

これは、$C(2^{N-1}-1) = D(2^N-1)$ で一致することとなる。
逆に、$2^N-1$ と $2^{N-1}-1$ の最大公約数は必ず1なので（ユークリッド互除法の最初の1手を考えるなど）、これ以上は小さくならない。

よって、少なくとも操作は $2^N-1$ 回は行われないと全てのペアを同数にできない。

これはあくまで下限なので、うまい振り分け方が無くて実際はもっとかかるかもしれないが、 もし $2^N-1$ 回でできるとしたら、同じグループに入る回数は $2^{N-1}-1$ 回、違うグループは $2^{N-1}$ 回ということになる。

どうせできるやろと当たりをつけて考えを進める。

$N$ の答えを求めるにあたり、$N-1$ の答えは、半数の人のグループ関係については条件を満たしているので、これをうまく使いたい。

$N=2$ の答えがある。（見やすさのため、$A=0,B=1$ とおく）

1 2 3 4
-------
0 0 1 1
0 1 0 1
0 1 1 0

$N=3$ の答えを7回の操作で実現したい。とりあえず最初の3回について横に並べてみる。

1 2 3 4  5 6 7 8
----------------
0 0 1 1  0 0 1 1
0 1 0 1  0 1 0 1
0 1 1 0  0 1 1 0

こうすると、

• 1と5、2と6、3と7、4と8は振る舞いが同じ
• 1から見たときに、2,3,4それぞれと同じグループに入った回数は同じ1回であることが $N=2$ の時の結果よりわかっている
• →1と、6,7,8それぞれとの、同じグループに入った回数は同じ1回

2,3,4についても同じことがいえ、残る問題は、1と5、2と6、などのペアについての回数が多くなっていることとなる。

7回中、同じグループに入るのは3回。つまり1と5などは、これ以上同じグループに入らない。

ここで、1と5、2と6などがこれ以上同グループにならないようにすることを考えると、 「$5～8$ については0,1をまるっと反転させた結果を横に並べた」のを追加するとよさそう。

1 2 3 4  5 6 7 8
----------------
0 0 1 1  0 0 1 1
0 1 0 1  0 1 0 1
0 1 1 0  0 1 1 0
0 0 1 1  1 1 0 0  NEW
0 1 0 1  1 0 1 0  NEW
0 1 1 0  1 0 0 1  NEW

ひとまず1を中心に考える。

$N=2$ の時に、1と、2,3,4の関係は、同グループが1回、違うグループが2回だった。
つまり、$N=3$ の時に上の図で1と6,7,8との関係は、反転してないのとしたのを合わせるとちょうど目標の3回となる。

また、1と5についても前述のように同グループとなる規定回数を満たしている。

残るは、1,2,3,4について同グループとなった回数が1回ずつ少ないことなので、それを追加すると、どのペアとも3回ずつとなる。

1 2 3 4  5 6 7 8
----------------
0 0 1 1  0 0 1 1
0 1 0 1  0 1 0 1
0 1 1 0  0 1 1 0
0 0 1 1  1 1 0 0
0 1 0 1  1 0 1 0
0 1 1 0  1 0 0 1
0 0 0 0  1 1 1 1  NEW

今、1と同グループになる回数をもとに説明したが、対称性があり、2,3,4についても同じことがいえる。

（問題文の条件違反ではあるが）全ての人が同グループになる仮想的な操作を追加すると、

1 2 3 4
-------
0 0 0 0  ←
0 0 1 1
0 1 0 1
0 1 1 0

これを田の字に並べ、右下だけ反転したもの（の最初の1行を無視したもの）が、次の答えとなる。

1 2 3 4  5 6 7 8
----------------
0 0 0 0  0 0 0 0
0 0 1 1  0 0 1 1
0 1 0 1  0 1 0 1
0 1 1 0  0 1 1 0
0 0 0 0  1 1 1 1
0 0 1 1  1 1 0 0
0 1 0 1  1 0 1 0
0 1 1 0  1 0 0 1

仮想的な操作の追加により、全てのペアについて同グループになった回数も、違うグループになった回数も $2^{N-1}$ 回で揃うので、 反転させたもの、反転させないものを繋げた時、各ペアにつき同じグループに属した回数がそれぞれ2倍になることが少しだけイメージしやすくなる、かも。

このように生成される行列は、アダマール行列と名前が付いていて、任意の2行が互いに垂直になるなどの性質があるらしい。

Python3

E - Greedy Ant

• 数直線上に $N$ 個のキャンディが落ちている
• $i$ 番目のキャンディの美味しさは $a_i$ で、座標 $2i$ に落ちている
• このキャンディを、人と蟻が交互に1個ずつ取り合う（人から始める）
• 人は好きな位置のキャンディを取る
• 蟻は、「今自分がいる位置」が決まっていて、左右にあるキャンディのうち美味しい方のキャンディの位置まで移動して取る
• 蟻が、座標 $1,3,5,...,2N+1$ の $N+1$ 箇所から開始した時それぞれについて、人がとれるキャンディの美味しさの総和の最大値を求めよ
• $1 \le N \le 400$
• $a_i$ は全て異なる

解説AC。区間DPで解ける。

大まかには美味しいキャンディから取っていくのがよさそうだが、それでは上手くいかない例が入力例1で（優しいことに）紹介されている。

4 3 1 🐜 2 1000 2000 3000

この例では、初手で1を取るのが最適となる。
うかうか3000などを取っていると蟻は2→1000→2000とどんどん美味しいキャンディの方に浸食してきてしまうが、 1を取ることで蟻は3→4の方向に誘導され、2の壁によって美味しいキャンディが後回しになる。

このような現象は初手にのみ起こるわけでも無く、途中で何度でも起こりうる。
また、蟻に隣接するもののみ考えていればいいわけでも無く、「あらかじめある範囲をまとめてごそっと取り除いておく」必要があるケースも考え得る。

N=20
11 10 9 8 7 3 6 2 1 5 🐜 4 1000 2000 3000 4000 5000 6000 7000 8000 9000

この例とか、何も対策しないと蟻は2ターン目に4の壁を突破して、以降は大きい数の取り合いとなり1000～3000は蟻に取られてしまうが、 まず1,2,3を取り除いてやることで、蟻は7→8→…の方に誘導され、人は大きい方から7つを悠々と取ることができる。

この「蟻がまだ4,5あたりにいる段階から、1,2,3を選んで取り除き始める」ことを予見するのはなかなか難しそうに思える。
また、蟻を誘導するためには何個か小さい数字を取ることになるので、その差し引きが、最大から貪欲した場合より得なのか損なのか変わってくる。
さらに、右側を堰き止めて、ある程度右側で大きい数字を取り尽くしたら、堰き止めてたやつを取って、今度は左で堰き止めて……という戦略もあり、 「どこで堰き止めるか」などを固定するような方法は、ちょっと切りが無さそう。

以下の事実を利用すると

• 蟻がある時点で取れるキャンディの配置は、（間のいくつかを人に抜かれるとしても）連続した区間となる
  • →どこからどこまでを取ったか、という区間DPが使えそう
• 上記の1,2,3のように、小さい数字を取って意味があるのは、すぐにではないにせよ、後に蟻がそこまで到達するような箇所のみ

なので、実際に蟻の行動範囲を管理などして、1,2あたりに到達したときに、「1,2を取った場合の最終値」と「無視して大きい方から取った最終値」の比較ができると、DPが組めそう。

ただ、十分準備ができないまま蟻が来てしまう場合もある。蟻がそこに到達するまでに、本当に取り除けるのか、位置関係によって変わってくる。

11 10 9 8 7 4 3 2 1 6 🐜 5 1000 2000 3000 4000 5000 6000 7000 8000 9000

5を取られる前に1,2,3,4を取り除くと蟻は7,8,...の方に誘導されるが、
実際には全部取り除くには間に合わず、どうしても5を先に取られてしまう。
（なのでこの場合は、大きい方から取っていくのがよい）

実際に取るのでは無く、「取る権利を1ターンごとにもらう」と考えると上手くいく。

• $DP[l][r][k]=$ 次が蟻のターンで、蟻の左右に残っているキャンディの位置が $l$ と $r$ であり、人の取る権利が $k$ 個残っている場合の、そこから人が獲得できる最大美味しさ

両端に $a_0=0,a_{N+1}=0$ を番兵として追加しておくとよい。

たとえば、最初の例では、以下の3通りの選択肢がある。

           l     r
i  0   1 2 3     4    5    6    7   8
  (0)  4 3 1 🐜 2 1000 2000 3000  (0)

• 何もしない
  • ここでは $a_l \lt a_r$ なので、$r$ の方を取られる。次のターンで取る権利を1個もらう
  • $DP[3][4][k] ← DP[3][5][k+1]$
• $l$ を取る
  • 取る権利を1個消費する。これは本来過去のターンを持ってきたものなので、続けて蟻のターンとなる
  • $DP[3][4][k] ← DP[2][4][k-1] + a_l$
• $r$ を取る
  • 同上
  • $DP[3][4][k] ← DP[3][5][k-1] + a_r$

ただし、$←$ はMAXで更新する操作とする。
$k=0$ の時は取ることはできないので、何もしない操作のみとなる。

$DP[l][r]$ を求める際には、より外側に範囲を拡張させた $DP[l-1][r]$ や $DP[l][r+1]$ が埋まっている必要がある。
つまり、$r-l$ の大きい方から順に埋めていくとよい。

$r-l=1$ まで埋めたら、$i=0～N$ につき、$DP[i][i+1][1]$ が答えとなる。（人からターンが始まるので、最初に取る権利は1個存在している）

Python3

まるで別の解法というわけではないが、以下の入力で、

2
1 1000

以下の結果を返すコードが通ってしまった。（本当は最初も当然1000）

1
1000
1000

どうも、「最大まで取れる権利を貯めてから、一気に使う」ようなケースが見逃されているらしい。

DP配列で、取る権利の残数 $k$ は、取る権利をためて意味のある $\dfrac{N}{2}$（切り上げ）個まで考慮すればよいはずと考えた。

この値を $lim$ とすると、配列外参照をしないためには、$DP[l][r][lim]$ の更新をどうすればよいか。

「$lim$ まで貯まったんなら、必ず消費する必要があるだろう」と誤った考えを元に、必ず $l,r$ のいずれかを取る、というコードを書いてしまうと、上記の誤ったコードになる。

このDPの遷移は、1つ $r-l$ が大きい前計算結果の $k-1,k+1$ を参照する。
そのため、($r-l$ の偶奇)XOR($k$ の偶奇) によって、遷移元・遷移先のつながりが2つに分かれてしまっている。
この断絶により、$N$ の値によっては、正しい答えが求まらなくなってしまっていた。

ここでは、$DP[l][r][lim]$ を「$lim$ 以上」と見なして、取る権利をさらに蓄積することも可能にすると、問題なくなる。