接着剤の精進日記

競プロでの精進や研究に関係したことを書いていきます。

接着剤の「CodinGame Spring Challenge 2022」 参加記

CodinGame CodinGame Spring Challenge 2022 ゲームAI

はじめに

CodinGameのコンテスト（CodinGame Spring Challenge 2022)に参加しました
結果は世界57/7,695位（Legend）、日本13/445位でした
超次元サッカーで自分だけのゴールを決めよう！

ルール

いつものごとくツカモさんが翻訳記事を書いてくださっているのでそちらを参照ください（ありがとうございます）
tsukammo.hatenablog.com

やったこと

ルールべースで序盤はファーム、30ターン以降は攻2、守1のフォーメーション
相手にやられる前にやる！

ファーム

初手はモンスターのリスポーン地点を目指して進む
モンスターが見え始めたらシミュレートで貪欲に評価の高い行動を決定
評価関数には獲得マナ、baseの視界にいるモンスター、baseに向かってくるモンスター、視界などを評価対象とする
敵も入れていたがあまりうまく動かなかったので最終的には消した

攻撃

攻2でWIND一発 -> 2人WINDで相手のbaseの視覚外のモンスターを2ターンでゴールに入れる
もしくは、すでにbaseに侵入しているやつがいたら2人WINDで一気に押し込む
WINDを打つ際には、モンスターの移動をシミュレートし、移動先とbaseの直線上で上記の2つを最短ターンで行える場所に先回りして移動する
モンスターがいない場合は、リスポーン地点付近を索敵する
また、マナが40以上のときはコントロールで敵を寄せ、逆にマナが30未満のときはファームを行いマナを稼ぐ

守備

守備が何もわからなかったので最低限だけ実装した
baseの視界に入っているモンスターのうち、baseから一番近いモンスターに移動する
このターンにダメージを与えてくるモンスターがいるならWINDを使う
以上
防衛役にシールドは攻めのリソースがなくなるので諦めた

やりたかったこと

・焼きなまし（or 探索）
・守備を頑張る
・攻撃の効率化（そのターンごとに判定しているので無駄な動作があったりする）
・過去情報の活用
・ファームの効率化

感想

"fog of war"で嫌な予感がしていたけど大いに苦しんだ
探索が難しいのでルールベースだったが、一つ行動を追加するとあちこち壊れたり、上手く行っていた行動が弱くなったりして難しかった
上位陣はちゃんと探索できるところは探索していたり、使える情報をきちんと使い切っていてまだまだ詰めれるところあったんだなあってなった
最初は焼きなましをしようとしたり（シミュレートが重くて結局諦めた）、ローカル対戦でパラメータ調整する環境を作ったり（今回のは有効じゃなかった）、ゲームと向き合う時間が足りなかったかなと反省
対戦環境は次回以降も使えるはずなので、今後有効活用したい
とりあえずLegend行けてよかった

AtCoder Beginner Contest 248（ABC248）

AtCoderBeginnerContest AtCoderBeginnerContest248 ABC ABC248

atcoder.jp

A - Lacked Number

$ S $ に含まれない数字を全探索する

提出コード

void solve(){
    string S;
    cin >> S;
    for(char c='0';c<='9';c++){
        bool ok = true;
        for(char s : S) if(c == s) ok = false;
        if(ok){
            cout << c << endl;
            return;
        }
    }
}

B - Slimes

シミュレートをして回数を数える

提出コード

void solve(){
    ll A, B, K;
    cin >> A >> B >> K;
    int ans = 0;
    while(A < B){
        A *= K;
        ans++;
    }
    cout << ans << endl;
}

C - Dice Sum

$ dp[i][j][k] := i $ 番目まで見て、最後に選んだものが $ j $ のときに、その総和が $ k $ の場合の数としてDPをする

提出コード

void solve(){
    int N, M, K;
    cin >> N >> M >> K;
    vector dp(55, vector<mint>(2525));
    REP(i,1,M+1) dp[i][i] = 1;
    REP(_,N-1){
        vector nxt(55, vector<mint>(2525));
        REP(j,1,M+1){
            REP(k,1,M+1){
                REP(sum,K+1) if(sum+k <=K){
                    nxt[k][sum+k] += dp[j][sum];
                }
            }
        }
        swap(dp, nxt);
    }
    mint ans = 0;
    REP(i,1,M+1)REP(j,K+1) ans += dp[i][j];
    cout << ans << endl;
}

D - Range Count Query

