接着剤の精進日記

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

接着剤の「CodinGame Green Circle」 参加記

はじめに

CodinGameのコンテスト(CodinGame Green Circle)に参加しました
結果は世界19/1,758位(Legend)、日本10/156位でした
技術的負債から目をそらして上手くアプリケーションを5つ作ろう!

ルール

ツカモさんの要約記事がとてもわかりやすいです(ありがとうございます)
tsukammo.hatenablog.com

やったこと

概要

方針:ボーナスを4つCIで貯める
ルールベース+評価関数で行動決め(各フェーズごとに評価、5つ目のアプリの時だけターン全体をシミュレートしてリリース判定を全探索)
初手は先手後手関係なく2で決め打ち、相手に取られてたら5
大体以下のパターン
2 -> 3(4を取る) -> 4(5を取る)
2 -> 4(5を取る)
5 -> 6

移動(MOVE)

基本的には1マスずつ移動(今いるマスから遠いマスほどペナルティ)
手札にボーナスがある時にはCIのマスの評価点を高くする
6にいて、ボーナスをCIできないときは7を無視してadminを通過する
ボーナスを4つ貯めていないときは2の評価を高くして、2 -> 3 or 4の流れをしやすくしてボーナスのCIを優先
敵と隣接するマスは基本的には止まらないようにし、5つ目のアプリケーションをリリースできるマスのときだけ許容

相手にカードの譲渡(GIVE_CARD)

リーサル時以外は止まらないので基本的には発生しない
リーサル時は渡してもリリースできるカードを渡す

通行税の支払い(THROW_CARD)

ボーナス以外を優先的に支払う
リーサル時はGIVE_CARDと同様に支払ってもリリースできるカードを支払う

カードの使用(PLAY_CARD)

優先順位をつけて、その順番に使用できるか判定をして使用できるならそれを使用する

  1. 5つ目をリリースできるなら何も使用しない
  2. TASK_PRIORITIZATIONを使って5つ目をリリースできるなら使用する
  3. CONTINUOUS_INTEGRATION(ボーナス4つを優先、それ以外はリリースに使いやすそうかどうかを評価関数で決定)
  4. TRAINING
  5. CODING
  6. REVIEW
  7. ARCHITECTURE_STUDY
  8. REFACTORING
  9. DAILY_ROUTINE
  10. TASK_PRIORITIZATION

アプリケーションのリリース(RELEASE)

ボーナスを2個CIするまではリリースしない
ただし、相手の方が自分よりリリースしていたら技術的負債が3以下のリリースを許容
ボーナスが2以上4未満のときは技術的負債が3以下、ボーナスが4以上のときは全部リリース
リリース対象は技術的負債が最も小さいものを選択
技術的負債が同じ場合は、相手がリリースしやすそうなものを評価関数で選択

やりたかったこと

・探索(モンテカルロ系)
・相手の行動も考慮して評価

知見

・ISMCTSというのが適用できるらしい
・NNとか強化学習勢がちらほらいたっぽい、難しそうに見えるけどできるのすごい(8位の人がDQNで完全にランダムからの学習らしい?)
・強いルールベースがあればそれをプレイアウトに使えるらしい

感想

コンテスト最初の方はゲーム側のバグとか仕様把握にかなり頭を悩まされた
ボーナスをCIするのが強すぎるのと初手が大体決まっているので戦略の幅が狭かった印象
コンテスト開催知ったのが割と直前だったのでこどげ休暇を取らなかったけどLEGEND行けてよかった
そろそろ不完全情報なくならない?(探索が難しくて評価関数に逃げてしまう)

Codingameのローカル対戦環境をdockerでポンする(GUI編)

はじめに

前回記事でローカル対戦環境をdockerで構築できるようにしたが、CUIのみだったのでGUIでもできるようにした
GUIでの環境構築には以下を参考にさせていただきました
前回同様おばあちゃん回での構築
koyumeishi.hatenablog.com

前提

dockerの詳しい説明は省きます
docker-desktopなどをインストールしてdockerコマンドが使えるようになっていればできるはずです

環境構築

必要なリポジトリをcloneする

git clone https://github.com/EmulsionBondo/CodingameLocalBattle_GUI.git
cd CodingameLocalBattle_GUI

Codingameのリポジトリをcloneする

今回はCodingameの公式リポジトリをそのまま使用します
src/test/javaに必要なファイルが入っているのでsrc/main/javaに移動します

