HHKB プログラミングコンテスト 2020
コンテスト前のレート:1815
レート通りのパフォーマンスが得られる順位:473位(1100点、28分42秒)
A - Keyboard
思考過程
- が"Y"の場合、.toUpperCase。以外はそのまま。
import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); String s = sc.next(); String t = sc.next(); sc.close(); if (s.equals("Y")) { System.out.println(t.toUpperCase()); } else { System.out.println(t); } } }
ここまで0分53秒+0ペナ。71位。
B - Futon
思考過程
- 横向きと縦向きを独立に数える。
- 横向きについて数えるときは、とが共に '.' であるかどうかを調べる。
import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int h = sc.nextInt(); int w = sc.nextInt(); char[][] s = new char[h][w]; for (int i = 0; i < h; i++) { s[i] = sc.next().toCharArray(); } sc.close(); int ans = 0; // 横向き for (int i = 0; i < h; i++) { for (int j = 1; j < w; j++) { if (s[i][j - 1] == '.' && s[i][j] == '.') { ans++; } } } // 縦向き for (int i = 1; i < h; i++) { for (int j = 0; j < w; j++) { if (s[i - 1][j] == '.' && s[i][j] == '.') { ans++; } } } System.out.println(ans); } }
ここまで3分11秒+0ペナ。135位。
C - Neq Min
問題
こういう存在確認しそうな問題を見るとすぐSetを使いたくなる。けど配列で十分だった。
思考過程
- として出現した回数(出現したかどうか)を保持しておく配列を用意する。
- 毎回から順にかどうかを調べていたら、で駄目。
- 答えは広義単調増加になるので、毎回からではなく、前回の答えから調べ始めればよい。これでならしとなった。
後から思いついたが、最初に~をTreeSetに入れておき、の削除とfirst()の出力を繰り返すのでもできそう。
import java.io.PrintWriter; import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] c = new int[200001]; PrintWriter pw = new PrintWriter(System.out); int min = 0; for (int i = 0; i < n; i++) { int p = sc.nextInt(); c[p]++; while (c[min] > 0) { min++; } pw.println(min); } pw.flush(); sc.close(); } }
ここまで5分57秒+0ペナ。185位。
D - Squares
問題
10分以上頑張っても全然解けない。といったところで順位表を見たら、まだ正解者数たった30人とかしかいなかったので、じっくり考えても良さそうだとなる。(でもこの時点でEの方が正解者数多かったので、素直にEを先にやれば良かった・・。)
30分経ってもできないので、いい加減Eを先にやることに。
Eを20分くらいで通して戻ってきた後、5分だけFを見たが、それ以外をずっとDに費やしても結局解けず。
思考過程
- 例1に誘導されて、全体から重なる場合を引くことを考える。どう考えても単純な計算ではできそうにない。
- 実は重ならない場合だけを考えていけるのではないかと考え直してみる。青が上の方にあって赤が下の方にある場合を数えて倍する方向で考えてみるが、赤が左下や右下にある場合の重複を上手く取り除けず終了。真下~右下だけを数えるようにできれば、重複せず倍でいけたのだろうか・・・。
E - Lamps
思考過程
- 各マスが答えにどれだけ寄与するかを計算していく。
- とりあえず例2の '.' の各マスについて、そのマスが照らされる照明の置き場所数をカウントしてみる。
- 個のマスの内いずれか箇所以上に照明を置かれるのが通り。
- 残りの個のマスは任意なので、通り。
- これらを掛け合わせれば、マス分の答えを求められる。(手計算で例2が合うことを確認。)
- の求め方は、ABC129-D:Lampをだいたい覚えていた。(緑diffで本番中に解けなかった問題はどれも結構印象に残っているので)
- 今回は、端や直前の '#' からマスまで連続した '.' の数を方向について足し、重複分のを引くことで求めた。
- の方を見て、「'.' マスの場合は以上なので、までしかないだろう」と配列pのサイズをにしていたら、ケースREになった。(の方を見たら、はまであり得る)
import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int h = sc.nextInt(); int w = sc.nextInt(); char[][] s = new char[h][w]; for (int i = 0; i < h; i++) { s[i] = sc.next().toCharArray(); } sc.close(); int[][] c1 = new int[h][w]; // → int[][] c3 = new int[h][w]; // ↓ int k = 0; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { if (s[i][j] == '.') { k++; if (j == 0) { c1[i][j] = 1; } else { c1[i][j] = c1[i][j - 1] + 1; } if (i == 0) { c3[i][j] = 1; } else { c3[i][j] = c3[i - 1][j] + 1; } } } } int[][] c2 = new int[h][w]; // ← int[][] c4 = new int[h][w]; // ↑ for (int i = h - 1; i >= 0; i--) { for (int j = w - 1; j >= 0; j--) { if (s[i][j] == '.') { if (j == w - 1) { c2[i][j] = 1; } else { c2[i][j] = c2[i][j + 1] + 1; } if (i == h - 1) { c4[i][j] = 1; } else { c4[i][j] = c4[i + 1][j] + 1; } } } } int mod = 1000000007; long[] p = new long[k + 1]; // p[i] = 2 ^ i p[0] = 1; for (int i = 1; i <= k; i++) { p[i] = p[i - 1] * 2 % mod; } long ans = 0; for (int i = 0; i < h; i++) { for (int j = 0; j < w; j++) { int c = c1[i][j] + c2[i][j] + c3[i][j] + c4[i][j] - 3; if (c > 0) { ans += (p[c] - 1) * p[k - c] % mod; ans %= mod; } } } System.out.println(ans); } }
ここまで55分28秒+1ペナ。532位。
最終結果:ABCEの4完、60分28秒、724位、パフォーマンス1611
レート変動:1815→1796(-19)
今回の敗因は、Dもどうせ解くから慌ててEを先にやらなくてもいいやという慢心だったと思う。
あとEで、前計算の配列サイズをどうして無駄に1減らそうとしてしまったのか。
A問題が相対的に一番早くてだんたん順位が下がっていく推移も珍しい。