AtCoder Grand Contest 047

AtCoderやり始めて以来、初めてNoSub撤退をした。
というか提出する以前に、まずコードを書き始められるほど考察が進んだ問題がなかった。

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

A - Integer Product

問題
20分ほど考えて解けず。下記思考過程の4まで。その後は700点か800点のいずれかが解けたら戻ってくるつもりだったが、どれも解けなかったのでそのまま放置。
続きはコンテスト後に「二次元累積和」と聞いてから解いた時のもの。

思考過程

1. を最低何倍したら整数になるのかを知りたいが、小数のままではよくわからないので、整数で扱いたい。
2. をすると、数の積がで割り切れるかどうかを調べればよくなる。
3. を素因数分解した時のとの指数とを求めておくと、かつを満たすペアの個数を数える問題になる。
4. 仮にの判定だけでよければ、と変形できるので、各について二分探索すれば、条件を満たすの個数がわかり、全体でで解けそう。
   　
5. 条件を満たすの個数を求める際、二分探索ではなく累積和を使えば、二次元に拡張することができる。
6. ()を二次元平面上にプロットし、二次元累積和を取る。
7. かつの個数を知りたいので、これはある点から右上の領域の個数を知りたいということで、座標が大きい方からの累積和を取った方が都合が良い。
8. が最大いくつになるかだが、くらいだと思うので適当にくらいの配列を確保しておく。
9. 各について上記7の個数（累積和内に自身が含まれる場合は）を求め、その総和をで割る（と入れ替え分）。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.math.BigDecimal;

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

        // 2と5の指数を求める
        BigDecimal b = BigDecimal.valueOf(1000000000);
        int[] c2 = new int[n];
        int[] c5 = new int[n];
        for (int i = 0; i < n; i++) {
            long v = a[i].multiply(b).longValue();
            while (v % 2 == 0) {
                v /= 2;
                c2[i]++;
            }
            while (v % 5 == 0) {
                v /= 5;
                c5[i]++;
            }
        }

        // 後ろから二次元累積和
        int[][] sum = new int[50][50];
        for (int i = 0; i < n; i++) {
            sum[c2[i]][c5[i]]++;
        }
        for (int i = 49; i >= 0; i--) {
            for (int j = 48; j >= 0; j--) {
                sum[i][j] += sum[i][j + 1];
            }
        }
        for (int i = 48; i >= 0; i--) {
            for (int j = 49; j >= 0; j--) {
                sum[i][j] += sum[i + 1][j];
            }
        }

        long ans = 0;
        for (int i = 0; i < n; i++) {
            int m2 = Math.max(18 - c2[i], 0);
            int m5 = Math.max(18 - c5[i], 0);
            ans += sum[m2][m5]; // 条件を満たす個数をプラス
            if (m2 <= c2[i] && m5 <= c5[i]) {
                ans--; // 自身（i=jとなる場合）をマイナス
            }
        }
        System.out.println(ans / 2);
    }
}

B - First Second（2020/8/12追記）

問題
公式解説を見たりTrie（トライ）木を調べたりしてACしたのでメモ。

解法

1. 扱いやすいように、入力の文字列を反転させる。
2. Trie木を構築する。その際、各ノードにアクセスするための情報も残しておく。（1つ手前のノードにアクセスできるようにしておくと都合が良い）
   

   

   例２についてTrie木構築後（下記ソースの前半部分実行後）のイメージ

3. が問題の条件を満たすためには、から末尾文字を除いた文字列がのPrefixになっており、のPrefix部分より後にの末尾の文字が含まれている必要がある。
   例えば例１（文字列反転後）の「xyxcba」と「xyc」では、先頭が「xy」で一致しており、それより後の「xcba」に「c」が含まれているので条件を満たす。
4. 各について後ろから、上記3を満たすが存在するか調べていく。
   「xyxcb」の次に「a」の終端ノードがあるか
   「xyxc」の次に「a」or「b」の終端ノードがあるか
   「xyx」の次に「a」or「b」or「c」の終端ノードがあるか
   　・・・
5. 上記4の最初で自身がヒットするので、その分を引く。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

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());
        char[][] s = new char[n][];
        for (int i = 0; i < n; i++) {
            s[i] = new StringBuilder(br.readLine()).reverse().toString().toCharArray(); // 1
        }
        br.close();

        // 2
        int[][] num = new int[n][];
        List<Node> trie = new ArrayList<>();
        trie.add(new Node(' '));
        for (int i = 0; i < n; i++) {
            num[i] = new int[s[i].length];
            int idx = 0;
            for (int j = 0; j < s[i].length; j++) {
                num[i][j] = idx;
                char c = s[i][j];
                Node o = trie.get(idx);
                idx = o.next.getOrDefault(c, 0);
                if (idx == 0) {
                    idx = trie.size();
                    o.next.put(c, idx);
                    trie.add(new Node(c));
                }
            }
            trie.get(idx).end = true;
        }

        // 4
        int ans = 0;
        for (int i = 0; i < n; i++) {
            Set<Character> set = new HashSet<>();
            for (int j = s[i].length - 1; j >= 0; j--) {
                set.add(s[i][j]);
                Map<Character, Integer> map = trie.get(num[i][j]).next;
                for (char c : set) {
                    int idx = map.getOrDefault(c, 0);
                    if (trie.get(idx).end) {
                        ans++;
                    }
                }
            }
        }
        System.out.println(ans - n); // 5
    }

    static class Node {
        char c;
        Map<Character, Integer> next = new HashMap<>();
        boolean end;

        public Node(char c) {
            this.c = c;
        }
    }
}

Trie木を知ることができたのは収穫。
本番時、知識不足を感じて粘らずに放棄した判断は正しかったらしい。
　

A～Dを各20分ずつくらい考えた後、残りの1時間程度はEの部分点狙いをしていた。
E問題はちゃんとテストすればWA出す可能性は低そうだったので、レートを意識するなら、1問も解けてない状態で狙うのはこの問題だと思っていた。解けなかったけど。

それにしても、本当にAGCがどんどんできなくなってる。
とはいえ、1年前の自分に解けるかと言えばもっと無理だとは思うのだが・・。