AtCoder Regular Contest 118 - ks2mのブログ

A - Tax Included Price
- 思考過程
B - Village of M People
- 思考過程
C - Coprime Set
- 思考過程
D - Hamiltonian Cycle
- 思考過程

コンテスト前のレート：2008
レート通りのパフォーマンスが得られる順位：327位（1200点、58分32秒）

A - Tax Included Price

思考過程

とりあえず愚直を実装してみて値の並びを観察する。
完全な等差数列か？と思ったが、例２が違った。
どうやら $t$ 回周期で、差の並びが繰り返されていそう。
　
1周期分を $\frac{N}{t}$ 倍して、残りの $N \% t$ 回分は1周期分愚直に求めた際の結果を使う。
微妙に合わなかったので、 $N-1$ にして帳尻を合わせる。

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);
        int t = sc.nextInt();
        int n = sc.nextInt();
        sc.close();

        List<Long> list = new ArrayList<>();
        long x = 0; // 前回値
        for (int i = 1; list.size() <= t * 2; i++) {
            long y = i * (100 + t) / 100;
            // 前回値より2以上増えた場合、間の数を追加
            for (long j = x + 1; j < y; j++) {
                list.add(j);
            }
            x = y;
        }
        x = list.get(0);
        long y = list.get(t);
        int c = (n - 1) / t;
        long v1 = list.get((n - 1) % t);
        long v2 = (y - x) * c;
        System.out.println(v1 + v2);
    }
}

ここまで16分31秒＋0ペナ。672位。

B - Village of M People

問題
そのままやろうとすると小数が出てきてしまってよくわからず、とりあえずC問題も見たところ、Cの方がすぐにできそうだったので、先にそちらを解いてから戻ってくる。
Cの後続けてDを解くことも考えたが、その時点でAC数0だったのでさすがにBからやった。

思考過程

なるべく $\frac{B_i}{M}=\frac{A_i}{N}$ に近付けたい。
これを変形すると、 $B_iN=A_iM$ 。
一旦 $B_i=\lfloor \frac{A_iM}{N} \rfloor$ としておくと、各 $B_i$ は答えの数列と同じか小さい値になるので、あとは足りない分を適切に振り分けたい。
PriorityQueueを使い、 $A_iM-B_iN$ の大きい順に $1$ ずつ加算していけば、適切に振り分けられそう。（実際は、同じ要素に $2$ 回加算することはなく、ソートして前から足りない件数分でよかったらしい？）

import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int k = sc.nextInt();
        int n = sc.nextInt();
        int m = sc.nextInt();
        Obj[] arr = new Obj[k];
        long sum = 0;
        for (int i = 0; i < k; i++) {
            Obj o = new Obj();
            o.a = sc.nextInt();
            o.b = o.a * m / n;
            o.d = o.a * m - o.b * n;
            arr[i] = o;
            if (o.d < 0) {
                throw new Exception();
            }
            sum += o.b;
        }
        sc.close();

        // am-bnの降順
        PriorityQueue<Obj> que = new PriorityQueue<>((o1, o2) -> Long.compare(o2.d, o1.d));
        for (Obj o : arr) {
            que.add(o);
        }
        long rem = m - sum;
        for (int i = 0; i < rem; i++) {
            Obj o = que.poll();
            o.b++;
            o.d = o.a * m - o.b * n;
            que.add(o);
        }

        StringBuilder sb = new StringBuilder();
        for (Obj o : arr) {
            sb.append(o.b).append(' ');
        }
        sb.deleteCharAt(sb.length() - 1);
        System.out.println(sb.toString());
    }

    static class Obj {
        long a, b, d;
    }
}

ACBと解いた時点で42分35秒＋0ペナ。157位。

C - Coprime Set

問題
類題（AGC022-B）をくじかつで5ヶ月前と1ヶ月前に解いていたおかげか、発想はすぐに出てきた。

思考過程

