接着剤の精進日記

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

AtCoder Beginner Contest 169(ABC169)

atcoder.jp

最近だめだこれ〜

A - Multiplication 1

A \times Bを出力
提出コード

void solve(){
    int a, b;
    cin >> a >> b;
    cout << a * b << endl;
}

B - Multiplication 2

結構難しい
0が含まれてたら答えが0になるのに注意
それ以外は順に掛け算をしていく
オーバーフローはcur \gt \frac{10^{18}}{a_i}で判定できる
提出コード

void solve(){
    int N;
    cin >> N;
    vector<ll> a(N);
    bool zero = false;
    REP(i,N){
        cin >> a[i];
        if(a[i] == 0) zero = true;
    }
    if(zero){
        cout << 0 << endl;
        return;
    }
    ll ans = 1;
    REP(i,N){
        if(ans > LINF / a[i]){
            cout << -1 << endl;
            return;
        }
        ans *= a[i];
    }
    cout << ans << endl;
}

C - Multiplication 3

doubleやlong doubleだと誤差で落ちる(本番はlong doubleでも通ったらしい)
小数点以下2桁までしかないので、stringなどで受け取って100倍にしてかけたあと100で割って切り捨てればいい
提出コード

void solve(){
    ll A;
    cin >> A;
    string b;
    cin >> b;
    ll B = 0;
    ll cur = 100;
    REP(i,b.size()){
        if(b[i] == '.') continue;
        B += cur * (b[i] - '0');
        cur /= 10;
    }
    ll ans = A * B / 100;
    cout << ans << endl;
}

D - Div Game

素因数分解をする
各素因数を1個、2個、…と取っていくのが最適
提出コード

vector<pair<long long, long long> > prime_factorize(long long n) {
    vector<pair<long long, long long> > res;
    for (long long p = 2; p * p <= n; ++p) {
        if (n % p != 0) continue;
        int num = 0;
        while (n % p == 0) { ++num; n /= p; }
        res.push_back(make_pair(p, num));//p^num
    }
    if (n != 1) res.push_back(make_pair(n, 1));
    return res;
}

void solve(){
    ll N;
    cin >> N;
    auto res = prime_factorize(N);
    ll ans = 0;
    for(auto x : res){
        int cur = 1;
        while(x.second > 0 && x.second >= cur){
            x.second -= cur;
            ans++;
            cur++;
        }
    }
    cout << ans << endl;
}

E - Count Median

中央値になる最大と最小の区間を求める
AとBをそれぞれソートをすると\frac{N}{2}番目の最小はA_{\frac{N}{2}}となる
同様に最大はB_{frac{N}{2}}となるのでB_{\frac{N}{2}} - A_{\frac{N}{2}} + 1が答え
偶数の時も殆ど同様で、(B_{\frac{N}{2}} + B_{\frac{N}{2} - 1}) - (A_{\frac{N}{2}} + A_{\frac{N}{2} - 1}) + 1が答えになる
最小と最大の間は全部作れるいつものあれ
本番はimosっぽくやってWA取れなかったけど素直にソートで良かったね…
提出コード

void solve(){
    ll N;
    cin >> N;
    vector<ll> A(N), B(N);
    REP(i,N) cin >> A[i] >> B[i];
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    if(N & 1){
        ll a = A[N/2];
        ll b = B[N/2];
        cout << b - a + 1 << endl;
    }
    else{
        ll a = A[N/2-1] + A[N/2];
        ll b = B[N/2-1] + B[N/2];
        cout << b - a + 1 << endl;
    }
}

NOMURA プログラミングコンテスト 2020

atcoder.jp

競プロなんもわかんね〜

A - Study Scheduling

分に直してから計算する
提出コード

void solve(){
    int H1, M1, H2, M2, K;
    cin >> H1 >> M1 >> H2 >> M2 >> K;
    ll sum = H2 * 60 + M2 - (H1 * 60 + M1);
    cout << sum - K << endl;
}

B - Postdocs

