AtCoder エクサウィザーズ 2019

結果

　A,B,Cの3完。350位でパフォーマンスは1924、レーティング変動は1727→1749(+22)だった。D問題は自分の力でも解き得る問題だったと思うが、上手くまとめられなかった。

A問題

　最初は"正"三角形というところを見落としていて、三角形の成立条件は最大辺が他の2辺の和より短いことだっけとか考えて実装し始めてしまっていた。入力例2がNoであることでようやく気づいたが、YesをYES(NoをNO)と出力してしまい1WA。

B問題

　数えるだけとは思いつつ思考したくなかったのでわりと冗長な書き方をしてしまった。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N;
    string s;
    cin >> N >> s;
    ll red = 0, blue = 0;
    for (char c : s) {
        (c == 'R' ? red++ : blue++);
    }
    cout << (red > blue ? "Yes" : "No") << endl;
}

C問題

　考察メモを丁寧に取ることを意識してやる。操作を後ろから見るというのは使いそうと思ってちょっと考えたりもしたけどわからず、サンプルをちゃんと解かないとダメだと思って紙の上で解きはじめる。入力例2までを解いたところで以下の画像左下あたりの性質に気づいてこれは解けそうな問題だと感じた。入力例3をやるか一瞬迷ったけどこういうのをちゃんとやるのが大事だと思ってやって、しばらく眺めていたところ網掛けにしているような感じでゴーレムが消滅する範囲が下の方から定まることに気づいた。これは入力例をやらないと気づかないことだったと思う。

　左端の文字で左へ行けという指示が出ると左側の消滅範囲が一つ広がる。右側も同様。しかし左端の文字でその前に右へ行けという指示があると消滅しない。そんな感じで境界付近の指示だけを監視していれば範囲がわかる。

　しかし提出してみるとWAが出る。左右の境界がすれ違うまで進むと答えが負になるというバグを直して再提出したがまだWA。条件わけに不要なelseによる分岐を入れてしまっていたせいだった。右端と左端が同じ文字だったとき、一つの命令で左右両方の境界が動き得るのにelseで分岐していたので片方しか見れていなかった。下のような例を考えてようやく原因がわかった。

　WAが出たとき原因となる例を思いつく能力はどうやれば伸ばせるのかよくわからない。

#include"bits/stdc++.h"
using namespace std;
using ll = int64_t;

int main() {
    ll N, Q;
    string s;
    cin >> N >> Q >> s;
    vector<char> t(Q), d(Q);
    for (ll i = 0; i < Q; i++) {
        cin >> t[i] >> d[i];
    }

    //[left, right]にあるものは生き残る
    ll left = 0, right = N - 1;

    for (ll i = Q - 1; i >= 0; i--) {
        if (d[i] == 'L') {
            if (t[i] == s[left]) {
                left++;
            } 
            if (right < N - 1 && t[i] == s[right + 1]) {
                right++;
            }
        } else {
            if (t[i] == s[right]) {
                right--;
            } 
            if (left > 0 && t[i] == s[left - 1]) {
                left--;
            }
        }
    }

    cout << max(right - left + 1, (ll)0) << endl;
}

D問題

　1時間以上この問題を考えていたわけだけど全然考察が進んでいる感じがしなかった。こういうときはもっとスタート地点に戻って考えることを意識しないとダメだった。しかしより大きいものは関係ないということがわかっていながら降順に見ていく発想が出てこないのは残念。

　merom686氏の提出を参考にしてAC。これは解けるようになっておきたい問題だ。

#include <bits/stdc++.h>
using namespace std;
using ll = int64_t;

constexpr ll MOD = 1e9 + 7;
ll N, X;
vector<ll> S;
vector<vector<ll>> memo;

ll solve(ll i, ll x) {
    if (i == N - 1) {
        return x % S[i];
    }

    if (memo[i][x] != -1) {
        return memo[i][x];
    }

    ll result = 0;

    //i番目のものを先頭で使う
    (result += solve(i + 1, x % S[i])) %= MOD;

    //i番目のものを先頭以外で使う
    //S[i]より小さいもので先にmodが取られるのでS[i]はxに影響しない
    //残りN - i個で先頭以外の位置はN - i - 1通りありうる
    (result += (N - i - 1) * solve(i + 1, x) % MOD) %= MOD;

    return memo[i][x] = result;
}

int main() {
    cin >> N >> X;
    S.resize(N);
    for (ll i = 0; i < N; i++) {
        cin >> S[i];
    }

    sort(S.begin(), S.end(), greater<>());

    memo.resize(N + 1, vector<ll>(X + 1, -1));
    cout << solve(0, X) << endl;
}