Atcoder Grand Contest021のC問題
お久しぶりです。かささぎです。
テストとかテストとかテストが忙しく、なかなか書けませんでした。
最近Atcoderで競プロの練習をしています。といってもガチ勢ではないので、アルゴリズムのあれこれは分かりません。bitDPもビームサーチもできません。
こういう経緯もあり、500点以上の問題を解けた試がありません。そこで普段は300点までの問題をサッと解いた後、解けそうor面白そうな問題に挑戦しています。
今回開催されたAtcoder Grand Contest021は、A問題が300点、B問題が600点...となっており、A問題を解いた後、問題を眺めて、C問題を解くことにしました。私は浮動小数演算弱者なので、B問題は諦めました。
問題はこちら。
敷き詰め系の問題ですね。
要は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); }
この二つの変更を加え、再提出。結果、
もう見た。
テストケース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となりました。
まとめるとこんな感じ。
実行時間とメモリ容量のトレードオフは大切だと実感しました(こなみ)。
いい感じになりましたが、WAは6個残っているままタイムアップ。6/105なんで、たぶんなにか一つアルゴリズム的に間違っているんでしょう。
やっぱり900点問題は難しかったよ。
Atcoderの高得点問題を解けるようになるため、これからも続けていきます。
それでは。
P.S.
来月東京行くので、おいしい店教えてください。