git clone https://github.com/CodinGame/FallChallenge2020.git
cp assembly.xml FallChallenge2020/
mv FallChallenge2020/src/test/java/Fall2020Main.java FallChallenge2020/src/main/java/
mv FallChallenge2020/src/test/java/BasicAgent.java FallChallenge2020/src/main/java/

Mavenでビルド

docker run -it --rm --name my-maven-project --platform linux/amd64 -v $PWD/FallChallenge2020/:/usr/src/mymaven -w /usr/src/mymaven maven:3.3-jdk-8 mvn clean install assembly:assembly -Ddescriptor=assembly.xml
mv FallChallenge2020/target/fall-2020-1.0-SNAPSHOT-jar-with-dependencies.jar ./

ローカル対戦環境のdockerを立てる

docker build -t local_battle --platform linux/amd64 ./
docker run -it -d --rm --name local_battle --platform linux/amd64 -p 8888:8888 -v $PWD:/work local_battle

ブラウザでローカル対戦のGUIを確認

ブラウザからhttp://localhost:8888/test.htmlにアクセス
実行に若干時間がかかるので、dockerを立ててすぐだとアクセスできないかもしれません

対戦させるAIの変更

src/main/java/Fall2020Main.java

//Add players
gameRunner.addAgent(BasicAgent.class, "Kotake");
gameRunner.addAgent(BasicAgent.class, "Koume");

部分を自分の書いたプログラムへのパスに変更
変更したあとは再度ビルドしてからdockerを再度立てるなりしてください

終わりに

GUIで試してみたらできた
IDEで十分な気もするけど気にしない

Codingameのローカル対戦環境をdockerでポンする

はじめに

Codingameのローカル対戦環境を用意するときに、Java周りの環境構築が難しかったのでdockerでポンするようにした
cg-brutaltesterを使用して、CLIでローカル対戦を行うことを目的としています
GUIで対戦を見たい場合の環境構築は以下を参照してください

coonevo.hatenablog.com

前提

dockerの詳しい説明は省きます
docker-desktopなどをインストールしてdockerコマンドが使えるようになっていればできるはずです

環境構築

必要なリポジトリをcloneする

git clone https://github.com/EmulsionBondo/CodingameLocalBattle.git
cd CodingameLocalBattle

CodingameのRefreeをcloneする

利用可能なものの一覧はこちらにあります
今回は通称おばあちゃんことFall Challenge2020のものをcloneします
cg-brutaltesterには記載されていませんが、対応してくれたリポジトリがあったのでそちらを使用します

git clone https://github.com/FrogChopi/FallChallenge2020_brutaltester

cg-brutaltesterの実行ファイルをダウンロード

curl -OL https://github.com/dreignier/cg-brutaltester/releases/download/1.0.0/cg-brutaltester-1.0.0.jar

Refreeのビルド

docker run -it --rm --name my-maven-project --platform linux/amd64 -v $PWD/FallChallenge2020_brutaltester/:/usr/src/mymaven -w /usr/src/mymaven maven:3.3-jdk-8 mvn clean install package
mv FallChallenge2020_brutaltester/target/fall-2020-1.0-SNAPSHOT.jar ./

ローカル対戦環境のdockerを立てる

docker build -t local_battle --platform linux/amd64 ./
docker run -it -d --name local_battle --platform linux/amd64 -v $PWD:/work local_battle

docker上でcg-burutaltesterを動かす

以下のコマンドでローカル対戦が実行されます

docker exec local_battle java -jar cg-brutaltester-1.0.0.jar -r "java -jar fall-2020-1.0-SNAPSHOT.jar" -p1 "python3 test.py" -p2 "./a.out" -n 1

-p1でplayer1のAI、-p2でplayer2のAI、-nで対戦数を指定します
a.outのような実行ファイルを指定する場合、docker上の環境と違うとエラーが出るかもしれないです
C++の場合、以下でdocker上でビルドできるようにしています
プログラムはpathを指定するなり、CodingameLocalBattleディレクトリに持ってくるなりよしなにしてください

docker exec local_battle g++ -std=gnu++17 -O2 a.cpp -o a.out

実行が終わると以下のような出力が出ます