ぱっと見わかんなくてDP書いて思いとどまった
'?'に’D'を置くのが最適になる
提出コード

void solve(){
    string T;
    cin >> T;
    REP(i,(int)T.size()){
        if(T[i] == '?') T[i] = 'D';
    }
    cout << T << endl;
}

C - Folia

解ける人多くて困った
葉から考えて深さdのときに頂点として選べる最小と最大の区間を求める
その後、上から取れる最大と求めた区間の範囲との最大を貪欲に取っていけばいい
もしくは、最初から上から見ていくとする
深さdを見ている時、その頂点数の最大は深さd-1の葉を除いた頂点数の2倍まで最大で取れる
また、深さdの葉ではない頂点は深さd+1以降で葉となる頂点が存在するため、\sum^{N}_{d+1} A_i以下を満たす
この2つの条件を満たす範囲のうち最大のものを貪欲に取っていけばいい
提出コード

void solve(){
    int N;
    cin >> N;
    vector<ll> A(N+1), cum(N+1);
    REP(i,N+1) cin >> A[i];
    cum[0] = A[0];
    for(int i=1;i<=N;i++) cum[i] = cum[i-1] + A[i];

    if(N == 0 && A[0] == 1){
        cout << 1 << endl;
        return;
    }
    if(A[0] != 0){
        cout << -1 << endl;
        return;
    }

    ll cur = 1, ans = 0;
    REP(i,N+1){
        // cout << i << " " << cur << endl;
        if(cur - A[i] < 0){
            cout << -1 << endl;
            return;
        }
        ans += cur;
        cur -= A[i];
        if(cur > cum[N] - cum[i]){
            cout << -1 << endl;
            return;
        }
        cur = min(cur * 2, cum[N] - cum[i]);
    }
    cout << ans << endl;
}

Codeforces Round #645 (Div. 2)

codeforces.com

A. Park Lighting

 \lceil \frac{n \times m}{2} \rceilを出力
提出コード

void solve(){
    int n, m;
    cin >> n >> m;
    cout << (n * m + 1) / 2 << endl;
}

B. Maria Breaks the Self-isolation

ソートをし、小さい方からシミュレートをする
提出コード

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    REP(i,n) cin >> a[i];
    sort(a.begin(), a.end());
    int cur = 1;
    int num = 1;
    REP(i,n){
        if(cur + num - 1 >= a[i]){
            cur += num;
            num = 1;
        }
        else{
            num++;
        }
    }
    cout << cur << endl;
}

C. Celex Update

editorialの図がわかりやすかった

和が最小の経路を基準にし、最大の経路まで何通りあるかを考える
そうすると図のように(x2 - x1) \times (y2 - y1)通りあることがわかる
よって、これに最小の経路を加算したものが答え
多倍長とか使えば最小と最大の間は全部作れるいつものあれかな
提出コード

void solve(){
    ll x1, x2, y1, y2;
    cin >> x1 >> y1 >> x2 >> y2;
    ll dx = x2 - x1;
    ll dy = y2 - y1;
    cout << dx * dy + 1 << endl;
}

D. The Best Vacation

各月の和でしゃくとりをする
この和がxに足りないときは、余った分を加えてあげればいい
年度を跨いでもいいので、2周分取っておくと楽
提出コード

void solve(){
    ll n, x;
    cin >> n >> x;
    vector<ll> d(2*n);
    REP(i,n){
        cin >> d[i];
        d[i+n] = d[i];
    }
    int right = 0;
    ll sum = 0;
    ll sumDays = 0;
    ll ans = 0;
    for(int left=0;left<n;left++){
        while(right < 2*n && sumDays + d[right] <= x){
            sum += d[right] * (d[right] + 1) / 2;
            sumDays += d[right];
            right++;
        }
        ll rem = x - sumDays;
        ll tmp = sum;
        if(rem > 0) tmp += rem * (d[right] + d[right] - rem + 1) / 2;
        chmax(ans, tmp);
        if(left == right) right++;
        else{
            sum -= d[left] * (d[left] + 1) / 2;
            sumDays -= d[left];
        }
    }
    cout << ans << endl;
}

