AGC 023 A-C

昨日AGC023に出ました.

順位:657位

パフォーマンス:1475

レーティング:1662→1641(-21)

はい,大爆死という奴ですね...

A問題は200点じゃないけどすぐわかる.でもB問題がぜんぜんわからず,C問題に行くなどしてたら終わってしまった.ただ自分が失敗してしまっただけで実装もシンプルで良い問題だった.

 ・A問題 Zero-Sum Ranges

長さNの整数列Aがある.Aの空でない連続する部分列のうち和が0となるものはいくつあるか?

B[i]=A[0]+A[1]+...+A[i](i番目までの累積和)としたとき,区間[l,r]の和はB[r]-B[l-1]だから,同じ値のもの同士をペアにすると和が0になることがわかるので上手く数える.

ソースコード

#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
int A[200000];
int main() {
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) cin >> A[i];
    map<LL, int> cnt;
    LL sum = 0;
    LL ans = 0;
    for (int i = 0; i < N; i++) {
        sum += A[i];
        if (sum == 0) ans++;
        ans += cnt[sum];
        cnt[sum]++;
    }
    cout << ans << endl;
}

・B問題 Find Symmetries

大きさN×Nのグリッドが二つある.グリッドの上からiマス目,左からjマス目のマスをマス(i,j)と呼ぶ.一つ目のグリッドの各マスには小文字のアルファベットが書かれている.ある二つの整数A,B(0≦A,B<N)を選び,二つ目のグリッドのマス(i,j)には一つ目のグリッドのマス((i+A)%N,(j+B)%N)に書かれている文字を書くことにする.このとき二つ目のグリッドが「良いグリッド」であるとは,全てのマス(i,j)について「マス(i,j)に書かれた文字=マス(j,i)に書かれた文字」を満たすということである.二つ目のグリッドが「良いグリッド」となるような(A,B)の選び方は何通りあるか?

問題文の通りに文字を書いていくと元々の文字を左にA個シフト,上にB個シフトすることになる.「良いグリッド」は左に1個,上に1個シフト(対角線に沿ってシフト)させても「良いグリッド」である,ということに気づくかがポイント.そうすると(A,B)を選んだとき「良いグリッド」になることと(A+1,B+1)を選んだとき「良いグリッド」になることが同値であることがわかるので試すべきシフトは(0,0),(0,1),...(0,N-1)だけになる(B-A≡kであるような(A,B)を選んだとき「良いグリッド」になるかは(0,k)をチェックすればわかるから).チェックにO(N^2)かかるのでチェックすべき組をO(N)にしないといけない.だからA,Bのどちらか一方だけ固定することにしようとはかんがえたが出来ず.

ソースコード

#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
char S[300][301];
int main() {
    int N;
    cin >> N;
    for (int i = 0; i < N; i++) cin >> S[i];
    int ans = 0;
    for (int B = 0; B < N; B++) {
        bool ok = 1;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (S[i][(j + B) % N] != S[j][(i + B) % N]) {
                    ok = 0;
                    break;
                }
            }
            if (!ok) break;
        }
        if (ok) ans += N;
    }
    cout << ans << endl;
}

・C問題 Painting Machines

N個のマスが横一列に並んでいる.はじめ全てのマスは白である.N-1個のマシンがあり,i番目のマシンはi番目とi+1番目のマスを黒く塗る.N-1個のマシンを稼働させる順番を(1,2,...,N-1)の順列Pで表すことにする.Pのスコアは,その順列に従ってマシンを稼働させていったとき,はじめて全てのマスが黒になるまでに稼働させたマシンの台数と定義される.全ての順列Pについてのスコアの和を10^9+7で割った余りを求めよ.

スコアがk以下となるような順列の個数をf(k)とすると,スコアがちょうどkになる順列の個数はf(k)-f(k-1)で計算できるのでf(k)を求めることにしよう.(全て稼働させたあとに)全てのマスが黒になるようなk個のマシンの選び方をg(k)とする.そうするとf(k)=g(k)*k!*(N-1-k)!である(注目しているk個のマシンを先頭に並べ,それ以外をうしろに並べることにすると,それらの中で自由に並び替えてもスコアはk以下だからこのようなことがわかる).という所まではコンテスト中にわかったが肝心のg(k)の求め方がわからなかった.実はg(k)=combination[k-1,N-1-k]である.重要なことは「稼働させないマシンの両脇のマシンは必ず稼働させなければならない」という観察.稼働させるk個のマシンのk-1個のすきまのうちN-1-k個を選んでそこに稼働させないマシンを入れるとかんがえればこの式にたどり着ける.

ソースコード

#include "bits/stdc++.h"
using namespace std;
typedef long long LL;
LL MOD = 1000000007;
LL fact[1000001];
LL inv_fact[1000001];
LL comb(LL n, LL k) {
    if (n < k) return 0;
    LL ret = fact[n];
    (ret *= inv_fact[k]) %= MOD;
    (ret *= inv_fact[n - k]) %= MOD;
    return ret;
}
LL mod_pow(LL a, LL b) {
    if (b == 0) return 1;
    if (b % 2 == 0) {
        LL x = mod_pow(a, b / 2);
        return (x*x) % MOD;
    }
    return (mod_pow(a, b - 1)*a) % MOD;
}
int main() {
    int N;
    cin >> N;
    fact[0] = inv_fact[0] = 1;
    for (int i = 1; i <= N; i++) {
        fact[i] = fact[i - 1];
        (fact[i] *= i) %= MOD;
        inv_fact[i] = inv_fact[i - 1];
        (inv_fact[i] *= mod_pow(i, MOD - 2)) %= MOD;
    }
    LL ans = 0;
    LL prev = 0;
    LL now = 0;
    for (int i = 1; i <= N - 1; i++) {
        LL ret = comb(i - 1, N - 1 - i);
        (ret *= fact[i]) %= MOD;
        (ret *= fact[N - 1 - i]) %= MOD;
        now = ret;
        ret = (ret - prev + MOD) % MOD;
        (ret *= i) %= MOD;
        (ans += ret) %= MOD;
        prev = now;
    }
    cout << ans << endl;
}