$ A_i $ の要素ごとにそのインデックスをvectorなどに入れておくことで、二分探索で $ [L, R] $ の範囲にある個数を数えることができる

提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    int Q;
    cin >> Q;
    RangeCountExact<int> cnt(A);
    while(Q--){
        int l, r, x;
        cin >> l >> r >> x;
        --l;
        cout << cnt.get(l, r, x) << endl;
    }
}

E - K-colinear Line

$ K = 1 $ の場合のみ infinityなのでそれ以外の場合を考える
$ i $ 番目の頂点と $ j ( j ≠ i ) $ 番目の頂点の直線を求め、その直線をmapなどで数える
数えた直線の個数が $ K - 1 $ 以上ならその直線を答えに加える

提出コード

void solve(){
    int N, K;
    cin >> N >> K;
    vector<ll> x(N), y(N);
    REP(i,N) cin >> x[i] >> y[i];
    if(K == 1){
        cout << "Infinity" << endl;
        return;
    }
    set<tuple<ll, ll, ll>> st;
    REP(i,N){
        map<pair<ll, ll>, int> mp;
        REP(j,N) if(i != j) {
            ll x1 = x[j] - x[i], y1 = y[j] - y[i];
            ll g1 = gcd(abs(x1), abs(y1));
            x1 /= g1, y1 /= g1;
            if(x1 == 0) continue;
            if(y1 == 0) continue;
            if(x1 < 0) x1 *= -1, y1 *= -1;
            if(x1 == 0 and y1 == 0) continue;
            mp[{x1, y1}]++;
        }
        for(auto [k, v] : mp){
            auto [x1, y1] = k;
            if(v + 1>= K){
                if(x1 == 0 or y1 == 0) st.insert({x1, y1, 0});
                else st.insert({x1, y1, y[i] * x1 - y1 * x[i]});
            }
        }
    }

    map<int, int> mpx, mpy;
    REP(i,N){
        mpx[x[i]]++;
        mpy[y[i]]++;
    }
    int ans = (int)st.size();
    for(auto [k, v] : mpx) if(v >= K) ans++;
    for(auto [k, v] : mpy) if(v >= K) ans++;
    cout << ans << endl;
}

AtCoder Beginner Contest 247（ABC247）

AtCoderBeginnerContest AtCoderBeginnerContest247 ABC ABC247

atcoder.jp

A - Move Right

二進数を右に1シフトする

提出コード

void solve(){
    string S;
    cin >> S;
    cout << '0' << S[0] << S[1] << S[2] << endl;
}

B - Unique Nicknames

人 $ i $ にあだ名をつけるには、人 $ i $ 以外に $ s_i $ も $ t_i $ も両方とも出現していなければいいのでこれを全探索する

提出コード

void solve(){
    int N;
    cin >> N;
    vector<string> s(N), t(N);
    REP(i,N) cin >> s[i] >> t[i];
    
    REP(i,N){
        int cnt_s = 0;
        int cnt_t = 0;
        REP(j,N) if(i != j){
            if(s[i] == t[j] or s[i] == s[j]) cnt_s++;
            if(t[i] == s[j] or t[i] == t[j]) cnt_t++;
        }
        if(cnt_s and cnt_t){
            cout << "No" << endl;
            return;
        }
    }
    cout << "Yes" << endl;
}

C - 1 2 1 3 1 2 1

再帰関数で実際に作る

提出コード

void solve(){
    int N;
    cin >> N;
    auto f = [&](auto &&self, int n) -> vector<int>{
        if(n==1) return vector<int>(1, 1);
        vector<int> v = self(self, n-1);
        vector<int> res = v;
        res.push_back(n);
        for(auto x : v) res.push_back(x);
        return res;
    };
    for(auto c : f(f, N)) cout << c << " ";
    cout << endl;
}

D - Cylinder

dequeで $ x $ とその個数を管理し、クエリに答える

提出コード

void solve(){
    int Q;
    cin >> Q;
    deque<pair<ll, ll>> dq;
    while(Q--){
        ll q, x, c;
        cin >> q;
        if(q == 1){
            cin >> x >> c;
            dq.push_back({x, c});
        }
        else{
            cin >> c;
            ll sum = 0;
            while(c > 0){
                auto [x, cnt] = dq.front(); dq.pop_front();
                if(c < cnt){
                    sum += x * c;
                    cnt -= c;
                    dq.push_front({x, cnt});
                    break;
                }
                else{
                    sum += x * cnt;
                    c -= cnt;
                }
            }
            cout << sum << endl;
        }
    }
}