Codeforces Round #644 (Div. 3)

codeforces.com

A. Minimal Square

2a \geq bなら2aをそうでないならbを正方形の辺として使う
提出コード

void solve(){
    int a, b;
    cin >> a >> b;
    if(a > b) swap(a, b);
    if(2 * a >= b) cout << 2 * a * 2 * a << endl;
    else cout << b * b << endl;
}

B. Honest Coach

ソートをし、隣接要素の差の絶対値の最小を出力すればいい
提出コード

void solve(){
    int n;
    cin >> n;
    vector<int> s(n);
    REP(i,n) cin >> s[i];
    sort(s.begin(), s.end());
    int ans = INF;
    REP(i,n-1){
        chmin(ans, abs(s[i+1] - s[i]));
    }
    cout << ans << endl;
}

C. Similar Pairs

偶数のものと奇数のものの数を数える
このとき偶数の数と奇数の数が両方2で割り切れるものなら"YES"
そうでないときは、偶数のものと奇数のものを1つずつ使ってペアを作ることができれば"YES"になる
したがって、そのようなときは差が1であるペアを見つければいい
提出コード

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    int even = 0, odd = 0;
    REP(i,n){
        cin >> a[i];
        if(a[i] & 1) odd++;
        else even++;
    }

    if(even % 2 == 0 && odd % 2 == 0){
        cout << "YES" << endl;
        return;
    }
    sort(a.begin(), a.end());
    REP(i,n-1){
        if(a[i+1] - a[i] == 1){
            cout << "YES" << endl;
            return;
        }
    }
    cout << "NO" << endl;
}

D. Buying Shovels

nの約数を調べる
nの約数を調べていき、k以下で最大のものを見つければいい
提出コード

void solve(){
    ll n, k;
    cin >> n >> k;
    ll ans = 0;
    for(ll i=1; i*i <= n; i++){
        if(n % i == 0){
            if(i <= k) chmax(ans, i);
            if(i != n / i && n / i <= k) chmax(ans, n/i);
        }
    }
    cout << n / ans << endl;
}

E. Polygon

操作を考えると、n行目とn列目以外で'1'がある場合
行方向もしくは列方向の1つ後ろに'1'がなければいけない
そのため、これを満たすかどうかを全部調べればいい
提出コード

void solve(){
    int n;
    cin >> n;
    vector<string> fi(n);
    REP(i,n) cin >> fi[i];
    bool ok = true;
    REP(i,n) REP(j,n){
        if(fi[i][j] == '1'){
            if(i == n-1 || j == n-1) continue;
            if(fi[i+1][j] == '1' || fi[i][j+1] == '1') continue;
            ok = false;
        }
    }
    if(ok) cout << "YES" << endl;
    else cout << "NO" << endl;
}

F. Spy-string

i文字目を考えたときにいくつの文字列が異なるものになるかを考える
i文字目に出現する文字の種類をcnt_iとすると
cnt_i - 1個の文字列がsとi文字目が異なる文字列となる
sと1文字異なるものが許されるのはn個までなので\sum^{m}_{i=1} (cnt_i - 1) \gt nのときは作れない
そうでないときは、dfsで作ることの出来る文字列を全列挙し、条件に合うものを出力する
提出コード

