AtCoder Beginner Contest 190 - suisen のブログ

f:id:suisen_kyopro:20210130213637p:plain

2 連続橙 perf で黄色復帰！！めでたい．

A - Very Very Primitive Game

$A\gt B$ なら高橋君の勝ち
$A\lt B$ なら青木君の勝ち
$A=B$ なら $C=0$ のとき青木君， $C=1$ のとき高橋君の勝ち

int a = sc.nextInt();
int b = sc.nextInt();
int c = sc.nextInt();
if (a > b) {
    pw.println("Takahashi");
} else if (b > a) {
    pw.println("Aoki");
} else {
    pw.println(c == 0 ? "Aoki" : "Takahashi");
}

B - Magic 3

$X _ i \lt S$ かつ $Y _ i \gt D$ を満たす $i$ が存在すれば Yes, そうでなければ No．

int n = sc.nextInt();
long s = sc.nextLong();
long d = sc.nextLong();
boolean ok = false;
for (int i = 0; i < n; i++) {
    long x = sc.nextLong();
    long y = sc.nextLong();
    ok |= x < s && y > d;
}
pw.println(ok ? "Yes" : "No");

C - Bowls and Dishes

$K$ 人の人がそれぞれ $C_i$ と $D_i$ のどちらに置くかの $2 ^ K$ 通りを全探索し，幾つの条件が満たされているかを愚直に数えてその最大値を求めればよい．これは全体 $O(2 ^ K (N+K+M))$ で計算できる．

int n = sc.nextInt();
int m = sc.nextInt();
int[] a = new int[m];
int[] b = new int[m];
for (int i = 0; i < m; i++) {
    a[i] = sc.nextInt() - 1;
    b[i] = sc.nextInt() - 1;
}
int k = sc.nextInt();
int[][] cd = new int[k][2];
for (int i = 0; i < k; i++) {
    cd[i][0] = sc.nextInt() - 1;
    cd[i][1] = sc.nextInt() - 1;
}
int max = 0;
for (int s = 0; s < 1 << k; s++) {
    boolean[] put = new boolean[n];
    for (int i = 0; i < k; i++) {
        put[cd[i][(s >> i) & 1]] = true;
    }
    int cnt = 0;
    for (int i = 0; i < m; i++) {
        if (put[a[i]] && put[b[i]]) cnt++;
    }
    max = Math.max(max, cnt);
}
pw.println(max);

D - Staircase Sequences

初項 $A$ ，公差 $D$ ，項数 $X$ の等差数列の和は $\dfrac{1}{2}X(2A+(X-1)D)$ である．いま， $D=1$ で固定なので， $N=\dfrac{1}{2}X(2A+X-1)$ を満たす整数 $A$ , $X$ の組の個数が求まればよい．ただし， $X$ は項数なので $X\gt 0$ である．

両辺に $2$ を掛けてやると，条件式は $2N=X(2A+X-1)$ と書き直せるので， $X$ の値としてあり得るのは $2N$ の正の約数のみであることが分かる．

$X$ を $2N$ の約数として， $Y=2N/X$ と置くと $Y$ もまた整数であり， $Y=2A+X-1$ が成り立つ．これを $A$ について解くと， $A=\dfrac{1}{2}(Y-X+1)$ となるので， $Y-X+1$ が偶数であれば $A$ は整数となり条件を満たす．( $A$ の範囲に関する制約は存在しない)

$\sqrt{2N}$ まで試し割りして約数を列挙すれば，全体 $O(\sqrt{N})$ で解くことが出来る．

long n = sc.nextLong() * 2;
long cnt = 0;
for (long x : MathUtil.divisors(n)) {
    long y = n / x;
    cnt += 1 ^ ((y - x + 1) & 1);
}
pw.println(cnt);

E - Magical Ornament

少し隠されてはいるが，TSP を解けばよいことが分かる．

辺 $(A_i, B_i)$ を張ったグラフを作って各 $s=1,\dots,K$ に対して $C_s$ を始点に BFS を行うことで，任意の $1\leq s\lt t\leq K$ に対して $C_s,C_t$ を結ぶ最短経路長 $w(s,t)$ が求まる．

あとは， $1\leq s\lt t\leq K$ に対して重み $w(s,t)$ の辺を張ったグラフに対して TSP を解けば OK．答える列の長さは経路長 +1 となるのでそこだけ注意する． $K$ 回の BFS と TSP を合わせると，全体の計算量は $O((N+M)K+2 ^ KK ^ 2)$ ．

実装量は少し多いが，すべて典型的な実装なのでさほど大変ではないと思う．

int n = sc.nextInt();
int m = sc.nextInt();
IntArrayList[] _g = new IntArrayList[n];
for (int i = 0; i < n; i++) {
    _g[i] = new IntArrayList();
}
for (int i = 0; i < m; i++) {
    int u = sc.nextInt() - 1;
    int v = sc.nextInt() - 1;
    _g[u].add(v);
    _g[v].add(u);
}
int[][] g = new int[n][];
for (int i = 0; i < n; i++) {
    g[i] = _g[i].toArray();
}
int k = sc.nextInt();
int[] c = sc.ints(k, e -> e - 1);

// BFS
int[][] ds = new int[k][n];
for (int i = 0; i < k; i++) {
    int[] d = ds[i];
    IntDeque dq = new IntDeque();
    Arrays.fill(d, -1);
    d[c[i]] = 0;
    dq.addLast(c[i]);
    while (dq.size() > 0) {
        int u = dq.removeFirst();
        for (int v : g[u]) {
            if (d[v] >= 0) continue;
            d[v] = d[u] + 1;
            dq.addLast(v);
        }
    }
}

// TSP
long[][] dp = new long[k][1 << k];
for (int i = 0; i < k; i++) {
    Arrays.fill(dp[i], Const.LINF);
    dp[i][1 << i] = 1;
}
int[][] bits = BitUtil.bits(k);
for (int s = 1; s < 1 << k; s++) {
    if (bits[s].length <= 1) continue;
    for (int v : bits[s]) {
        int p = s ^ (1 << v);
        for (int u : bits[p]) {
            if (ds[u][c[v]] < 0) continue;
            dp[v][s] = Math.min(dp[v][s], dp[u][p] + ds[u][c[v]]);
        }
    }
}
long ans = Const.LINF;
for (int i = 0; i < k; i++) {
    ans = Math.min(ans, dp[i][(1 << k) - 1]);
}
pw.println(ans >= Const.LINF ? -1 : ans);

F - Shift and Inversions

初めの一回は普通に転倒数を求める (これは有名かつ頻出なので理解した上でライブラリ化しておくとよさそう)．先頭の要素を末尾に移動したときの転倒数の差分が分かればよい．

移動する要素を $X$ として， $X$ より大きい要素は $N-1-X$ 個，小さい要素は $X$ 個存在するので，差分は $N-1-2X$ である．あとは，この差分を足しこむ操作を $N-1$ 回繰り返しながら出力すればよい．

全体の計算量は，初回の転倒数を求める部分が $O(N\log N)$ で，他は線形時間で動作するので $O(N\log N)$ ．

注意点といえば，転倒数は最大で $\dfrac{N(N-1)}{2}$ なので 32 bit 整数で計算するとオーバーフローする可能性があることくらい？

int n = sc.nextInt();
int[] a = sc.ints(n);
long inv = InversionNumber.solve(a);
pw.println(inv);
for (int i = 0; i < n - 1; i++) {
    inv += n - 1 - 2 * a[i];
    pw.println(inv);
}