E - Max Min

$ i $ より右側で $ Y $ が含まれる区間の最も左側と最も右側（$ l_1, r_1 $ )、 $ X $ が含まれる最も左側と最も左側（$ l_2, r_2 $) を求めることができれば、$ i $ についての答えは $ \max(0, \min(r_1, r_2) - \max(l_1, l_2)) $ となる
$ l, r $ についてはセグ木上の二分探索で求めることができるので、この総和が答え

提出コード

void solve(){
    int N, X, Y;
    cin >> N >> X >> Y;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    segtree<int, op1, e1> mi(A);
    segtree<int, op2, e2> ma(A);
    ll ans = 0;
    REP(i,N){
        global_mi = Y+1;
        global_ma = X-1;
        int l1 = mi.max_right<g1>(i);
        int l2 = ma.max_right<g2>(i);
        global_mi = Y;
        global_ma = X;
        int r1 = mi.max_right<g1>(i);
        int r2 = ma.max_right<g2>(i);
        ans += max(0, min(r1, r2) - max(l1, l2));
    }
    cout << ans << endl;
}

AtCoder Beginner Contest 246（ABC246）

AtCoderBeginnerContest AtCoderBeginnerContest246 ABC ABC246

atcoder.jp

A - Four Points

$ x $ は $ x1, x2, x3 $ のうち、一つしか使われていない値になる
$ y $ についても同様

提出コード

void solve(){
    int x1, x2, x3, y1, y2, y3;
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
    cout << (x1^x2^x3) << " " << (y1^y2^y3) << endl;
}

B - Get Closer

$ ( \frac{A}{\sqrt{A^2 + B^2}}, \frac{B}{\sqrt{A^2 + B^2}} ) $ が答え

提出コード

void solve(){
    int A, B;
    cin >> A >> B;
    printf("%.12lf %.12lf\n",  (double)A / hypot(A, B), (double)B / hypot(A, B));
}

C - Coupon

$ A_i \geq X $ の間はどれに使ってもいい
すべての $ i $ について $ A_i \lt X $ となった場合、降順ソートをして使えるだけ使う

提出コード

void solve(){
    ll N, K, X;
    cin >> N >> K >> X;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    ll ans = 0;
    REP(i,N){
        if(A[i] / X <= K){
            K -= A[i] / X;
            A[i] = A[i] % X;
        }
        else{
            A[i] -= K * X;
            K = 0;
        }
    }

    sort(ALL(A));
    reverse(ALL(A));
    REP(i,N){
        if(K > 0) K--;
        else ans += A[i];
    }
    cout << ans << endl;
}

D - 2-variable Function

$ 0 \leq a, b \leq 10^6 $ となるので片方は全探索できる
片方を固定した場合、二分探索で $ N $ 以上となる最小の $ X $ になる値を求めることができるのでその中で最小のものが答え

提出コード

void solve(){
    ll N;
    cin >> N;
    ll ans = 9LL * LINF;
    auto f = [](ll a, ll b) ->ll{
        return a*a*a + a*a*b + a*b*b + b*b*b;
    };

    REP(a,1e6+10){
        ll l = -1, r = 1e6+10;
        while(r - l > 1){
            ll m = (r + l) >> 1;
            if(f(a, m) >= N) r = m;
            else l = m;
        }
        chmin(ans, f(a, r));
    }
    cout << ans << endl;
}

E - Bishop 2

$ dist[dir][x][y] := $ マス $ (x, y) $ に方向 $ dir $ でたどり着いたときの最短距離としてダイクストラを行う
$ dir $ と同一の方向に進むならコストは $0$、それ以外ならコストは $1$ として最短経路を求めればいい（01BFS）

提出コード

void solve(){
    int N;
    cin >> N;
    int Ax, Ay, Bx, By;
    cin >> Ax >> Ay >> Bx >> By;
    --Ax, --Ay, --Bx, --By;
    vector<string> S(N);
    REP(i,N) cin >> S[i];
    vector dist(5, vector(N, vector(N, INF)));
    int dx[4] = {1, 1, -1, -1};
    int dy[4] = {1, -1, 1, -1};
    using T = tuple<int, int, int, int>;
    priority_queue<T, vector<T>, greater<T>> q;
    REP(d, 4){
        dist[d][Ax][Ay] = 0;
        q.emplace(0, 4, Ax, Ay);
    }
    dist[4][Ax][Ay] = 0;
    while(!q.empty()){
        auto [c, dir, x, y] = q.top(); q.pop();
        if(c < dist[dir][x][y]) continue;
        REP(d, 4){
            int nx = x + dx[d], ny = y + dy[d];
            if(nx < 0 or nx >= N or ny < 0 or ny >= N or S[nx][ny] == '#') continue;
            if(d == dir){
                if(chmin(dist[d][nx][ny], c)) q.emplace(dist[d][nx][ny], d, nx, ny);
            }
            else{
                if(chmin(dist[d][nx][ny], c + 1)) q.emplace(dist[d][nx][ny], d, nx, ny);
            }
        }
    }
    int ans = INF;
    REP(d, 4){
        chmin(ans, dist[d][Bx][By]);
    }
    cout << (ans == INF ? -1 : ans) << endl;
}

