AtCoder Grand Contest 056
コンテスト前のレート:2028
レート通りのパフォーマンスが得られる順位:336位(300点、36分11秒)
A - Three Cells per Row and Column
問題
公式解説よりだいぶ面倒な方法になった。
思考過程
1. がの倍数の時は、横につ連続したものをずらして並べていくだけ。
2. そうでないときは、つ連続はしないがとりあえず左端から続きを並べるようにしてみると、個の連結成分ができる以外は条件を満たす。
###....... ...###.... ......###. ##.......# ..###..... .....###.. #.......## .###...... ....###... .......###
3. ここから、各行各列に個ずつという条件を満たしたまま盤面を変えていくには、長方形領域の隅の内、一方の対角が両方黒でもう一方の対角が両方白になっているような箇所を以下のように入れ替える方法がある。('-'部分の内容は任意)
--.---#-- --#---.-- --------- -> --------- --#---.-- --.---#--
4. この操作を地道に繰り返すと、以下のように右端の個浮いている黒を下に動かしていくことができる。これで連結成分をつ減らせる。('o':変更箇所)
###....... ###....... ###....... ...###.... ...###.... ...###.... ......###. ......###. ......###. ##.......# ##o....... ###....... ..###..... -> ...##....o -> ...##o.... .....###.. .....###.. ......##.o #.......## #.......## #.......## .###...... .###...... .###...... ....###... ....###... ....###... .......### .......### .......###
5. 左端の個浮いている黒についても同様に上に動かしていく。
6. 上記4.の時は、右端を下に動かす代わりに上に動かす黒マスの列番号がのように完全に等差数列になるが、その操作の影響で、5.の操作をするときにはから等差数列とはいかなくなっている。
7. 確実にやるため、「黒白」の順に並んでいるところの黒を下に動かすことにする。これにかけても、全体でなので大丈夫。
###....... ###....... ###....... ...###.... ...###.... ...###.... ......###. ......###. ......###. ###....... ###....... ###....... ...###.... -> ...###.... -> o..##..... ......##.# o.....#..# .....o#..# #.......## .......o## .......### .###...... .###...... .###...... ....###... ....###... ....###... .......### .......### .......###
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.Arrays; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); br.close(); char[][] s = new char[n][n]; for (int i = 0; i < n; i++) { Arrays.fill(s[i], '.'); } int x = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < 3; j++) { s[i][x] = '#'; x = (x + 1) % n; } } if (n % 3 != 0) { for (int i = 0; i < n; i++) { // 右端の単独'#'を下に動かす if (s[i][n - 1] == '#' && s[i][n - 2] == '.') { x = 2; for (int k = i; k < n - 1; k++) { if (s[k + 1][n - 1] == '#') { break; } s[k][x] = '#'; s[k + 1][x] = '.'; s[k][n - 1] = '.'; s[k + 1][n - 1] = '#'; x += 3; } } } for (int i = 0; i < n; i++) { // 左端の単独'#'を上に動かす if (s[i][0] == '#' && s[i][1] == '.') { for (int k = i; k > 0; k--) { if (s[k - 1][0] == '#') { break; } for (int y = n - 2; y >= 0; y--) { if (s[k - 1][y] == '#' && s[k - 1][y + 1] == '.') { s[k][y] = '#'; s[k - 1][y] = '.'; s[k][0] = '.'; s[k - 1][0] = '#'; break; } } } } } } PrintWriter pw = new PrintWriter(System.out); for (int i = 0; i < n; i++) { pw.println(s[i]); } pw.flush(); } }
ここまで42分23秒+0ペナ。329位。
残り時間のほとんどはC問題に使ったが、半分くらいのケースしか通らず。
前から貪欲に可能なら'0'にする方針で頑張ろうとしたが、どうしても後から上手くいかないケースが出てきてしまった。
最終結果:Aの1完300点、42分23秒、387位、パフォーマンス1916
レート変動:2028→2017(-11)
昨日のABCといい、レート相当のパフォを得るのに最低必要な問題を通すことはできているが、早解き依存になっているので、あともう1問を解けるようにならないと出遅れた時に挽回する術がないという感じ。