01:40:47,055 INFO  [com.magusgeek.brutaltester.Main] Referee command line: java -jar fall-2020-1.0-SNAPSHOT.jar
01:40:47,059 INFO  [com.magusgeek.brutaltester.Main] Player 1 command line: python3 test.py
01:40:47,059 INFO  [com.magusgeek.brutaltester.Main] Player 2 command line: ./a.out
01:40:47,059 INFO  [com.magusgeek.brutaltester.Main] Number of games to play: 1
01:40:47,060 INFO  [com.magusgeek.brutaltester.Main] Number of threads to spawn: 1
01:40:53,751 INFO  [com.magusgeek.brutaltester.GameThread] End of game 1     0.00% 0.00%
01:40:53,754 INFO  [com.magusgeek.brutaltester.Main] *** End of games ***
+----------+----------+----------+
| Results  | Player 1 | Player 2 |
+----------+----------+----------+
| Player 1 |          | 0.00%    |
+----------+----------+----------+
| Player 2 | 0.00%    |          |
+----------+----------+----------+

こどげの初期プログラムを使っているのでどちらも0.00%になっていますが、ちゃんと動くプログラムに差し替えれば勝率が変動します

終わりに

Javaの環境にブチギレた結果できあがった
cg-brutaltesterに対応したRefreeが公開されていれば、基本的には同様に動くはず
動かないとかあればお気軽にどうぞ
GUIの方もそのうち試して見るかも

AtCoder Beginner Contest 250(ABC250)

atcoder.jp

A - Adjacent Squares

上下左右の4方向にマスがあるかどうかを調べる

提出コード

void solve(){
    int H, W, R, C;
    cin >> H >> W >> R >> C;
    --R, --C;
    int ans = 0;
    REP(d,4){
        int nh = R + dx[d];
        int nw = C + dy[d];
        if(nh < 0 or nh >= H or nw < 0 or nw >= W) continue;
        ans++;
    }
    cout << ans << endl;
}

B - Enlarged Checker Board

$ A = B = 1 $ のとき、.#かどうかは $ i + j $ の偶奇で決まる
それ以外の場合でも同様で、$ i + j $ ごとに $ A \times B $のマスを出力していく

提出コード

void solve(){
    int N, A, B;
    cin >> N >> A >> B;
    vector fi(A * N, vector<char>(B * N));
    int p = 0;
    REP(i,N){
        REP(h,A){
            REP(j,N) {
                REP(w,B){
                    fi[i*A+h][j*B+w] = ((i + j) % 2 == 0 ? '.' : '#');
                }
            }
        }
    }
    REP(i,A*N){
        REP(j,B*N) cout << fi[i][j];
        cout << endl;
    }
}

C - Adjacent Swaps

整数 $ i $ のボールが今どこにあるかと、実際に並んでいる $ a $ の情報を持っておき、各クエリで実際にswapを行う

提出コード

void solve(){
    int N, Q;
    cin >> N >> Q;
    vector<int> x(Q);
    vector<int> A(N), idx(N);
    iota(ALL(A), 0);
    iota(ALL(idx), 0);
    REP(i,Q){
        cin >> x[i];
        --x[i];
        int idx1 = idx[x[i]];
        int idx2 = (idx1 == N - 1 ? idx1 - 1 : idx1 + 1);
        int right = A[idx2];
        swap(A[idx1], A[idx2]);
        swap(idx[x[i]], idx[right]);
    }
    REP(i,N) cout << A[i] + 1 << " ";
    cout << endl;
}

D - 250-like Number

素数 $ p $ を決めると、条件に当てはまる素数 $ q $ には単調性があるので二分探索で求めることができる
そのため素数をエラトステネスの篩などで予め求めておけばいい

提出コード

void solve(){
    ll N;
    cin >> N;
    SieveOfEratosthenes<ll> sieve(1010101);
    vector<ll> cum(1010102);
    REP(i,1010101) cum[i+1] = cum[i] + sieve.is_prime[i];
    ll ans = 0;
    for(ll p : sieve.prime){
        if(p > N) break;
        ll l = -1, r = (int)sieve.prime.size() - 1;
        while(r - l > 1){
            ll m = (l + r) >> 1;
            ll q = sieve.prime[m];
            if(q * q * q > N / p) r = m;
            else l = m;
        }
        cerr << p << " " << l << " " << r << endl;
        if(l < 0) continue;
        if(p >= sieve.prime[l]) continue;
        ans += cum[sieve.prime[l]] - cum[p];
        cerr << ans << endl;
    }
    cout << ans << endl;
}

E - Prefix Equality

ある整数 $ i $ が集合に含まれるかどうかをZobrist Hashで管理する
各整数ごとにHashを割り当てておき、追加されるときにそのXorを取ればその値が一致するかどうかで集合に含まれる要素の一致を判定することができる
任意の区間クエリだと最初勘違いしていたので無駄にMoを使って解いた

