AtCoder Beginner Contest 276(Rated範囲外)

A - Rightmost
- 思考過程
B - Adjacency List
- 思考過程
C - Previous Permutation
- 思考過程
D - Divide by 2 or 3
- 思考過程
E - Round Trip
- 思考過程
F - Double Chance
- 思考過程

コンテスト前のレート：2000
（Ratedだとしたら）レート通りのパフォーマンスが得られる順位：305位（2000点、56分02秒）

A - Rightmost

思考過程

$S$ を後ろから調べていき、'a'だった時点で位置を出力して終了。
最後まで終了しなければ $-1$ 。

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().toCharArray();
        sc.close();

        for (int i = s.length - 1; i >= 0; i--) {
            if (s[i] == 'a') {
                System.out.println(i + 1);
                return;
            }
        }
        System.out.println(-1);
    }
}

ここまで1分02秒＋0ペナ。178位。

B - Adjacency List

問題

思考過程

グラフ問題をやる時のようにとりあえず入力を隣接リストで受け取る。
各行をソートしてから出力する。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

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 n = Integer.parseInt(sa[0]);
        int m = Integer.parseInt(sa[1]);
        List<List<Integer>> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            list.add(new ArrayList<>());
        }
        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;

            list.get(a).add(b);
            list.get(b).add(a);
        }
        br.close();

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < n; i++) {
            List<Integer> li = list.get(i);
            Collections.sort(li);
            StringBuilder sb = new StringBuilder();
            sb.append(li.size());
            for (int e: li) {
                sb.append(' ').append(e + 1);
            }
            pw.println(sb.toString());
        }
        pw.flush();
    }
}

ここまで4分20秒＋0ペナ。652位。

C - Previous Permutation

問題
筋の悪い実装の仕方をしていそう。実装やや手間取ってしまった。
C++ならnext_permutationを上手く使って簡単なんだろうな・・・。

思考過程

例２を見ると、後ろから調べて初めて増加している箇所 $i$ を特定し、 $i$ より後ろにある $P_i$ より小さい数の内最大のものを位置 $i$ に置き、残りを降順に並べればよさそう。
実際例２の後ろ $5$ つを見て、 $3$ から始まる最小の数列の $1$ つ前は $2$ から始まる最大の数列と考えれば間違ってはなさそう。

なお、nextPermutationメソッドは一応自作してあったことを終わった後に思い出し、実はそれを使えば入力を $-1$ 倍してnextPermutationして $-1$ 倍して出力するだけだった。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

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

        int[] a = new int[n];
        for (int i = n - 1; i > 0; i--) {
            // 初めて増加している箇所
            if (p[i - 1] > p[i]) {
                // 増加している箇所の手前までは元の順列通り
                for (int j = 0; j < i - 1; j++) {
                    a[j] = p[j];
                }
                // p[i - 1]より小さい内の最大を探す
                int x = 0;
                for (int j = n - 1; j >= i; j--) {
                    if (p[j] < p[i - 1]) {
                        a[i - 1] = p[j];
                        x = j;
                        break;
                    }
                }

                // 残りを一旦リストに入れてソート
                int k = n - 1;
                List<Integer> list = new ArrayList<>();
                for (int j = i; j < n; j++) {
                    if (k == x) {
                        k--;
                    }
                    list.add(p[k]);
                    k--;
                }
                Collections.sort(list);

                // リストから降順に取り出して設定
                k = list.size() - 1;
                for (int j = i; j < n; j++, k--) {
                    a[j] = list.get(k);
                }
                break;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(a[i]).append(' ');
        }
        sb.deleteCharAt(sb.length() - 1);
        System.out.println(sb.toString());
    }
}

ここまで14分59秒＋0ペナ。1174位。

D - Divide by 2 or 3

問題

思考過程

目指す値は $A$ の最大公約数になりそう。
各 $a_i$ について、最大公約数で割った後回数をカウントしながら $2, 3$ で割れるだけ割る。 $1$ にならなければ達成不可。

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 g = 0;
        for (int i = 0; i < n; i++) {
            g = gcd(g, a[i]);
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            a[i] /= g;
            while (a[i] % 2 == 0) {
                a[i] /= 2;
                ans++;
            }
            while (a[i] % 3 == 0) {
                a[i] /= 3;
                ans++;
            }
            if (a[i] > 1) {
                System.out.println(-1);
                return;
            }
        }
        System.out.println(ans);
    }

    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

