キーエンスプログラミングコンテスト2021
キーエンスプログラミングコンテスト2021 の備忘録です。
問題はこちら↓
今回はAB2完でした。
・A問題:Two Sequences 2
n ≦ 2*10^5 の為全探索では間に合わない。また n 番目までに出てきた最大値を記録しておくだけでは i > j の時を弾けない。ここで n が 1 増えた時を考えると、b[n-1] まででの最大値 c[n-1] は計算済みのため、c[n] になりうるものは c[n-1] か、それまでに出てきた a の最大値に b[n] を掛けたもののどちらかとなる。
・B問題:Mex Boxes
蓋に表示される整数を最大化する為には、箱に 0,1,2,... のように納めていくのがよい。なので同じ整数の書かれたボールは可能な限り違う箱に納めた方が良いことがわかる。各整数毎に何個あるかを調べておき、ボールの個数と K の小さい方だけ答えに 加えていくことで求めることができる。ただし途中で数字が飛んでしまうとその箱の蓋に表示される値がそれ以上大きくなることは出来ないので、それまでに出てきた整数の個数の中でもっとも小さいものを加えていくようにする。
この記事が気に入ったらサポートをしてみませんか？