まず、少ない要素数で条件を満たす集合を作り、それに無影響な値を付け足していくような流れで構築したい。
小さい方から素因数 $3$ つ（ $2, 3, 5$ ）を挙げ、これらから $2$ つを選んで掛けた値（ $6, 10, 15$ ）は条件を満たす。
全要素のgcdが $1$ という条件は今後考える必要がない。
$6, 10, 15$ の倍数であれば、いずれか $2$ 要素のgcd $\gt 1$ という条件は満たせる。
$6, 10, 15$ の倍数をSetに追加してサイズを求めてみると、 $2600$ 以上はあったので、左記の $3$ つとそれ以外の $N-3$ 個を出力する。

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

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

        Set<Integer> set = new HashSet<>();
        for (int i = 16; i <= 10000; i++) {
            if (i % 6 == 0 || i % 10 == 0 || i % 15 == 0) {
                set.add(i);
            }
        }

        StringBuilder sb = new StringBuilder();
        sb.append("6 10 15");
        Integer[] arr = set.toArray(new Integer[0]);
        for (int i = 0; i < n - 3; i++) {
            sb.append(' ').append(arr[i]);
        }
        System.out.println(sb.toString());
    }
}

ACと解いた時点で27分51秒＋0ペナ。88位。

D - Hamiltonian Cycle

問題
AtCoder Problemsによると、自分のレートで解ける可能性は15％しかない橙diff問題。
C問題までで十分な結果になりそうだったので、途中で離脱してもいいくらいに思っていたが、一応まったり続けていたら通すことができた。
しばらくE問題をやっていた後に戻ってきたので、この問題にかけた時間は40分くらい。

思考過程

例１で、まずは $4$ 倍し続けた場合と $5$ 倍し続けた場合の数列を見てみると、それだけでは構築できておらず、 $a$ 倍と $b$ 倍を織り交ぜて構築しなければならないケースもあるとわかる。
　
行方向に $1, a, a^2, \cdots$ 、列方向に $1, b, b^2, \cdots$ を取り、中身にそれらの積を記入した二次元表を作ってみると、表内の $1$ が書かれている箇所から始めて、 $4$ 方向への移動を繰り返して一筆書きで各値を一度ずつ通って $1$ に戻ってくる経路を構築する問題になった。
　
このグリッドをBFSやDFSで移動させて経路を探すのは難しそう。
よく見ればグリッド内の値の並びには周期性があり、また、いくつか入力を変えてみても、長方形の領域内に $1$ ～ $P-1$ が $1$ 個ずつ存在している箇所を見つけられる。
とりあえず、 $P-1$ の約数を全列挙し、 $1$ が書かれたマスを左上とした全パターンの長方形（ $1 \times (P-1), 2 \times \frac{P-1}{2}, \cdots$ ）について、条件を満たすものがあれば"Yes"とすることにする。（長方形の領域が存在せずに構築できるケースが本当にないかどうかは知らない）
　
あとは、公式解説の方法１のような経路を実装する。

2ペナは、何故か約数列挙を $\sqrt{N}$ までにしてしまったのと、同じ実装を縦横で2回書いてしまって後から手直ししていたら片方直し忘れ。

