AtCoder Beginner Contest 367に参加しました。

使用しているテンプレート

A - Shout Everyday

B時からC時までの間にA時があるかを判定する問題。日付をまたぐかどうかで場合分けをする。 Yesになる条件は、$B<C~かつ~(A<B~または~C<A)$、または、$B>C~かつ~C<A<B$。

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int A, B, C; cin >> A >> B >> C;
    string ans = "No\n";
    if(B < C){
        if(A < B or C < A) ans = "Yes\n";
    }else{
        if(C < A and A < B) ans = "Yes\n";
    }
    cout << ans;
}

B - Cut .0

小数第3位まで与えられた実数の末尾の0と.を取り除く問題。文字列として受け取り、末尾が0の間末尾を削除して、最後に末尾が.なら末尾を再び削除する。

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string S; cin >> S;
    while(S.back() == '0'){
        S.pop_back();
    }
    if(S.back() == '.'){
        S.pop_back();
    }
    cout << S << "\n";
}

C - Enumerate Sequences

成約がとても小さいので全探索すれば解けそう。ただし、愚直にforループを書くと最大で8重ループになってしまうので、再帰で実装する。 あまり美しくない書き方だと思うが、再帰を書くときは混乱しないようにあらゆる変数をグローバル変数として宣言している。引数を考えなくていいだけで実装がとても楽。

int N, K;
vector<int> R;

vector<int> A;
void dfs(){
    // 最後までたどり着いたら K の倍数か判定して出力
    if(A.size() == N){
        int sum = accumulate(all(A), 0);
        if(sum % K == 0){
            v_cout(A);
        }
        return;
    }

    int n = A.size();
    // n + 1 個目の数を全部探索する
    rrep(i, 1, R[n] + 1){
        A.emplace_back(i);
        dfs();
        A.pop_back();
    }
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> N >> K;
    R.resize(N); v_cin(R);

    dfs();
}

D - Pedometer

一方通行の池の周に $N$ 個の休憩所があり、休憩所間の距離が与えられる。休憩所の組 $(s, t)~(s\ne t)$ であって $s$ から $t$ までの距離が $M$ の倍数となるものの個数を求める問題。 問題を読んでもよくわからなかったので、とりあえず入力例1で考察した。愚直に実装すると $O(N^2)$となってしまうので、別の方法が必要。$s$ から $t$ までの距離を $M$ で割った余りを $d(s, t)$ とし、$d(0, t)$ の表を考えてみる。

0 1 2 3
0 2 0 1

このとき、$d(0, 0) = d(0, t)$ なる $t\ne 0$ の個数が $s = 0$ のときの組の個数になりそう。 次に $s = 1$ のときは始点が変わるので、$d(0, 0) \leftarrow d(0, 0) + R\%M~(R: 周の長さ)$ として表を更新する。

0 1 2 3
1 2 0 1

あとは、同様に表を更新していく。 ここで、任意の $s$ に対して $d(0, s) = d(0, t)$ なる $t\ne s$ の個数を高速に求める必要があるが、$s = 0$ のときにすべての場合の個数を配列に入れておき、表を変更した部分だけ個数の配列も更新すれば $O(1)$ で個数を求めることができる。 これによって $O(N)$ で問題が解ける。

int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N, M; cin >> N >> M;
    vector<ll> A(N); v_cin(A);
    vector<ll> S(N, 0);
    rrep(i, 1, N) S[i] = (S[i - 1] + A[i - 1]) % M;

    ll R = accumulate(all(A), 0LL);

    vector<int> cnt(M, 0);
    rep(i, N) cnt[S[i]] ++;

    ll ans = 0;
    rep(s, N){
        ans += cnt[S[s]] - 1;
        cnt[S[s]] --;
        cnt[(S[s] + R) % M] ++;
    }
    
    cout << ans << "\n";
}

コンテスト結果

E問題ではダブリング、F問題ではハッシュが出題されたので、アルゴリズム勉強回だと思って復習したい。