ここまで18分30秒＋0ペナ。544位。

E - Round Trip

問題

思考過程

$S$ から上→右→下→左のような最短ルートであっても長さ $4$ 以上の条件を満たすことをしっかり確認する。
$S$ の上下左右を始点として訪問済みマスに始点を記録しながらBFSを行い、別の始点を記録済みのマスにたどり着くことがあればサイクルを検出できていそう。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;

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]);
        char[][] g = new char[h][w];
        for (int i = 0; i < h; i++) {
            g[i] = br.readLine().toCharArray();
        }
        br.close();

        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};
        int s = 0;
        label:
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (g[i][j] == 'S') {
                    s = i * w + j;
                    break label;
                }
            }
        }

        int[] c = new int[h * w]; // sの上下左右のどこからたどり着いたかを記録
        Arrays.fill(c, -1);
        c[s] = s;
        Queue<Integer> que = new ArrayDeque<>();
        for (int i = 0; i < 4; i++) {
            int nx = s / w + dx[i];
            int ny = s % w + dy[i];
            if (nx < 0 || h <= nx || ny < 0 || w <= ny || g[nx][ny] == '#') {
                continue;
            }
            int next = nx * w + ny;
            if (c[next] == -1) {
                que.add(next);
                c[next] = next;
            }
        }
        while (!que.isEmpty()) {
            int cur = que.poll();
            int cx = cur / w;
            int cy = cur % w;
            for (int i = 0; i < 4; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];
                if (nx < 0 || h <= nx || ny < 0 || w <= ny || g[nx][ny] == '#') {
                    continue;
                }
                int next = nx * w + ny;
                // nextが未訪問
                if (c[next] == -1) {
                    que.add(next);
                    c[next] = c[cur];
                // nextに既に別の始点からたどり着いている
                } else if (c[next] != s && c[next] != c[cur]) {
                    System.out.println("Yes");
                    return;
                }
            }
        }
        System.out.println("No");
    }
}

ここまで29分11秒＋0ペナ。227位。

F - Double Chance

問題
オーバーフローの見落としで8分＋2ペナのロス。

思考過程

二次元表を書いてみると、 $i$ 枚から $2$ 回取り出す $i^2$ 通りの内、最も小さい値となるのが $1$ 通り、 $2$ 番目に小さい値が $3$ 通り、 $3$ 番目が $5$ 通り、 $\cdots$ となる。
$i$ 番目までについて上記の総和を求め、 $i^2$ で割ることで期待値を求めることを考える。
新しい要素 $A_i$ が増えた時に総和の差分がどうなるかを実験する。
　
$A_i$ の寄与分は、 $A_i$ 以下の要素が $x$ 個あるとすると $(2x+1) \times A_i$ となる。
既に存在する要素で $A_i$ より大きいものについては、小さい順で $1$ つ後ろにずれることで一律 $2$ 通り分ずつ増える。
これらは、個数を管理するセグ木と値を管理するセグ木を用意することで求められる。（値の方は初め区間加算が必要？と思って遅延セグ木を持ち出したりもしていたが $1$ 点加算だけでよかった）
　
大半のケースがWAになってしまったが、例２が合っていて解法が間違っているとは考えにくい。
値のセグ木でオーバーフローしていそうなので対策するがWA数変わらず。
さらに見直して $i^2$ がオーバーフローしていると気付き修正する。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.function.BinaryOperator;
import java.util.function.Predicate;

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 m = 200001;
        int mod = 998244353;
        long sum = 0;
        SegTree<Integer> stc = new SegTree<>(m, 0, (v1, v2) -> v1 + v2);
        SegTree<Long> stv = new SegTree<>(m, 0L, (v1, v2) -> v1 + v2); // 8

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < n; i++) {
            // 4
            int num = i - stc.prod(a[i] + 1, m);
            long v1 = (long) (num * 2 + 1) * a[i];
            // 5
            long v2 = stv.prod(a[i] + 1, m) * 2;
            sum += v1 + v2;
            sum %= mod;

            long mi = modinv((long) (i + 1) * (i + 1), mod); // 9
            long ans = sum * mi % mod;
            pw.println(ans);

            stc.set(a[i], stc.get(a[i]) + 1);
            stv.set(a[i], stv.get(a[i]) + a[i]);
        }
        pw.flush();
    }

    // 以下ライブラリ

    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;
    }
}

// 以下ACLを移植したSegTree