AtCoder Beginner Contest 176

ABC

コンテスト前のレート：1747
レート通りのパフォーマンスが得られる順位：575位

A - Takoyaki

問題

思考過程
  1. たこ焼きを作る回数は、X \div Nの切り上げ。（これをYとする）
  2. 1回T分かかるのがY回なので、T \times Yを求める。
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

問題

思考過程
  1. 問題文に書いてある通り、各桁の和を求めてそれが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問題。

思考過程
  1. 2人目以降について、前の人より小さければ、前の人と同じ身長に増やす。
  2. その際、増やした分を答えに加算する。
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問題と比べて一気にややこしくなった。難易度調整・・・。
ちょっと時間かかってしまったと思ったが、一発で通ったのでまあ良かったか。

思考過程
  1. 歩きで移動できる連結成分を作り、スタートからゴールまでいくつの連結成分をワープで移動するかを求める？
  2. ワープで移動できる連結成分を調べるのが大変そうなので却下。
    　
  3. 上下左右へは距離0、それ以外の5 \times 5の範囲内へは距離1で遷移するダイクストラをすれば良さそうか。
  4. しかし、頂点数10^6、辺数はさらに24倍でダイクストラをするのは計算量が心配な気がしないでもない。よく考えたら、辺の重みは0と1しかないので、01BFSでいけそう。
  5. ただし、単に上下左右に距離1で移動していくBFSとは異なり、ワープで+1の更新をしてから、歩きで+0の更新をする順番になる可能性もありそうなので、更新とキューへの追加を行う条件は、一度も更新していない場合ではなく、ダイクストラと同様に距離が縮む場合としておく。
  6. 遷移部分の実装は、現在地-2～+2の範囲で二重ループを回し、隣接マスの判定はマンハッタン距離が1であることとすれば、条件分岐を減らせそう。
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問題にしては滅茶苦茶簡単では？と思ったが、-1する必要があるのかどうかの判定に手間取った。
まあそれがこの問題の肝だろうけど・・。

思考過程
  1. 最も多くの爆破対象が存在する行と列をそれぞれ独立に求め、個数の和を求める。
  2. 例２の結果が4となり、1個重複していることに気付く。
  3. 爆破対象の個数が最大になる行も列も1箇所とは限らない。
  4. 爆弾の設置場所は、「爆破対象の個数が最大になる行の個数\times列の個数」だけ候補があり、それらの候補地全てに爆破対象が存在する場合のみ、上記1の行と列の和から1を引く必要がある。
    　
  5. 設置候補地を全て調べていたらO(HW)になってしまうが、爆破対象をベースに調べればO(M)でできそう。
  6. 爆破対象が設置候補地に入っているかどうかがわかっても、その情報がどう使えるのかよくわからない。（※実は後述の通り使える。）
  7. やっぱり設置候補地を全て調べ、爆破対象がなかった時点でそのままの値を出力。全てに爆破対象があった場合は-1した値を出力することにする。
  8. 各候補地に爆破対象があるかどうかをO(1)で判定できれば、鳩の巣原理（の逆？）により、最悪でもM+1個目に爆破対象なしのマスが見つかるので、O(M)で調べられる。
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しか下がってないし・・。
一応以下はコンテスト中に考えていた、誤った思考過程。

思考過程
  1. 一目でDPっぽい雰囲気は感じられるが、遷移がさっぱりわからない。後ろから見てもあまり変わらない気がする。実はある程度貪欲的にやれるのではないかと思って以下の考察を進める。（最終的には全否定して終わった）
  2. 同じ数字が3枚揃わない限りは何を残しておくのが最善かわからないので、全部保持したまま見ていく。
  3. まず最初に2枚を持っておき、3～5枚目、6～8枚目、\cdotsのように3枚ずつ処理していく。
  4. 新たに処理する3枚により、保持情報と合わせて3枚になったら、1点プラスしてその3枚を取り除く。
    • その際、新たな3枚の内の1枚を使った場合は、保持情報を残りの2枚のみにする。
    • 新たな3枚の内の2枚を使った場合は、既存で2枚のものを全て1枚に減らした上で、新たな3枚の内の残りの1枚を加える。
      　
  5. 保持情報と合わせて3枚になった数字が同時に複数発生した場合、どれを揃えたことにすればいいのかわからない。
  6. おまけに、最初に3枚揃った数字で1点を取らないことにより、後で2点取れるようなケースもないとは言えないのでは？

ここで破綻して終了。
　


最終結果：ABCDEの5完、43分14秒、282位、パフォーマンス2028
レート変動：1747→1778


highestまで回復するにはあと2回同じパフォ出す必要があってなかなか厳しい。Fが解ければ一発だったけど。
赤難易度ではどちらにしろ難しいとはいえ、先週以降DPの精進が進んでいないところにDPの問題が出てしまっているので、やっぱり弱点克服は早くしないと駄目かな。