Google code jam 2015 Round1B B. Noisy Neighbors

2015-05-03

15:45 |

1セルに高々1人入れる R*C のグリッドがある。ここに住人を N 人いれたとき、住人が隣り合ってる辺数の最小値を求めよ。
small 1≦R*C≦16, large 1≦R*C≦10,000

smallは全探索
largeは、半分くらいまでは色が多い市松模様状に置いてくのがよいはずで、その後はやむなく影響の少ないところから置いてけばよさげ。
具体的には、あるセルに置いた時すでに置いてあるセルとX辺で接するようなのがY個ある (X in [0, 4]) を求めておいて、X が小さい順に N から min(N, Y) を引いていく。

4x4, N in [0, 16] の small 解を眺めたところそれでよさげなので実装開始。（証明できてないけど
R*Cが偶数のときは「置くと既に置いてあるとこと2辺と接する」ようなセルが 2 コ, 3辺はその他の外周で置いてない個数, 中は 4辺, R*Cが奇数なら云々, 1x? なら云々, ... (めんどくさい
書いた

small解と比較してると、5x3, N=13 のときはもう１つの市松模様状に置かないといけないことに気づく

■■■■■
■□■□■
■■■■■
5x3, N=13→答え14

■□■□■
□■□■□
■□■□■
↑これ前提で9個目以降を□に置いて行くと答え15になってしまう

□■□■□
■□■□■
□■□■□
↑こっちだと14

市松模様を２通り試して min をとる必要があるな...（めんどくさい
手動で求めるとめんどくさいしこれはミス不可避だなぁ
R*C≦10,000だから実際に塗ってみて数えればよいのだ
0辺と接するのがY個、も同様の仕組みで数えていけばいいのか。けっこうきれいになった。

最大ケースとか入念にチェックして large download
180ケース目で Bus error →ファッ!?
(ていうかテストケース1000個だったのか)

やばいまた 8 分デバッグだ.....
VVI を char[][] に変えてみる
gdb を付けてみる → command not found (◞‸◟)

お、なぜか B-large.in に対してだけ small コードで実行していた
落ち着いて再実行して提出

Accepted

int dx[4] = {0,0,1,-1};
int dy[4] = {1,-1,0,0};

char m[10010][10010]; // 無駄
ll large(ll W, ll H, ll N) {
	if(W>H) swap(W, H);
	// W<=H

	ll ans = 1LL<<60;
	REP(eo, 2) {
		ll NN=N;

		VI n(5);
		CLEAR(m, 0);
		REP(y,H)REP(x,W) if((x+y)%2==eo) m[y+1][x+1]=1;
		REP(y,H)REP(x,W) {
			int co=0;
			REP(dir, 4) if(m[y+dy[dir]+1][x+dx[dir]+1]) co++;
			n[co]++;
		}
		ll lans = 0;
		REP(i, 5) {
			ll use = min(NN, n[i]);
			lans += use * i;
			NN -= use;
		}
		if(NN) cout<<"ERR "<<W<<" "<<H<<" "<<N<<" eo "<<eo<<endl;
		assert(NN==0);
		ans = min(ans, lans);
	}
	return ans;
}

int main() {
	int test_cases;
	cin>>test_cases;
	ll W,H,N;
	string s;
	
	REP(ttt, test_cases) {
		cin>>H>>W>>N;
		ll ans = large(W, H, N);
		cout<<"Case #"<<ttt+1<<": "<<ans<<endl;
	}
	return 0;
}

おまけ: おっちょこちょいな command line history

  766  G++ -O2 Bs.cpp && ./a.out < a.txt
  767  G++ -O2 Bs.cpp && ./a.out < a.txt
  768  G++ -O2 Bs.cpp && ./a.out < B-small-attempt0.in > try_bs.txt 
  769  diff b try_bs.txt                                              ← small解と一致確認、よかった
  770  G++ -O2 BsRef.cpp && ./a.out < B-small-attempt0.in > b         ← b が古くなってたら困るので念のため small 解の出力を更新しておこう
  771  diff b try_bs.txt                                              ← small解と一致確認、よかった
  772  G++ -O2 BsRef.cpp && ./a.out < B-large.in > obl.txt            ← largeをsmallコードで実行! ROCK! (Bus error)
  773  G++ -O2 BsRef.cpp && ./a.out < B-large.in > obl.txt            ← (Bus error) (つд⊂)ｺﾞｼｺﾞｼ
  774  G++ -O2 BsRef.cpp && ./a.out < B-large.in > obl.txt            ← (Bus error) ...???
  775  gdb ./a.out < B-large.in > obl.txt                             ← -bash: gdb: command not found (カッコわるい)
  776  G++ -O2 BsRef.cpp && ./a.out < a.txt 
  777  G++ -O2 BsRef.cpp && ./a.out < a.txt 
  778  G++ -O2 BsRef.cpp && ./a.out < a.txt                           ← cout<<"ok"<<endl; を入れてどこまで実行できてるか見るなど
  779  G++ -O2 BsRef.cpp && ./a.out < a.txt 
  780  G++ -O2 BsRef.cpp && ./a.out < a.txt 
  781  G++ -O2 BsRef.cpp && ./a.out < a.txt 
  782  G++ -O2 Bs.cpp && ./a.out < a.txt                              ← やっと気づいた(´・ω・｀)
  783  G++ -O2 Bs.cpp && ./a.out < a.txt 
  784  G++ -O2 Bs.cpp && ./a.out < B-large.in                             ← 動くじゃ〜ん
  785  G++ -O2 Bs.cpp && ./a.out < B-large.in > obl.txt 
  786  G++ -O2 Bs.cpp && ./a.out < B-small-attempt0.in > try_bs.txt 
  787  diff b try_bs.txt                                              ← 念のため念のためsmall解と一致確認、よかった