A - Painting

問題概要: H 行 W 列のマス目がある。すべてのマスは白である。以下の操作を繰り返し行い、黒のマスを N 個以上にしたい。操作回数の最小値を求めよ。

操作: 以下の2つから1つを選ぶ。

ある行に含まれるマスをすべて黒にする。
ある列に含まれるマスをすべて黒にする。

A: 考察

H≤W の場合だけ考えればよいです。というのも、H > W のときは全体を90度回転して H と W を交換すれば、H≤W とみなせるからです。

行を黒にする操作では、最大 H 個のマスを黒にできます。列を黒にする操作では、最大 W 個のマスを黒にできます。

なるべく多くのマスを黒にしたいので、列を黒にする操作の方がお得です。逆に、行を黒にする操作を使う理由は特にありません。また、すでに黒にした列に対して同じ操作を行う理由も特にありません。

したがって、操作回数を K とするとき、K 個の相異なる列に操作を行うのが最善です。結果として黒のマスの個数は KW になります。

N 個以上のマスを黒にしたいので、条件 KW ≥ N が成り立つ最小の整数 K を考えます。条件を変形すると K ≥ N/W です。

最小の K は N/W 以上の最小の整数、つまり N/W の端数を切り上げた整数といえます。これは (N + W - 1)/W の端数を切り捨てた結果に等しいです。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/keyence2020/submissions/9570013

B - Robot Arms

問題概要: 一直線上に N 個のロボットがある。i 番目のロボットは位置 X(i) にあり、長さ L(i) のアームを持つ。いくつかのロボットを取り除くことで、どの2つのロボットもアームが「接触」しないようにするとき、取り除かれないロボットの個数の最大値を求めよ。

接触: i 番目のロボットのアームの展開範囲を (X(i) - L(i), X(i) + L(i)) とおく。展開範囲が共通部分を持たないとき、2つのロボットのアームは接触しないとする。

B: 前提知識

区間スケジューリング問題という有名な問題があります。

区間スケジューリング問題: N 個の区間がある。いくつかの区間を削除して、どの2つの区間も共通部分を持たないようにするとき、取り除かれない区間の個数が最大になるような取り除き方を1つ求めよ。

解法: 各区間の終端をソートする。区間の終端が最左にある区間を1つ選び、それと共通部分を持つ他の区間を削除する。これを繰り返せば解ける。

理由:

終端が最左にある区間を A とし、この解法の結果として得られる区間の集合を X とします。A∈X です。
問題の解の1つを Y とします。つまり、Y は取り除かれない区間の個数が最大であるような、残された区間の集合です。
Y には少なくとも1つの区間が含まれます。その中で終端が最小であるものを B とします。A の区間の終端が最小なことから、B 以外に、Y に含まれるどの区間も A と共通部分を持ちません。そのため、Z = (Y \ {B})∪{A} も問題の解になります。
(N に関する数学的帰納法を使い、X = Z を示したいです。)
Z = {A} なら X = Z なので OK です。N=1 のときは必ずこれになります。
そうでないとき、A および A と共通部分を持つ各区間を除いて、同じ問題を考えます。帰納的に (X \ {A}) = (Z \ {A}) なので X = Z です。

参考: Spaghetti Source - 区間スケジューリング

B: 考察

これは N 個の区間 (X(i) - L(i), X(i) + L(i)) に関する区間スケジューリング問題です。

X(i) + L(i) の値が小さい順にロボットをソートして、貪欲に選べば解けます。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/keyence2020/submissions/9572817

C - Subarray Sum

問題概要: 整数 N, K, S が与えられる。整数からなる長さ N の数列 A で、以下の条件を満たすものを1つ構築せよ。

条件: 整数の組 (l, r) で、l ≤ r かつ A(l) + A(l+1) ... + A(r) = S になるようなものの個数がちょうど S 個

制約: K≤N, S≤10^9, A(i)≤10^9

C: 考察

制約 K≤N と、l = r が許されることに気づくと解けます。S を K 個並べればいいです。残りの N-K 個の要素は適当に 10^9 で埋めれば OK。

ただしエッジケースがあって、S=10^9 かつ K < N のとき、残りを 10^9 以外の数で埋める必要があります。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/keyence2020/submissions/9571265

D - Swap and Flip

問題概要: 一列に並べられた N 枚のカードが与えられる。i 番目のカードの表には整数 A(i)、裏には整数 B(i) が書かれている。以下の操作を繰り返すことで、左から順にカードの表に書かれている整数が広義単調増加になるようにしたい。これが可能が判定し、可能なら最小の操作回数を求めよ。

操作: 左から i 番目のカードと i+1 番目のカードを交換し、それぞれ裏返す。

制約:

N≤18
A(i), B(i)≤50

D: 考察

入力例5を考えてみます。上段を表、下段を裏とします。

4  46  6 38 43
33 15 18 27 37

出力例によると3回の操作で完了するらしいので、左端は 4 か 6 か 15 になる可能性が高そうです。試してみると、実は 15 が正解です。

左端の2枚を交換します。結果的には 4 を右下の 15 と交換し、46 を左下の 33 と交換すればいいです。

15 33  6 38 43
46  4 18 27 37

6 は裏返すしかなさそうです。15 → 18 で都合がよさそうなので、左から2番目と3番目を交換します。

15 18  4 38 43
46  6 33 27 37

最後に左から3番目と4番目を交換すれば完成です。カードの表側 (上段) が広義単調増加になっています。

15 18 27 33 43
46  6 38  4 37

「裏返す」操作がややこしいので、どのカードを裏返すかは決め打ちすることにします。制約から 2^N が 10^5 程度なので間に合います。

最後に裏返っていると決め打たれたカードを裏返してからソートすると、結果として得られる数列 num が分かります。後はうまくカードを交換 (裏返さない) して、この数列に一致させたいです。

やや天下りですが、選択ソートを参考にやるとうまくいきます。左から l 枚のカードは num に一致させられたとします (はじめ l = 0)。

左から l+1 番目のカードは値が num(l) であるものであり、さらに操作を繰り返して移動した結果として、裏返るかどうかが最初に決め打ちした結果と同じになるようなものです。操作回数を最小化するため、そういうカードのうち左端になるものを選び、実際に移動させます。

そうすると左から l+1 枚が num に一致するので、残りも同様にやっていけば OK。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/keyence2020/submissions/9578778