AtCoder Beginner Contest 245（ABC245）

AtCoderBeginnerContest AtCoderBeginnerContest245 ABC ABC245

atcoder.jp

A - Good morning

分に直して比較をする

提出コード

void solve(){
    int A, B, C, D;
    cin >> A >> B >> C >> D;
    if(60*A+B < 60*C+D+1) cout << "Takahashi" << endl;
    else cout << "Aoki" << endl;
}

B - Mex

配列で出現した値を管理する

提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> A(2020);
    REP(i,N){
        int a;
        cin >> a;
        A[a]++;
    }
    REP(i,2020) if(A[i] == 0){
        cout << i << endl;
        return;
    }
}

C - Yamanote Line Game

DPをする

提出コード

void solve(){
    int N, K;
    cin >> N >> K;
    vector<int> A(N),B(N);
    REP(i,N) cin >> A[i];
    REP(i,N) cin >> B[i];
    map<int, int> mp;
    mp[A[0]] = 1;
    mp[B[0]] = 1;
    REP(i,1,N){
        map<int, int> nxt;
        for(auto [k, v] : mp){
            if(abs(k - A[i]) <= K) nxt[A[i]]++;
            if(abs(k - B[i]) <= K) nxt[B[i]]++;
        }
        swap(mp, nxt);
    }
    if(mp.size() > 0) cout << "Yes" << endl;
    else cout << "No" << endl;
}

D - Polynomial division

上の桁から決めていく

提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<int> A(N+1), B(M+1), C(N+M+1);
    REP(i,N+1) cin >> A[i];
    REP(i,N+M+1) cin >> C[i];
    for(int i=M;i>=0;i--){
        B[i] = C[i+N] / A[N];
        REP(j,N+1) C[i+j] -= B[i] * A[j];
    }
    REP(i,M+1) cout << B[i] << " ";
    cout << endl;
}

E - Wrapping Chocolate

箱とチョコレートを同じ配列に入れ、縦の降順にソートを行う
このとき、縦が同じなら箱が手前に来るようにソートをする
縦の降順に見ていき、箱なら横の長さをmultisetなどで管理し、チョコレートなら $ B_i $ 以上の箱で一番小さい値の箱を使う

提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    vector<int> A(N), B(N), C(M), D(M);
    REP(i,N) cin >> A[i];
    REP(i,N) cin >> B[i];
    REP(i,M) cin >> C[i];
    REP(i,M) cin >> D[i];
    vector<tuple<int, int, int>> vs;
    REP(i,N) vs.emplace_back(-A[i], 1, B[i]);
    REP(i,M) vs.emplace_back(-C[i], -1, D[i]);
    sort(ALL(vs));
    multiset<int> ms;
    for(auto [h, c, w] : vs){
        if(c == -1) ms.insert(w);
        else{
            auto itr = ms.lower_bound(w);
            if(itr == ms.end()){
                cout << "No" << endl;
                return;
            }
            ms.erase(itr);
        }
    }
    cout << "Yes" << endl;
}

F - Endless Walk

強連結成分分解を行ったグラフ上でDPを行う

提出コード

void solve(){
    int N, M;
    cin >> N >> M;
    StronglyConnectedComponents scc(N);
    REP(i,M){
        int u, v;
        cin >> u >> v;
        scc.make_edge(--u, --v);
    }
    scc.solve();
    auto g = scc.topological_sort();
    auto edge = scc.edge;
    int ans = 0;
    vector<int> dp(N);
    for(int i=(int)g.size()-1;i>=0;i--){
        if(g[i].size() == 1) for(auto nv : edge[g[i][0]]) dp[i] |= dp[scc.getLabel(nv)];
        else dp[i] = 1;
        if(dp[i]) ans += g[i].size();
    }
    cout << ans << endl;
}