void solve(){
    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    REP(i,n) cin >> a[i];
    vector<int> cnt(m);
    vector<vector<char>> c(m);
    int diff = 0;
    int ma = 0;
    REP(i,m){
        REP(j,n){
            c[i].push_back(a[j][i]);
        }
        sort(c[i].begin(), c[i].end());
        c[i].erase(unique(c[i].begin(), c[i].end()), c[i].end());
        cnt[i] = (int)c[i].size();
        if(cnt[i] > 1) diff++;
        chmax(ma, cnt[i]);
    }

    if(diff == 0 || diff == 1){
        cout << a[0] << endl;
        return;
    }

    int sumDiff= 0;
    REP(i,m) sumDiff += cnt[i] - 1;
    if(sumDiff > n){
        cout << -1 << endl;
        return;
    }
    string ans = "";
    auto dfs = [&](auto && self, string cur, int len) -> void{
        if(len == m){
            bool ok = true;
            REP(i,n){
                int cntDiff = 0;
                REP(j,m) if(a[i][j] != cur[j]) cntDiff++;
                if(cntDiff > 1){
                    ok = false;
                    break;
                }
            }
            if(ok){
                ans = cur;
                return;
            }
            return;
        }
        if(cnt[len] == 1){
            cur += a[0][len];
            self(self, cur, len+1);
        }
        else{
            for(auto c1 : c[len]){
                cur += c1;
                self(self, cur, len+1);
                cur.pop_back();
            }
        }
    };

    string cur = "";
    dfs(dfs, cur, 0);
    if(ans == "") cout << -1 << endl;
    else cout << ans << endl;
}

G. A/B Matrix

na = mbのときのみ構築することが出来る
このようなとき各行にa個ずつ各列に連続して並べ、次の行は前の行の最後においた列の次からまた連続でa個置いていくように作ればいい
提出コード

void solve(){
    ll N;
    cin >> N;
    vector<ll> a(N), b(N);
    ll sum = 0, mi = LINF;
    REP(i,N){
        cin >> a[i] >> b[i];
        if(a[i] > b[i]) chmin(mi, b[i]);
        sum += a[i];
    }
    if(a == b) cout << 0 << endl;
    else cout << sum - mi << endl;
}

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

はじめに

CodinGameのコンテスト(CodinGame Spring Challenge 2020)に参加しました
結果は世界61位(LEGEND)、日本12位と健闘出来たかなと思います
Legendリーグは114人いて日本人が18人なのでLegendのうち6人に1人くらいが日本人だったみたいですね
みんな強い
f:id:tkm-kyudo:20200518222958p:plain
f:id:tkm-kyudo:20200518223030p:plain

ルール

詳しいルールはツカモさんが記事にしているのでそちらを参照するのが良いと思います
簡単に言うと、パックマンで相手よりたくさんポイント(ペレット)を集めたほうが勝ちで、パックマンのタイプによってじゃんけん要素が加わった感じです
tsukammo.hatenablog.com

やったこと

リーグ別に段階を踏んで改善していったものも書きますが、ここでは最終的にどんなことをやったのかだけ簡単にまとめておきます
基本的には貪欲とルールベースで評価関数によって行動を決定していました
1. 各ターンごとに自機の居る位置をまとめてpriority_queueに入れて、評価関数に応じたスコアの高い順に20MOVEまでの最短経路を評価の高い順に探索する
2. ペレットの評価はスーパーペレットが100、視認したペレットが10、あるかどうかわからない未探索のペレットは5で決め打ち
3. 近くにあるペレットの価値が高く、遠くにあるものほど価値は小さくなるので、距離の二乗分の重みを考慮
4. 衝突時は相手にリソースを打たせるルールベース
5. 相手が袋小路にいる(移動できるマスが3マス以内)でabilityが使えない状態ならkillするようにスコアを加算
他にも細かい点はありますが、だいたいこんな感じでやっていました

Wood2

最初見たときはtron battleっぽいなって思ったのでbfsで色塗りゲームをする感じで多く移動できる4方向を選択するものを組んで昇格

Wood1

いきなり複数体操作が可能になりました、しんどい
複数体が色塗りで自分の領域を作ると考えると、 floodfillが使えそう
なのでfloodfillで自分の動ける領域を作り、その中で貪欲にpelletのある方向に動くようにした
また、スーパーペレットは取らないとかなり損なので残っている間は貪欲に取りに行く
これをやると昇格

Bronze

