AtCoder Regular Contest 107 - ks2mのブログ

A - Simple Math
- 思考過程
B - Quadruple
- 思考過程
C - Shuffle Permutation
- 思考過程

コンテスト前のレート：1722
レート通りのパフォーマンスが得られる順位：631位（1200点、35分13秒）

A - Simple Math

問題
これが一瞬でわからない辺り、単純な数学はどちらかと言えば自分の弱点だと思う。

思考過程

適当に $(1,1,1), (1,1,2), \cdots$ と書き出してみたら、 $\sum_{a=1}^A \sum_{b=1}^B ab \times \sum_{c=1}^C c$ とまとめられた。
ということは結局、 $\sum_{a=1}^A a \times \sum_{b=1}^B b \times \sum_{c=1}^C c$ となり、 $\frac{A(A+1)}{2} \times \frac{B(B+1)}{2} \times \frac{C(C+1)}{2}$ を求めればよさそう。

ちょっと計算するし、3回並べるよりfor文にするかと書き換えたけど、何十秒か余計に時間かかっただけだったかもしれない。

import java.util.Scanner;

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

        long ans = 1;
        for (int i = 0; i < 3; i++) {
            ans *= a[i] * (a[i] + 1) / 2 % 998244353;
            ans %= 998244353;
        }
        System.out.println(ans);
    }
}

ここまで4分51秒＋0ペナ。1134位。

B - Quadruple

問題

思考過程

$(a+b)-(c+d)=K$ と変形してみると、適宜 $(a+b)$ と $(c+d)$ を入れ替えればので、 $K$ は絶対値を取って $0$ 以上の場合のみ考えればよい。
となるを作る方法が何通りあるかを求める。二次元表を書いて実験してみると、以下のように山なりになっている。サイコロを個振ったときのことを思い浮かべたら確かにこんな感じ。
- $i=2$ の場合 $1$ 通り
- $i=3$ の場合 $2$ 通り
- $\cdots$
- $i=N+1$ の場合 $N$ 通り
- $\cdots$
- $i=2N$ の場合 $1$ 通り
とりあえずこれを求める関数を作る。前半の増える部分は $i-1$ で、後半の減る部分は $-i+x$ の $x$ を適当にガチャガチャやって書き出した二次元表と合わせるようにして求める。
　
最初の式を $(a+b)-K=(c+d)$ と変形すると、各 $i$ について、上記3の関数を引数 $i$ と $i-K$ で呼び出し、それぞれの結果の積を答えに足していく。

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

        k = Math.abs(k);
        int n2 = n * 2;
        long ans = 0;
        for (int i = 2; i <= n2; i++) {
            if (i < k + 1) { // 最初i < kとしており、デバッグで数分ロス
                continue;
            }
            long val1 = cnt(n, i);
            long val2 = cnt(n, i - k);
            ans += val1 * val2;
        }
        System.out.println(ans);
    }

    static long cnt(int n, int i) {
        long val = i - 1;
        if (i > n + 1) {
            val = n + n + 1 - i;
        }
        return val;
    }
}

ここまで18分48秒＋0ペナ。756位。

C - Shuffle Permutation

問題
解けず。これが緑diffってどういうことですか。

思考過程

とりあえず $3 \times 3$ のマスに1～9を入れて、合計 $K$ 以下の制限はないものとして、与えられている操作を適当に行ってみる。
すると、各行内、列内の数字の順番は変わるが、内訳は変わらないことがわかる。
$K$ の制限がない場合、 $N=3$ の場合は、縦横それぞれ任意の順列にすることができ、 $(3!)^2=36$ となりそう。例１では、行の並べ替えをしようとしたときに、 $1, 3$ 行目の入れ替えしかできないため、 $(3!) \times 2=12$ となっている。
　
例１の列の並べ替えについては、 $1,2$ 列目、 $1,3$ 列目のみ入れ替え可能だが、 $1$ 列目を介すことで実質 $2,3$ 列目の入れ替えも可能になっている。
ここでUnionFindっぽさを感じはしたが、少なくとも特定の $1$ 行(列)について見たときは、その中で最小の要素との和が $K$ 以下である要素は全て、最小の要素と同一連結成分にできることになり、また、連結成分は必ず $1$ つになるはず？これが $N$ 行全体でも同様だと思い込む。
長さ $N$ のboolean型配列を用意し、初め全てtrueで初期化する。各行について、最小要素との和が $K$ より大きい列をfalseにしていく。N行分処理後、trueで残った要素数の階乗が答え。
　
行列入れ替えて求め、 $2$ つの結果の積が最終的な答え。　→9WA
添え字ミスがあったので直す。　→7WA
ベルマンフォード法と似たイメージで、 $N$ 回調べないとfalseなのにfalseにならない箇所が出るかも。　→7WA