提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> a(N), b(N);
    Compress<int> cmp;
    REP(i,N){
        cin >> a[i];
        cmp.add(a[i]);
    }
    REP(i,N){
        cin >> b[i];
        cmp.add(b[i]);
    }
    cmp.build();
    int sz = cmp.size();
    vector<uint32_t> hash(sz);
    REP(i,sz) hash[i] = XorShift();

    int Q;
    cin >> Q;
    vector<int> x(Q), y(Q);

    REP(i,Q) cin >> x[i] >> y[i];
    vector<int> ans1(Q), ans2(Q);
    vector<int> cnt1(sz), cnt2(sz);
    int sum1 = 0, sum2 = 0;
    auto add1 = [&](int idx){
        if(cnt1[cmp.get(a[idx])]++ == 0) sum1 ^= hash[cmp.get(a[idx])];
    };
    auto erase1 = [&](int idx){
        if(--cnt1[cmp.get(a[idx])] == 0) sum1 ^= hash[cmp.get(a[idx])];
    };
    auto out1 = [&](int idx){
        ans1[idx] = sum1;
    };
    auto add2 = [&](int idx){
        if(cnt2[cmp.get(b[idx])]++ == 0) sum2 ^= hash[cmp.get(b[idx])];
    };
    auto erase2 = [&](int idx){
        if(--cnt2[cmp.get(b[idx])] == 0) sum2 -= hash[cmp.get(b[idx])];
    };
    auto out2 = [&](int idx){
        ans2[idx] = sum2;
    };
    Mo mo1(N);
    Mo mo2(N);
    REP(i,Q){
        mo1.add(0, x[i]);
        mo2.add(0, y[i]);
    }
    mo1.build(add1, erase1, out1);
    mo2.build(add2, erase2, out2);
    REP(i,Q){
        cout << (ans1[i] == ans2[i] ? "Yes" : "No") << endl;
    }
}

AtCoder Beginner Contest 249(ABC249)

atcoder.jp

A - Jogging

for文でそれぞれの移動距離を求める

提出コード

void solve(){
    int A, B, C, D, E, F, X;
    cin >> A >> B >> C >> D >> E >> F >> X;
    int t = 0, a = 0;
    for(int i=0;i<=X;){
        if(i + A <= X) t += A * B;
        else{
            t += (X - i) * B;
            break;
        }
        i += A + C;
    }
    for(int i=0;i<=X;){
        if(i + D <= X) a += D * E;
        else{
            a += (X - i) * E;
            break;
        }
        i += D + F;
    }
    if(t == a) cout << "Draw" << endl;
    else if(t > a) cout << "Takahashi" << endl;
    else cout << "Aoki" << endl;
}

B - Perfect String

大文字・小文字の判定と、setですべての文字が異なるかどうかを判定

提出コード

void solve(){
    string S;
    cin >> S;
    set<char> st;
    bool big = false;
    bool small = false;
    for(char c : S){
        st.insert(c);
        if('a' <= c and c <= 'z') small = true;
        if('A' <= c and c <= 'Z') big = true;
    }
    cout << (big and small and st.size() == S.size() ? "Yes" : "No") << endl;
}

C - Just K

bit全探索をする

提出コード

void solve(){
    int N, K;
    cin >> N >> K;
    vector<string> S(N);
    REP(i,N) cin >> S[i];
    int ans = 0;
    REP(i,1<<N){
        vector<int> cnt(26);
        REP(j,N) if(i >> j & 1){
            vector<int> _cnt(26);
            for(char c : S[j]) _cnt[c-'a']++;
            REP(k,26) if(_cnt[k]) cnt[k]++;
        }
        int tmp = 0;
        REP(j,26) if(cnt[j] == K) tmp++;
        chmax(ans, tmp);
    }
    cout << ans << endl;
}

D - Index Trio

予め、それぞれの要素ごとに個数をカウントしておく
$ A_j $ を固定すると、$ A_i $ は $ A_j $ の倍数となり、$ A_k $ は一つに定まるので、$ A_i $ を固定したときに $ A_j $ を調和級数で数えれば全体として $ O(N \log N) $ で求めることができる

提出コード

void solve(){
    int N;
    cin >> N;
    vector<int> A(N);
    REP(i,N) cin >> A[i];
    vector<ll> cnt(202020);
    REP(i,N) cnt[A[i]]++;
    ll ans = 0;
    REP(i,202020) if(cnt[i]){
        for(int j=i;j<202020;j+=i){
            int k = j / i;
            ans += cnt[i] * cnt[j] * cnt[k];
        }
    }
    cout << ans << endl;
}