Bronzeになるとabilityが解禁されて、情報が不完全になる
取り敢えず、見えているペレットだけを考えることにする
スキルはSPEEDが強そうなのでSPEED使えるときは使うようにする
すでに取られているのに、あると思い込んでペレットを取りに行くような動きがあったので、視界にあるのに、ペレットの情報が与えられていなかったらすでに取られたものとして補正する
ここまでのものを提出すると初日は日本5位、世界97位になった

この時点での負けパターンとして、相手をまったく考慮していなかったので不利な相手が見えている状態でも突っ込んでしまう場合が結構見られた
純粋に稼ぎ負けるパターンもあった
この時点では、スーパーペレットがあれば貪欲に取りに行って、それ以外は4近傍でペレットがある方向に貪欲に取りに行っていたのでたくさん残っている部分を取り損ねるみたいな動きが目立ちました

見えている部分は情報として取り込んだほうが自明に強いのでその部分を実装
敵が見えているときは、敵の移動可能マスを計算し、基本的には近づかないようにする
場合によっては追いかけたり、衝突したほうが良かったりするけど一先ず敵から逃げる方針で実装

評価関数も入れて4方向のどっちが良いかを探索したりもしたけどpacが反復横跳びしてしまったので一旦断念(反復横跳びみんな通る道だと思う)

ここまでのを提出するとBronzeで32.5とかでした

4方向だと取りこぼしたりしていたので未探索マスがあれば今の位置からそこに向かわせるように実装

silverが解禁され無事即昇格
Bronzeボス手元で数戦しただけなんだけど結構killしてきて殺意高くなかった?

Silver

初動で大体Silverの真ん中らへんでした
敵が見えているときの情報を使うことを取り敢えず考えました
味方に対してだけfloodfillしていたのを敵に対してもfloodfillするように実装
この時点での問題点としては、floodfillで移動できないときに未探索マスを選ぶようにしていたが、その経路上に敵がいても構わず突っ込んでしまうのでそれでやられることが多かった
敵のfloodfillも考慮してたんだけど、その影響か集める効率が悪そうな気がした
固まっているところを連続で取っていったほうが効率が良いので連結成分で考慮してみる
連結成分を実装してみたが、評価が悪かったのか微妙だった

この辺りのときに、各pacを行ける範囲でbfsし、その中でスコア最大の経路を選択するという方針を思いつく
1体ずつbfsでスコア最大の経路を選択しその経路は次のpacは通れないようにする、ということで味方同士の衝突も避けれそう
そうすると、基本的には衝突するときは敵との衝突になるのでその管理も楽そうになる、天才では?

ついでに、敵をfloodfillでしていたけど敵の移動可能マスには近づかないようにロールバック
経路選択を20MOVEまで見るようにしたけど近いところのものを取らないで遠くの方にばかり行くようになってしまったので、(MAX_MOVE - distance)の重みを追加し、近いところを優先するように

ボスが解禁され、無事Goldへ

Gold

Gold入って最初のほうはリプレイ見て考察メインでしてました (体調崩したのもある) リプレイを眺めていると、後半の取りこぼしが結構目立つ
20MOVEで見ているので、近くのものよりも遠くにたくさんある(あると思いこんでいる)ほうに行ってしまう動きがあった
そのため先程の距離の重みを二乗にしてみた
これが結構効いたっぽい

他には

// 0 : なにもない, 1:ペレット
0S00  
#1#0  
#11G  

みたいなS -> Gの経路があったときにS -> 1 -> 1 -> 1 -> Gが最適
bfsだとS -> 0 -> 0 -> 0 -> Gと通ってしまうような試合がいくつかあった

これを解決するために、bfsをやめてダイクストラを使うことにした
価値の高い順に20MOVEの最短経路を求めるようにした
これを実装すると全体95位で2桁順位復帰、やったね

閉路に居るときにその場待機しちゃうことがあったので移動1マスごとに1重みづけを加えた
また、前のターン通って来た道に引き返して別のところに向かうという動きも多かったので、戻る移動にマイナス補正をかけた

