AtCoder Beginner Contest 176
コンテスト前のレート:1747
レート通りのパフォーマンスが得られる順位:575位
A - Takoyaki
思考過程
- たこ焼きを作る回数は、の切り上げ。(これをとする)
- 回分かかるのが回なので、を求める。
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 x = sc.nextInt(); int t = sc.nextInt(); sc.close(); int y = (n + x - 1) / x; System.out.println(t * y); } }
ここまで1分05秒+0ペナ。347位。
B - Multiple of 9
思考過程
- 問題文に書いてある通り、各桁の和を求めてそれがの倍数か判定する。
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(); sc.close(); int sum = 0; for (int i = 0; i < s.length(); i++) { int d = s.charAt(i) - '0'; sum += d; } if (sum % 9 == 0) { System.out.println("Yes"); } else { System.out.println("No"); } } }
ここまで2分47秒+0ペナ。565位。
C - Step
問題
今日はだいぶ簡単なC問題。
思考過程
- 人目以降について、前の人より小さければ、前の人と同じ身長に増やす。
- その際、増やした分を答えに加算する。
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[] a = new int[n]; for (int i = 0; i < n; i++) { a[i] = sc.nextInt(); } sc.close(); long ans = 0; for (int i = 1; i < n; i++) { if (a[i] < a[i - 1]) { int d = a[i - 1] - a[i]; ans += d; a[i] += d; } } System.out.println(ans); } }
ここまで4分40秒+0ペナ。314位。
D - Wizard in Maze
問題
C問題と比べて一気にややこしくなった。難易度調整・・・。
ちょっと時間かかってしまったと思ったが、一発で通ったのでまあ良かったか。
思考過程
- 歩きで移動できる連結成分を作り、スタートからゴールまでいくつの連結成分をワープで移動するかを求める?
- ワープで移動できる連結成分を調べるのが大変そうなので却下。
- 上下左右へは距離、それ以外のの範囲内へは距離で遷移するダイクストラをすれば良さそうか。
- しかし、頂点数、辺数はさらに倍でダイクストラをするのは計算量が心配な気がしないでもない。よく考えたら、辺の重みはとしかないので、01BFSでいけそう。
- ただし、単に上下左右に距離で移動していくBFSとは異なり、ワープでの更新をしてから、歩きでの更新をする順番になる可能性もありそうなので、更新とキューへの追加を行う条件は、一度も更新していない場合ではなく、ダイクストラと同様に距離が縮む場合としておく。
- 遷移部分の実装は、現在地~の範囲で二重ループを回し、隣接マスの判定はマンハッタン距離がであることとすれば、条件分岐を減らせそう。
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.Arrays; import java.util.Deque; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] sa = br.readLine().split(" "); int h = Integer.parseInt(sa[0]); int w = Integer.parseInt(sa[1]); sa = br.readLine().split(" "); int ch = Integer.parseInt(sa[0]) - 1; int cw = Integer.parseInt(sa[1]) - 1; sa = br.readLine().split(" "); int dh = Integer.parseInt(sa[0]) - 1; int dw = Integer.parseInt(sa[1]) - 1; char[][] s = new char[h][w]; for (int i = 0; i < h; i++) { s[i] = br.readLine().toCharArray(); } br.close(); int[][] d = new int[h][w]; for (int i = 0; i < h; i++) { Arrays.fill(d[i], Integer.MAX_VALUE); } Deque<Integer> que = new ArrayDeque<>(); que.add(ch * w + cw); d[ch][cw] = 0; while (!que.isEmpty()) { int cur = que.poll(); int cx = cur / w; int cy = cur % w; for (int nx = cx - 2; nx <= cx + 2; nx++) { if (nx < 0 || h <= nx) { // 範囲外 continue; } for (int ny = cy - 2; ny <= cy + 2; ny++) { if (ny < 0 || w <= ny) { // 範囲外 continue; } if (s[nx][ny] == '#') { // 壁マス continue; } if (d[nx][ny] > d[cx][cy] && Math.abs(nx - cx) + Math.abs(ny - cy) <= 1) { // 歩き d[nx][ny] = d[cx][cy]; que.addFirst(nx * w + ny); // +0の場合先頭 } else if (d[nx][ny] > d[cx][cy] + 1) { // ワープ d[nx][ny] = d[cx][cy] + 1; que.addLast(nx * w + ny); // +1の場合末尾 } } } } if (d[dh][dw] == Integer.MAX_VALUE) { System.out.println(-1); } else { System.out.println(d[dh][dw]); } } }
ここまで23分20秒+0ペナ。328位。
E - Bomber
問題
火力最大のボンバーマンのような感じ。
E問題にしては滅茶苦茶簡単では?と思ったが、する必要があるのかどうかの判定に手間取った。
まあそれがこの問題の肝だろうけど・・。
思考過程
- 最も多くの爆破対象が存在する行と列をそれぞれ独立に求め、個数の和を求める。
- 例2の結果がとなり、個重複していることに気付く。
- 爆破対象の個数が最大になる行も列も箇所とは限らない。
- 爆弾の設置場所は、「爆破対象の個数が最大になる行の個数列の個数」だけ候補があり、それらの候補地全てに爆破対象が存在する場合のみ、上記1の行と列の和からを引く必要がある。
- 設置候補地を全て調べていたらになってしまうが、爆破対象をベースに調べればでできそう。
- 爆破対象が設置候補地に入っているかどうかがわかっても、その情報がどう使えるのかよくわからない。(※実は後述の通り使える。)
- やっぱり設置候補地を全て調べ、爆破対象がなかった時点でそのままの値を出力。全てに爆破対象があった場合はした値を出力することにする。
- 各候補地に爆破対象があるかどうかをで判定できれば、鳩の巣原理(の逆?)により、最悪でも個目に爆破対象なしのマスが見つかるので、で調べられる。
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Set; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] sa = br.readLine().split(" "); int h = Integer.parseInt(sa[0]); int w = Integer.parseInt(sa[1]); int m = Integer.parseInt(sa[2]); int[] x = new int[h]; // 各行の爆破対象数 int[] y = new int[w]; // 各列の爆破対象数 // 各行について、爆破対象がある列indexの集合 List<Set<Integer>> list = new ArrayList<>(); for (int i = 0; i < h; i++) { list.add(new HashSet<>()); } for (int i = 0; i < m; i++) { sa = br.readLine().split(" "); int a = Integer.parseInt(sa[0]) - 1; int b = Integer.parseInt(sa[1]) - 1; x[a]++; y[b]++; list.get(a).add(b); } br.close(); // 1行内の爆破対象数の最大値 int xx = 0; for (int i = 0; i < x.length; i++) { xx = Math.max(xx, x[i]); } // 爆破対象数が最大である行indexの集合 Set<Integer> sx = new HashSet<>(); for (int i = 0; i < x.length; i++) { if (x[i] == xx) { sx.add(i); } } // 1列内の爆破対象数の最大値 int yy = 0; for (int i = 0; i < y.length; i++) { yy = Math.max(yy, y[i]); } // 爆破対象数が最大である列indexの集合 Set<Integer> sy = new HashSet<>(); for (int i = 0; i < y.length; i++) { if (y[i] == yy) { sy.add(i); } } for (int i : sx) { for (int j : sy) { // 爆弾設置候補地に爆破対象がない場合 if (!list.get(i).contains(j)) { System.out.println(xx + yy); return; } } } System.out.println(xx + yy - 1); } }
思考過程6の部分について、設置候補地に入っている爆破対象の数をカウントし、設置候補地の数と一致するかどうかという判定方法もあった。
import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.HashSet; import java.util.Set; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); String[] sa = br.readLine().split(" "); int h = Integer.parseInt(sa[0]); int w = Integer.parseInt(sa[1]); int m = Integer.parseInt(sa[2]); int[] a = new int[m]; int[] b = new int[m]; int[] x = new int[h]; int[] y = new int[w]; for (int i = 0; i < m; i++) { sa = br.readLine().split(" "); a[i] = Integer.parseInt(sa[0]) - 1; b[i] = Integer.parseInt(sa[1]) - 1; x[a[i]]++; y[b[i]]++; } br.close(); // xx、sx、yy、syを求めている部分は同じなので省略 int cnt = 0; for (int i = 0; i < m; i++) { // 爆破対象が設置候補地の場合 if (sx.contains(a[i]) && sy.contains(b[i])) { cnt++; } } if ((long) sx.size() * sy.size() == cnt) { System.out.println(xx + yy - 1); } else { System.out.println(xx + yy); } } }
ここまで43分14秒+0ペナ。276位。
F - Brave CHAIN
問題
順位表を見ていてだいぶ厳しいとは思っていたが、やっぱり解けず。
5完してから順位が6しか下がってないし・・。
一応以下はコンテスト中に考えていた、誤った思考過程。
思考過程
- 一目でDPっぽい雰囲気は感じられるが、遷移がさっぱりわからない。後ろから見てもあまり変わらない気がする。実はある程度貪欲的にやれるのではないかと思って以下の考察を進める。(最終的には全否定して終わった)
- 同じ数字が枚揃わない限りは何を残しておくのが最善かわからないので、全部保持したまま見ていく。
- まず最初に枚を持っておき、~枚目、~枚目、のように枚ずつ処理していく。
- 新たに処理する枚により、保持情報と合わせて枚になったら、点プラスしてその枚を取り除く。
- その際、新たな枚の内の枚を使った場合は、保持情報を残りの枚のみにする。
- 新たな枚の内の枚を使った場合は、既存で枚のものを全て枚に減らした上で、新たな枚の内の残りの枚を加える。
- 保持情報と合わせて枚になった数字が同時に複数発生した場合、どれを揃えたことにすればいいのかわからない。
- おまけに、最初に枚揃った数字で点を取らないことにより、後で点取れるようなケースもないとは言えないのでは?
ここで破綻して終了。
最終結果:ABCDEの5完、43分14秒、282位、パフォーマンス2028
レート変動:1747→1778
highestまで回復するにはあと2回同じパフォ出す必要があってなかなか厳しい。Fが解ければ一発だったけど。
赤難易度ではどちらにしろ難しいとはいえ、先週以降DPの精進が進んでいないところにDPの問題が出てしまっているので、やっぱり弱点克服は早くしないと駄目かな。