キーエンス プログラミング コンテスト 2020 A, B, C 考察

keyence2020 A - Painting

ペイント操作は少ないほうが良いので 1 回の操作で塗れるマスが多い方が良い。行か列の大きい側を選んで塗る。これが 1 回の操作で塗れるマス数になる。その単位で塗って N を超えるのに何回かかるかなので割って切り上げれば良い。 (N + MAX(H, W) - 1) / MAX(H, W) で求まる。

https://atcoder.jp/contests/keyence2020/submissions/16974316

keyence2020 B - Robot Arms

最初に思いついたのはロボットの手を広げた状態でロボットごとに重なる個数を調べて 2 個以上になったものを取り除く方法。この方法だと O(N^2) になるので間に合わない。

重なっているかを調べるには広げた手の位置で並べたときに隣り合っているものを調べれば良い。左手の位置で並べて前のロボットの右手より左に左手があるなら重なっている。どちらを取り除くべきかはより右手の位置が右にあるほうだ。そのほうが次の要素が重なりにくくなる。どちらを取り除くにせよカウントは 1 増える。最後は全体の個数から取り除いた個数を引けば答えになる。

ソートと貪欲法で O(NlogN) になる。

https://atcoder.jp/contests/keyence2020/submissions/16975491

keyence2020 C - Subarray Sum

解説 AC 。解説を読むとかんたんだと分かる。もう頭が回っていなかった。

l = r が許されているので各要素を S にし K 個並べれば良い。残りの箇所で S がつくれないようにすれば答えになる。 S < 10^9 なら S+1 で S = 10^9 なら 1 などにすると N 個並べても S がつくれない。

https://atcoder.jp/contests/keyence2020/submissions/16975701

リングフィットアドベンチャーを続けている。