SRM 596 DIV1 本番

SRM 本番

少し調子が悪かった。

Coding

Easy (250)

最初全くわからず、焦った。
なんていうか2倍の操作は共有されるけどそれ以外は独立だから全部独立に求めた後上手く合成すればいけるのでは？と考える。
とりあえずDPで(数 * 2倍を使った回数 -> 最小のインクリメント回数)を求める。
さて、それを合成するにはどうしたら…
2倍にする回数は全部で固定なのでそれを全部試せばいいんじゃね？と、解けた。
テストをしてから提出。

Medium (500)

全然わからず。とりあえず辞書順最小はN*60回判定するのでいいな、とかは考える。
なんかマッチングとかフローっぽいな、とか考えながらうまく進められずに時間が経つ。
その間にいろいろ考えた。
まず、各ビットでそれを含む数の個数は2以下である必要がある。また、各数同士の無向ペアに対して少なくとも1つビットを共有してなければいけない。つまりグラフを考えるとクリークである必要がある。
ここまでわかってもそれをどう適用したらいいかがわからず時間が経つ。そして残り25分くらいの時にやっと思いついた。
(ビット位置, 各ペア)の二部グラフを考えて、そのビット位置がそのペアに含まれることができるならそこに辺を張る。そして全てのペアを使うマッチングが存在するかどうかを判定する。
さて、どこに辺を張れるかをどのようにして決めればいいのか？これは残り10分くらいでやっと思いつけた。
まず、そのビットがこのペアのどちらか片方で既に決まっていて(subsetに含まれていたり、既に決定されている)、その値が0なら張れない。
また、このビットを既に決めている数が存在して、その数がこのペアのうちどちらでも無い場合も張れない。
あとすこし引っかかったところが。辞書順最小greedyとはいっても、(subset以外の列が辞書順最小 <-> (答え = subset∪subset以外)が辞書順最小)は成立するのか？とりえあえずは成立すると信じた。
残り5分程度。テストもしたが解法に自身が持てない。しかし時間も無くしょうがないので提出。
が、落ちた。
subsetが最初から条件を満たしてない(3要素に共通するビットがある)ケースで落ちているようだった。その判定を入れたら通った。

Challenge

greedy解法とか知らないのでEasyのgreedyっぽい人のを写して、自分のものと答えが合うことを確認しただけ。他に1人だけ落とされてた。

SystemTest

遅延らしい。さて、通るか…
Medium落ちた。うーん…

結果

Easy: 227.48 / 250
Medium: Failed System Test / 500
Challenge: 0/0 = +0
Division Place: 368 / 792
Rating: 1957→1906

コメント

練習しよう。
落ちた理由がわからなかったのは久しぶりな気がする。
テストすればわかったよなあ。「焦っていても」コーナーケースをきちんと考えてテストをするべきだ。と、テストの重要性を再認識した。もちろん、書きながら気づけたらいいのだけれど…

コード

Easy
#include <vector>
#include <cstring>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define mset(m,v) memset(m,v,sizeof(m))
#define INF 0x3f3f3f3f
using namespace std;
struct IncrementAndDoubling {
	int getMin(vector <int> desiredArray) {
		static int dp[1001][11];
		mset(dp, INF);
		dp[0][0] = 0;
		rer(i, 0, 1000) rer(j, 0, 10) {
			int x = dp[i][j];
			if(x == INF) continue;
			if(i*2 <= 1000 && j+1 <= 10) dp[i*2][j+1] = min(dp[i*2][j+1], x);
			if(i+1 <= 1000) dp[i+1][j] = min(dp[i+1][j], x + 1);
		}
		int n = desiredArray.size();
		int r = INF;
		rer(j, 0, 10) {
			int x = j;
			rep(i, n) x = min(INF, x + dp[desiredArray[i]][j]);
			r = min(r, x);
		}
		return r;
	}
};