AtCoder Beginner Contest 171

コンテスト前のレート:1765
レート通りのパフォーマンスが得られる順位:604位

A - αlphabet

問題
JavaにはisUpperみたいな判定メソッドは多分存在しないと思う。
少なくとも自分は知らないので、知っている人がいたら教えてほしいです。

思考過程
  1. 入力値をchar型にして、'A' 以上 'Z' 以下ならば大文字、それ以外は小文字とする。

後から思えば、toUpperCaseで大文字に変換した結果が入力値と等しければ大文字でもよかった。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        char s = sc.next().charAt(0);
        sc.close();

        if ('A' <= s && s <= 'Z') {
            System.out.println("A");
        } else {
            System.out.println("a");
        }
    }
}

ここまで1分12秒+0ペナ。1035位。


B - Mix Juice

問題
A問題よりも考えることがなかった。

思考過程
  1. 昇順ソートして、前からK個足す。
import java.util.Arrays;
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 k = sc.nextInt();
        int[] p = new int[n];
        for (int i = 0; i < n; i++) {
            p[i] = sc.nextInt();
        }
        sc.close();

        Arrays.sort(p);
        int sum = 0;
        for (int i = 0; i < k; i++) {
            sum += p[i];
        }
        System.out.println(sum);
    }
}

ここまで2分35秒+0ペナ。843位。


C - One Quadrillion and One Dalmatians

問題
ドハマりした。
雑なやり方をして15分ほどかけて解けず、先にDとEを解いてから今度は丁寧にやって、合計45分ほどかけてようやくAC。

思考過程
  1. よくある26進数かと思って、とりあえず以下の操作を繰り返した後、リストを逆順にして出力することを考える。
    • N26で割った余りをリストに追加する。
    • N26で割った商の切り捨てに置き換える。
  2. 26の場合に答えが一桁にならないので、最初にNを1減らしてみたり、出力時に 'a' に足す値を1減らしてみたりなどするが、26, 27, 702, 703などの境界値でなかなか全ての答えが合わない。
  3. きちんと書き出してみると、1桁が26個、2桁が26^2個、3桁が26^3個、\cdotsとなる。
  4. i桁目までの文字列の合計数B_iは、B_i=\sum_{j=1}^{i}26^j(ただしi=1の場合は0)となる。
  5. 桁数Aは、N>B_iとなる最大のi+1
  6. 桁数Aが特定できれば、A-1桁までの文字列の合計数を引いて、26進数として扱える。
  7. 例えば703の場合、702(=26^1+26^2)より大きいため3桁となるが、703-702=1
  8. 'a'=0~'z'=25とすると、703は'aaa'=0としたいため、703-702-1=0としてつじつまを合わせる。
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        sc.close();

        // 思考過程4
        // 0, 26, (26 + 26^2), (26 + 26^2 + 26^3), ・・・
        List<Long> b = new ArrayList<>();
        b.add(0L);
        b.add(26L);
        long base = 26;
        while (true) {
            base *= 26;
            b.add(b.get(b.size() - 1) + base);
            if (b.get(b.size() - 1) > 1000000000000001L) {
                break;
            }
        }

        // 5、6
        int a = 0; // 答えの文字列の桁数
        for (int i = b.size() - 1; i >= 0; i--) {
            if (n > b.get(i)) {
                a = i + 1;
                n -= b.get(i);
                break;
            }
        }

        int[] c = new int[a];
        int i = 0;
        n--; // 8
        while (n > 0) {
            c[i] = (int) (n % 26);
            n /= 26;
            i++;
        }

        for (i = a - 1; i >= 0; i--) {
            char d = (char) ('a' + c[i]);
            System.out.print(d);
        }
        System.out.println();
    }
}

ABDECと解いた時点で59分05秒+0ペナ。2045位。


D - Replacing

問題
C問題を飛ばした上でここでも詰まったら絶望だったが、5分程度で解けた。

思考過程
  1. 最終的に1回出力するのではなく、クエリごとに毎回出力するので、全体を通して高速化ではなく、各クエリに対して高速に処理できる必要がある。
  2. BCに置き換える操作による合計値の変動は、「(C-B) \times (値がBである個数)」で計算できる。
  3. まず初期状態について、合計値と110^5の各値の個数を求めておき、クエリごとに適切に更新していける。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;

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());
        String[] sa = br.readLine().split(" ");
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sa[i]);
        }
        int q = Integer.parseInt(br.readLine());
        int[] b = new int[q];
        int[] c = new int[q];
        for (int i = 0; i < q; i++) {
            sa = br.readLine().split(" ");
            b[i] = Integer.parseInt(sa[0]);
            c[i] = Integer.parseInt(sa[1]);
        }
        br.close();

        // 初期化
        long[] cnt = new long[100001];
        long sum = 0;
        for (int i = 0; i < n; i++) {
            sum += a[i];
            cnt[a[i]]++;
        }

        // クエリ処理
        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < q; i++) {
            long d = (c[i] - b[i]) * cnt[b[i]];
            sum += d;
            pw.println(sum);

            cnt[c[i]] += cnt[b[i]];
            cnt[b[i]] = 0;
        }
        pw.flush();
    }
}

ABDと解いた時点で22分57秒+0ペナ。1615位。
同じタイムでCも含めて解けていたとしても既に遅そう。


E - Red Scarf

問題
4分程度で解けたのはいいが、C問題を通す前に大勢に解かれるほど簡単なのは困る・・。

思考過程
  1. 例1では、N=4の場合、2, 3, 4番目、1, 3, 4番目、1, 2, 4番目、1, 2, 3番目の要素のxorがわかっている。
  2. iについて、「i番目」が3回(奇数回)ずつ出現しているので、入力値全部のxorを取れば、全体のxorがわかる。
  3. 求めたい値は、「全体のxor」と「自身以外のxor」のxorを取ればわかる。
import java.io.BufferedReader;
import java.io.InputStreamReader;

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());
        String[] sa = br.readLine().split(" ");
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sa[i]);
        }
        br.close();

        int x = 0; // 全体のxor
        for (int i = 0; i < n; i++) {
            x ^= a[i];
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(x ^ a[i]).append(' ');
        }
        sb.deleteCharAt(sb.length() - 1);
        System.out.println(sb.toString());
    }
}

ABDEと解いた時点で27分06秒+0ペナ。915位。
順位表を確認し、F問題の正解者数は少なかったのでC問題に戻る。


F - Strivore

問題
残りの40分をかけて解けず。
全完最下位のパフォーマンスが1759で、ちょうどレート通りくらいだったので、解けさえすれば救われていた。

思考過程
  1. Sの長さをNとする。
  2. 文字を挿入する位置の組合せは、_{N+K}C_K通りあるので、作れる文字列は全部で26^K \times _{N+K}C_K通り。
  3. そこから重複を除くことを考えるが、全然わからない。
  4. 何を数えるにしても、元の文字と挿入した文字が混ざるとよくわからなくなる・・。
  5. 後から重複を除くのではなく、部分列としてSを含む数を数えればいいのでは?
  6. dp[i][j]:最終的な文字列のi文字目までで、元の文字列の内のj文字目まで消化済みの通り数」を考えてみたが、O((N+K)S)で明らかに間に合わない。

 


終結果:ABCDEの5完、59分05秒、2091位、パフォーマンス1192
レート変動:1765→1719

2日連続爆死で一気に-82。
1700前半までは落とさないとか言ったその日に落ちました。
先月結3回も構黄パフォが出ていたのは一体何だったんだろう。

とりあえずできる復習はちゃんとして、地道に弱点を減らすしかないんだろうけど。