kmjp's blog

競技プログラミング参加記です

yukicoder : No.540 格子点と経路

これが最大って証明可能なのかな?
https://yukicoder.me/problems/no/540

問題

矩形領域(0,0)-(W,H)中の格子点(W+1)*(H+1)個を考える。
距離1内の各格子点を線分で結び、全格子点を通るパスを作るとき、線分の数を最大化せよ。

解法

H,Wの偶奇で場合分けする。
図はEditorialを見てもらった方がいいのでここでは方針だけ示す。

  • H,Wがともに偶数の時
    • 外側から2列ずつ削り取るように渦巻き状に内側に向けて移動していく。最後は長めの線分が残る可能性がある。
  • それ以外の場合
    • 端から2列ずつ削り取るように移動していく。列を削るか行を削るかはW,Hのうち奇数がどちらかによって選ぶ。ともに奇数の場合小さい方を選ぶ。
ll W,H;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	
	ll ret=0;
	if(H%2 + W%2 == 0) {
		while(H&&W) {
			ret += 2*(W+H-1);
			W-=2;
			H-=2;
		}
		if(H||W) ret++;
	}
	else if(H%2 + W%2 == 1) {
		ret = (W+1)*(H+1) - ((H%2)?H:W);
	}
	else if(H%2 + W%2 == 2) {
		ret = (W+1)*(H+1) - min(H,W);
	}
	cout<<ret<<endl;
}

まとめ

コード長からDP等ではないとは思ったけど…。
2列ずつ削るのは思いついたけど、渦巻き状が最小か自身を持ちきれなかった。