Kasasagi’s memorandum

JavaとかProcessingとか。最近はAtcoderとか。

Atcoder Grand Contest021のC問題

お久しぶりです。かささぎです。

テストとかテストとかテストが忙しく、なかなか書けませんでした。



最近Atcoderで競プロの練習をしています。といってもガチ勢ではないので、アルゴリズムのあれこれは分かりません。bitDPもビームサーチもできません。

こういう経緯もあり、500点以上の問題を解けた試がありません。そこで普段は300点までの問題をサッと解いた後、解けそうor面白そうな問題に挑戦しています。



今回開催されたAtcoder Grand Contest021は、A問題が300点、B問題が600点...となっており、A問題を解いた後、問題を眺めて、C問題を解くことにしました。私は浮動小数演算弱者なので、B問題は諦めました。



問題はこちら。

f:id:yh9092:20180224235739p:plain
f:id:yh9092:20180224235803p:plain



敷き詰め系の問題ですね。

要はN*Mのタイルに、1*2のタイルA枚と2*1のタイルB枚を全て張り付けられるかって問題です。

この問題では、2*2のマスに縦長のタイル2枚または、横長のタイル2枚を置けることを軸として考えました。NやMが偶数であれば2*2の範囲を複数で埋められます(たとえば4*6のマスなら2*2が2つ*3つの集まりであると考えられます)。

NやMが奇数なら、一番端の列に敷き詰められるだけ敷き詰めて、N-1やM-1の偶数にして、敷き詰めていく方法をとりました。

Gistにコードを乗っけときます。コメントも何もないうえ、殴り書きなので、あまり参考にはならないと思います。

Atcoder Regular Contest 021 C

実行結果は安定のWAでした。

テストケース105個中、
AC:85
WA:16
TLE:4
でした。

コードを見ると、端に敷き詰めていく際に、タイルがなくなっても敷き詰めていたので、条件を追加。
また、メインの処理はO(nm)で、n,m<=1000より、2secの制限時間を超えるのはおかしいと思っていたのですが、この原因はchar型の二次元配列のデータを、1つづつprintしていたからでした。System.out.print関数は普通の処理に比べやや重いです。プロコンで学んだ数少ない教訓の一つです。

そこでアウトプットするコードをこのように変更。gistでは99行目からです。

 for(int n=0;n<N;n++){
    String st="";
    for(int m=0;m<M;m++){
	st += map[n][m];
    }
    System.out.println(st);
 }

この二つの変更を加え、再提出。結果、

f:id:yh9092:20180225002407p:plain

もう見た。

テストケース105個中、
AC:94
WA:6
MLE:5
でした。
なぜMLE?は?ってなったんですが、先ほどのアウトプット処理のString型の変数にどんどんchar型の文字を追加したからでしょうね。
ということで、TLEとMLEどちらも起こらないように、バランスをとってこんな感じに変更。

  for(int n=0;n<N;n++){
        String st="";
	for(int m=0;m<M;m++){
		st += map[n][m];
 
		if(m%64 == 63){
		   System.out.print(st);
		   st = "";
		}
	}
	System.out.print(st);
	System.out.println();
  }

stの文字数を64文字までに制限しました。
すると、MLEのところはACとなりました。

まとめるとこんな感じ。
f:id:yh9092:20180225003502p:plain

実行時間とメモリ容量のトレードオフは大切だと実感しました(こなみ)。

いい感じになりましたが、WAは6個残っているままタイムアップ。6/105なんで、たぶんなにか一つアルゴリズム的に間違っているんでしょう。
やっぱり900点問題は難しかったよ。

Atcoderの高得点問題を解けるようになるため、これからも続けていきます。
それでは。



P.S.

来月東京行くので、おいしい店教えてください。