この時点では、各pacごとに独立にダイクストラしていたが、まとめてpriority_queueに突っ込むことにした
これが結構良くて、各マスは1回しか訪れないため、味方の衝突が減ってまたいい感じにバラけて移動するようになってくれた

Legendが解禁されてボスが出現
初動のLegendが20人くらいでめちゃくちゃボスつえーとなっていた

この辺でLegend厳しいか?となり結構しんどかった

引き返す移動にマイナス補正をかけていたけど、そのせいかその場で立ち止まっちゃうpacがいたので一旦削除

流石にじゃんけん要素そろそろ入れないとやばいかな、と思いじゃんけん要素を解禁(今までしていなかったんですか?)
自分の実装だと衝突時には敵との衝突がほとんどなので、前のターン衝突していてabilityが使えるときは有利な手にswitchするように変更
Gold帯だとこれがかなり効いたように感じて、Gold下位との対戦成績が段違いに安定した気がします
これでGold1桁になり、放置して見守っていると無事Legend昇格!嬉しい!

Legend

Legendに到達するので燃え尽きたのか、正直あまり改善できず、パラメータ調整とか、ちょっとしたやつを追加するだけでメイン部分は殆どいじれませんでした

前に連続してペレットを取りたいから連結成分で見ていたけど、その部分をcomboボーナスとしてスコアに加算
ちょっと良くなった気がする

Goldのときには衝突時決め打ちswitchで大体取れてたんだけどLegend帯だと後出しが増えてきたので、後出しに変更

Goldのときは気にならなかったけどLegendだと後半の取りこぼしがまた目立つようになった
自分の得点と相手の得点から今の盤面状況を推測し、残りのペレットが大体30%くらいになったら近くのペレットの重みを増やして取りこぼしを減らすように変更

上位勢のリプレイを見ていると相手を確定でkill出来る状況ならkillするような動きが強いと思ったのでそれを実装
具体的には相手の移動可能マスが3マス以内で、cooldownがそれより大きく、自分の手が有利ならkillするように重み付けをした

Legend帯だと中々そういう状況にならないのでめちゃくちゃ効いたかはわからないけど、killするようになってそれで勝てる試合もあったので良かったんだと思う
もうちょっと積極的にkillしに行っても良かったけど実装が間に合わず

大体こんな感じでシステス前の暫定順位が61位
最終順位も61位でフィニッシュ

10日間フルでやり続けたので疲れました、楽しかった

最終提出のコードは627行でした
もう少し色々実装すべきだったかな

やりたかったこと

1.貪欲ベースで20MOVE読みしていたので、相手のほうが近いスーパーペレットを追いかけたり、食べられたりする動きが多かったので、初手を工夫したかった
2.ビームサーチなどでもう少し経路探索を工夫したかった
3.未確認のペレットの価値を5で決め打っていたけど盤面状況によって期待値を決めたかった
4.敵の行動予測をやりたかった
5.味方pacが衝突していて、残りのペレットがそのpacが取りに行こうとしている時、他のpacが反復横跳びしちゃうので、探索のときの順番を変更したかった

知見

交差点で止まると多くの情報を見られるので交差点であえて止まる
交差点の間隔の偶奇が一定なので交差点でSPEEDを使うと必ず2マス移動で交差点に止まれる
順番の考慮が結構効くらしく、順番を焼き鈍したりするといい
敵の位置予測をすると結構パターンが絞れるらしく、有利な相手に衝突する確率の高いマスに移動出来たりするかも?

感想

10日間ほぼずっと考え続けて疲れたけどめちゃくちゃ楽しかった
前回のOcean of Codeは実装で頭がやられたのと†人生†中だったのもあってあまり取り組めずSilverだったので今回Legend取れて嬉しい
序盤に割と当たり方針を引けて結局最後までその方針で走り続けられたんだけど、逆にLegend上がってからはあまり他のことを試せなかったのでもう少し最初の方に色々試してみても良かったかも
次回も参加します!!(修論とかでやばそうだけど)