import java.util.ArrayList;
import java.util.LinkedHashSet;
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);
        int p = sc.nextInt();
        int a = sc.nextInt();
        int b = sc.nextInt();
        sc.close();

        long ma = modinv(a, p);
        long mb = modinv(b, p);
        int p1 = p - 1;
        List<Integer> list = divList(p1);
        for (int x : list) {
            int y = p1 / x;
            LinkedHashSet<Long> ans = new LinkedHashSet<>();
            long now = 1;
            ans.add(1L);
            if (x == 1) {
                for (int i = 1; i < y; i++) {
                    now = now * b % p;
                    ans.add(now);
                }
            } else if (y == 1) {
                for (int i = 1; i < x; i++) {
                    now = now * a % p;
                    ans.add(now);
                }
            } else {
                if (x % 2 == 0) {
                    // 作る経路
                    // 1 20 19 18 17
                    // 2 13 14 15 16
                    // 3 12 11 10  9
                    // 4  5  6  7  8
                    // 経路2～4
                    for (int i = 1; i < x; i++) {
                        now = now * a % p;
                        ans.add(now);
                    }
                    // 経路5
                    now = now * b % p;
                    ans.add(now);
                    for (int i = x - 1; i >= 0; i--) {
                        if (i % 2 == 1) {
                            // 経路6～8、14～16
                            for (int j = 2; j < y; j++) {
                                now = now * b % p;
                                ans.add(now);
                            }
                        } else {
                            // 経路10～12、18～20
                            for (int j = 2; j < y; j++) {
                                now = now * mb % p;
                                ans.add(now);
                            }
                        }
                        if (i > 0) {
                            // 経路9, 13, 17
                            now = now * ma % p;
                            ans.add(now);
                        }
                    }
                } else {
                    // 作る経路
                    //  1  2  3 4
                    // 20 13 12 5
                    // 19 14 11 6
                    // 18 15 10 7
                    // 17 16  9 8
                    for (int i = 1; i < y; i++) {
                        now = now * b % p;
                        ans.add(now);
                    }
                    now = (int) ((long) now * a % p);
                    ans.add(now);
                    for (int i = y - 1; i >= 0; i--) {
                        if (i % 2 == 1) {
                            for (int j = 2; j < x; j++) {
                                now = now * a % p;
                                ans.add(now);
                            }
                        } else {
                            for (int j = 2; j < x; j++) {
                                now = now * ma % p;
                                ans.add(now);
                            }
                        }
                        if (i > 0) {
                            now = now * mb % p;
                            ans.add(now);
                        }
                    }
                }
            }
            if (ans.size() == p - 1) {
                System.out.println("Yes");
                StringBuilder sb = new StringBuilder();
                for (long e : ans) {
                    sb.append(e).append(' ');
                }
                sb.append(1);
                System.out.println(sb.toString());
                return;
            }
        }
        System.out.println("No");
    }

    // 以下ライブラリ

    // nの約数を列挙
    static List<Integer> divList(int n) {
        List<Integer> list = new ArrayList<>();
        int end = (int) Math.sqrt(n);
        for (int i = 1; i <= end; i++) {
            if (n % i == 0) {
                list.add(i);
            }
        }
        int i = end * end == n ? list.size() - 2 : list.size() - 1;
        for ( ; i >= 0; i--) {
            list.add(n / list.get(i));
        }
        return list;
    }

    // aのmod mでの逆元
    static long modinv(long a, int m) {
        long b = m;
        long u = 1;
        long v = 0;
        long tmp = 0;

        while (b > 0) {
            long t = a / b;
            a -= t * b;
            tmp = a;
            a = b;
            b = tmp;

            u -= t * v;
            tmp = u;
            u = v;
            v = tmp;
        }

        u %= m;
        if (u < 0) u += m;
        return u;
    }
}

ここまで113分54秒＋2ペナ。108位。

Eは包除原理をすることを考えてはいたが（'#'がない場合の通り数 $-$ '#'を $1$ つ通る通り数 $+$ $2$ つ通る・・・）、せいぜい $-1$ がない場合ならなんとなく方針が立った気がしたかもくらい。
Fは一応ページを開いたくらいで問題をまともに読んでもいない。

最終結果：ABCDの4完、123分54秒、112位、パフォーマンス2468
レート変動：2008→2064（+56）

3完で終わっていたとしても216位でパフォ2206だった。
途中Eに浮気しなければDがあと30分ほど早くて、パフォ2700台もあり得た可能性が・・・とか言うのはさすがに欲張りかな。
青落ちを回避しただけでも上出来なので。

本番中の橙diffACが2問目で、前回通したのも構築問題だったので、アイディア次第で通せる可能性のある問題は夢があるなと思った。
なお、これまでの本番中の黄diffACは約70問中9問で、青diffACは約90問中34問。（母数は初参加の2019/1/13以降の問題数）
まだまだ青diffの正答率が低いのでどうにかしていきたい。