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

https://atcoder.jp/contests/keyence2020

A
v = max(H, W)として、ceil(N/v)です。

B
区間スケジューリング。典型とは言え200はビビりました。

C
基本K個のSとN-K個のS+1で良いんですが、S=10^9の時だけN-K個の数を1にします。ギャグ。

D
個人的には解きやすかった。indexの距離の偶奇でAとBどちらを取るか決まります。あとはbitdpで前から順番に決めていけばよいです。
popcountすれば偶奇の判定も簡単です。

int N;
int dp[(1 << 18)][18];
int A[18], B[18];

void solve() {
	cin >> N;
	rep(i, 0, N) cin >> A[i];
	rep(i, 0, N) cin >> B[i];

	rep(bit, 0, (1 << 18)) {
		rep(i, 0, N) dp[bit][i] = inf;
	}

	dp[0][0] = 0;

	rep(bit, 0, (1 << N)) {
		rep(i, 0, N) {
			if(dp[bit][i] == inf) continue;
			int cnt = 0;
			rep(j, 0, N) {
				if(bit & (1 << j)) continue;
				int v = (__builtin_popcount(bit) - j + 50) % 2 == 0 ? A[j] : B[j];
				int pv = bit == 0 ? -1 : (__builtin_popcount(bit) - 1 - i + 50) % 2 == 0 ? A[i] : B[i];
				if(pv <= v) MIN(dp[bit | (1 << j)][j], dp[bit][i] + cnt);


				cnt += ((bit & (1 << j)) == 0);
			}
		}
	}
	int res = inf;
	rep(i, 0, N) MIN(res, dp[(1 << N) - 1][i]);
	if(res == inf) cout << -1 << "\n";
	else cout << res << "\n";
}

E
まず辺にどちらの頂点が大きいかで不等式をつけてみたところ、ある1点のみに小なりの符号が集中しているとできないことが
わかりました。逆に小なりの符号が集中しているのが、2点以上の等号による連結成分ならうまく行くだろうとなり、
構成法を色々考えていたんですが、コストの大きい頂点から辺を張っていくことを
ずっと考えていたせいでわかりませんでした。(小さい方からなら簡単です)でも偶然max(D_u,D_v)みたいなコストの辺で最小全域木を作る問題を
思い出したので、(https://atcoder.jp/contests/arc098/tasks/arc098_d)
それで全域木を作ってみた所、木上で2色彩色するだけになり簡単に構成できました。
1WA出したんですがこれは一箇所MとNを入れ替えていたためです…なんか木の場合を入力に入れたら都合よくバグってくれました。