SRM439 DIV2 過去問

点数	結果	備考
250	failed system test	resubmitしてpassed
500	compiled	後で解き直した
1000	−

250 - SquareOfDigits

問題文
『四隅が同じ数字の出来るだけ大きい正方形を探してその面積を返せ』

小さいので全部探します。
ケツから探せばその時点で値を返せることに後で気がつきました。
アホなミスしてsystem testに落ち、resubmitして129.81pt。洒落にならない遅さ

public class SquareOfDigits {
    public int getMax(String[] dat) {
        int res = 1;
	char[][] a = new char[dat.length][dat[0].length()];
	for(int i=0; i<dat.length; i++)
	    a[i] = dat[i].toCharArray();
	for(int i=0; i<a.length; i++){
	    for(int j=0; j<a[0].length; j++){
		char q = a[i][j];
		for(int k=1; ; k++){
		    if(i+k>=a.length) break;
		    if(j+k>=a[0].length) break;
		    if(q==a[i][j+k] && q==a[i+k][j] && q==a[i+k][j+k])
			res = res<((k+1)*(k+1)) ? ((k+1)*(k+1)) : res ;
		}
	    }
	}
        return res;
    }
}

500 - PouringWater

問題文

• 水1リットル入りのボトルをN個持っている。
• 水の量が同じボトル2つは、片方にまとめることができる。
• ボトルは底無しなのでいくらでも入る。
• 水入りのボトルをK個に減らしたいので、そのために必要な追加のボトルの数を返せ。

はい、無理だったので解答丸写しです。

public class PouringWater {
    public int getMinBottles(int N, int K) {
        int i = N;
	while(Integer.bitCount(i) > K){
	    ++i;
	}
	return i - N;
    }
}

もう解説読んでもどうしてこうなるのかが理解できなくて小一時間混乱していましたが、実際に手で解いてみたらあら不思議、一発で理解できました。最初からそうしろって話ですね

Examplesの(1)を考えてみます。N=13, K=2です。
この13個のボトルをまとめられるだけまとめてみると、

1. 1Lが13つ
2. 2Lが6つ、1Lが1つ
3. 4Lが3つ、1Lが1つ
4. 8Lが1つ、4Lが1つ、1Lが1つ

となり、これは13の2進表現そのまんまです。13d = 1101b
このように、立ってるビットの数がまとめた後のボトルの数となるので、それがK以下になるまで+1して探していけばおｋでした。

メモ

• くそおおおおおおおおお柔らかい頭が欲しいよおおおおおおおおおおおおお
• と愚痴っても仕方ないのでざくざく問題解いていくしかない
• Integer.bitCount() おぼえた

-