CODINGAME SPRING CHALLENGE 2021 参加記
CodinGameのSPRING CHALLENGE 2021に参加しました。
twitterが盛り上がっていて楽しかったです。
結果
世界66位日本12位でした。
TLの知見ツイートにかなり助けられました。
学校別では世界11位日本2位でした。
11人参加していたんですが、10人がゴールド以上で凄い。
ルール
いなにわさんの記事が分かりやすいです。
最初に実装したものを書いた後、改善したことを説明しようと思います。
最初に実装したもの
UCB1のDUCTで、プレイアウトはうまくいかなかった（時間がかかり過ぎるし、高速化しても強くなる気がしない）ので、評価関数を使いました。
評価関数
得点=(この後ずっとwaitすると仮定した場合の最終的なsun)/3+
(スコア+(自分の木がある場所のrich-1)×s[その木のサイズ])×日付×3/23
s[4]={0.2,0.7,1.2,1.8}
自分の得点と相手の得点を計算して、
自分の得点>相手の得点の場合、1
自分の得点=相手の得点の場合、0
自分の得点<相手の得点の場合、-1
今後取得できるsun、現在のスコア、木がある場所のrichを得点に入れたい気持ちになった感じです。
高速化
使える場面が多そうで、自分的には非自明だった高速化を1つ紹介します。
DUCTで使うノードの構造体のメンバに、手ごとの累積ポイントを記憶する配列が欲しくなると思います。
これのサイズはノードによって違うので、速度が遅いvectorを使うか多めにサイズを取った生配列を使うかになってしまいそうなのですが、下のように大きな配列をグローバル変数に持っておけば必要な分だけ生配列を使えます。上手い構造体を書けばvectorと同じ使い心地で使えそう。
改善したこと
評価関数
早々に試合を諦めてWAITをしまくるのを直したかったので、評価関数が返す絶対値をmin(1.5,大きい方の得点/小さい方の得点)にしました。狙い通りに諦めるのが減った気がします。
seedの制限
高速化と、探索の質の向上のために現在のターンor１日の初めのターンのみSEEDをするのを許可しました。
行動の順番を決める
DUCTの探索中、1日の中では、
SEED→COMPLETE→GROW(2→3)→GROW(1→2)→GROW(0→1)→SEEDの順番で行わせるようにしました(例えば、GROW(1→2)をやった後は、その日の中では左３つはやらない)。
seedの範囲制限
自分の木が隣接しているマスにSEEDをするのを禁止しました。
これがLEGEND入りの決め手になりました。LEGENDに入った後、同じ方向で2マス進んだところに自分の木があるマスも禁止したらさらに強くなりました。
感想
自己対戦を自動で行ってくれるツールが流れてきたおかげで素早く強さを測定できてとても便利でした。ただ、自分で作ったものではないので不便な点が多かった（エラー出力が闇に消える、時間制限の変更ができない、測定が遅いなど）ので、自分で作れるようになりたいな〜〜
MCTSを高速化以外で改善するのは初めてで楽しかったです。
2021/03/02
ペンキの色
JOI 難易度7
解法は一瞬で思いついたけど、実装にかなり時間がかかった。
座圧してbfsをした。
強い人はUnionfindを使っていた。こっちの方が楽そう。座圧用の配列に各値を+1した値も入れたが、必要なかった。
Grouping
EDPC U
3^Nになるやつ。
AtCoder Jumper
青diff
答えは知っていた。ページxからはx*2とx*2+1をリンク先にする。10回移動したら1024x+1~1024x+1023に移動できる。
庭園
黄diff 試験管
2つの長方形は上下か左右に分けることができる。
上下に分けるパターンを考える(左右はBを90度回転したものを同じようにすればいい)。
ue[i]:(i行目までの区画を使ってできる長方形の総和の最大値)
sita[i]:(i行目以降の区画を使ってできる長方形の総和の最大値)
を求めればいい。2次元累積和を使えばO(N^3)で求めることができる。
Binomial Coefficient is Fun
黄diff
分からなくて解説動画を見た。天才だった。
2021/03/01
今日から再開する
Unfair Nim
黄diff
A[0]^A[1]==A[2]^...^A[N-1]となればいい。
2進法の下の位から、桁dpで移動する石の数を考えていく。
A[0]は上の位から借りているか、A[1]で繰り上がりが起きているか、の情報をdpに持たせる。
釘 (Nails)
JOI 難易度8
縦方向に見て、横にどれだけ伸びるかをまとめて求めた後、横方向に見て輪ゴムの中にあるかを求めた。
公式解説では斜めのimosをしたり、自分=max(自分, max(左上, 右上)-1)の性質を使ったりしていて、天才だった。
distribution - 冊子の配布 (Distribution)
JOI 難易度8
木の2乗dpみたいな感じでやるとO(n^2)になる。
通知
PAST O
解けなかった。想定解法を見て天才に思ったけど、PASTに出てるし、汎用性が高そうだから典型なのかな。友達が√M以上の人はT=1のクエリで愚直に通知を送らず、T=2のクエリのときに送られたかを見るようにする。そうすると、各クエリはO(√M)になり間に合う。
輪投げ
PAST O
DPを考えたけど無理だったので諦めた。
最小費用量で解ける。存在をすっかり忘れていた。思いついたとしても解けたかは微妙。正直、どんな問題を解けるのかがよく分かってない。......ライブラリを見ると「割り当て問題はこれ！らしい」と書いてあった。
typhoon - 台風 (Typhoon)
JOI 難易度9
イベントソートをした。台風の被害にあった数はBITとimosでいい感じにした。
2021/02/20
困った。書くやる気がでない
2021/02/18
Battle with E869120!
unrated
好き。(H-1,W)か(H,W-1)に最初に置いた人の負け。全体のマスから(1,1),(H-1,W),(H,W-1),(H,W)を除いたマスの数が奇数なら先攻、偶数なら後攻を選ぶと、(H-1,W)か(H,W-1)に置くことをを相手に押し付けることができる。
リスのお仕事
unrated
(今いる木の番号、直前に飛んだ隙間の長さ)を頂点とした拡張ダイクストラ。計算量が不安。頂点数は高々2*M。辺の数は(M/2)*(M)になる場合がありそう(木が3本あって①-②、②-③にそれぞれM/2本の枝がある場合)。ACがでたし、他の人もこの解法で通してるから間違ってるのかも。すぬけくんの地下鉄旅行が似てるらしい？
ヌクレオチド
unrated
N%2==0のとき、塩基列はa b c d d c b aのようになる。a b c dの中の0の数をxと置く。
転倒数は、(a b c dの転倒数)+(d c b aの転倒数)+x*(4-x)=x*(4-x)*2。
N%2==1の場合も同様に求めることができる。後は数式をこねる。二次方程式の解を求めるライブラリを書いた。詳しくは提出(
https://atcoder.jp/contests/iroha2019-day1/submissions/20243029)に書いた(かなり雑)。
ルーレット
unrated
まとめて計算するいつものやつ。
をあ ぷろぶれむ
unrated
「mid以上の数がK個以上ある」を満たす最大のmidが答え。セグ木上のにぶたんを実装した。上がにぶたん+セグ木(O(N*(logN)^3))で、下がセグ木上のにぶたん(O(N*(logN)^2))。
日記
競プロ楽しい。google hash codeに出ることになった。
2021/02/17
認証レベル
JOI 難易度8
各事務所で、「need[x]:x個の部屋を見学するために必要なレベル」を求めることができれば解ける。次に見学可能な(まだ見学していない)部屋の内、最小のレベルの部屋に見学することを繰り返すbfsをすれば損をすることはなさそう。priority_queを使って頑張る。
ABland Yard
黄diff
AとB両方に行くことができない頂点を消す操作を繰り返して、1個以上の頂点が残れば"Yes"っぽい→O(N^2)かかってしまうな～→解説を見るって感じだった。トポロジカルソートっぽくすればO(M+N)でできる。もう少し粘ればよかった……。
虚無2問
日記
チーム練(https://codeforces.com/gym/102785)をした(面倒だから問題については書かない)。
2021/02/16
解読 (Deciphering)
JOI 難易度8
以下のように定義する。
dp[i]:i番目の文字で終わる原文からi-1番目の文字まででできる原文を引いた総数
cnt[i][a]:i番目の文字までを考慮したとき、文字aで終わる原文の総数
dp[i]=sum(cnt[i-1][a](文字aとi番目の文字が連続することは禁止されていない) a='A'~'Z') - cnt[i-1][i番目の文字]となる。sum(dp)が答え。実際にはcntは一次元配列で実装した。
散歩
JOI 難易度8
N-1回の散歩で各交差点に何回訪れたかが分かれば解くことができる。(0,0)にはN-1回訪れている。(0,1)には(N-1+(0,0の最初の文字)==東?1:0)/2回訪れているって感じで求めていく。
Skate
黄diff
twitterを見る限り典型らしい。解説動画を見た。
行と列を分けた二部グラフを作る。#は辺になる。「この二部グラフが連結になる」と「スケートリンクに無駄はない」は同値。
日記
いろはコンDay1の残りを脳内ACした。明日実装する。
