RTA in Japanを見たり、ゲームをやっていたりしたら気がついたら5時前だった。
13時からチーム練があるのでやべえと言いながら急いで寝る。
起床後、虚無でstreakを繋いでチーム練に備える。
2020-2021 ACM-ICPC Brazil Subregional Programming Contest
https://codeforces.com/gym/102861
nowcowとのチーム練。
くれそんとおるふぇが朝までゲームをやっていたせいで出られず、2チームとも2人になっていた。
問題を後ろから読んでいく。とりあえず問題文が長かったりやばそうな図がある問題を飛ばして、短めのHを読み始める。
問題の制約から適切なビット列を作成して桁DPをやればよさそうだなと思う。実装が重そうなので流石に初手からやるのはやめておこうと思い、順位表を見るとGが解かれていたのでGを解く。AC(~0:08)
Bを相方に任せてFをやる。ぱっと見丁寧に実装をするだけの問題。丁寧に実装してAC(~0:43)
相方にAを任せていたが、期待値DPの遷移が分からないらしい。自分もよくわからないので困ったねと言っていた。勉強します。
Lもまぁいつものという感じで縦横と斜め2方向に文字種別の累積和を取って、頑張る。頑張るとACが出る(~1:37)
Hは最初の方に考察をしていたので詰める。
どんなに2個の箱も、重いほうは軽いほうの少なくとも2倍の重さはあるのでテキトーにビット列に変換したくなる。なるね
nCkの中でx 以下になるような最大のビット列を作り、あとは丁寧に桁DP
互いに独立なdp1とdp2を作っていたのだが、1か所dp1からdp2に遷移させており、1ペナ。実装が下手くそ(~2:17)
Eは区間に収まるような最も上の人からその区間に対するimosをやりたい気持ちになるので、ダブリング+DFSでBITでいもすをするとAC(~3:18)
Nがバグっているらしいのでコードを眺める。何でバグっているのか分からん。終わり。
コンテスト後にコーチモードをonにしてみてみると、どうやら1か所、非本質的なところで配列外参照をしていた。泣いた。
書き直したコードが通ったとの報告を受けたので、Iを読む。
根からDFSで、{それ以下が全部わかっている, 1個以外全部わかっている}をもって計算するとできそう。
これをするとmulが途中で0になった時に破滅する。
ll mul = 1;
for(auto i:v[p]){
auto t = dfs(i);
mul *= t[0];
mul %= mod;
g.push_back(t);
}
ll res = 0;
for(auto [x,y]:g){
res += (((mul * modinv(x))%mod) * y)%mod;
res %= mod;
}
こんな感じに左右から積を取っておこう。
vector<ll> l,r;
l.push_back(1);
r.push_back(1);
for(auto i:v[p]){
auto t = dfs(i);
g.push_back(t);
}
for(int i=0;i<(int)g.size();i++){
l.push_back(l.back() * g[i][0] % mod);
r.push_back(r.back() * g[(int)g.size()-1-i][0]% mod);
}
reverse(all(r));
ll res = 0;
for(int i=0;i<(int)g.size();i++){
auto [x,y] = g[i];
ll t = (l[i] * y) % mod;
t *= r[i+1];
t %= mod;
res += t;
res %= mod;
}
結果は8完85位
1人足りないので、中難易度の問題を解ききる前に時間切れになってしまったし、ペナも多め。
人生
お隣の天使様の読書を再開した。
次買うラノベ何にしようかしらねと言っている。
食事とゲームをしていたら一日が終わっていた。
TwitterのAPI申請が通ったのでtotori_nyaaアカウントのツイ消しを始めた。
ネットに落ちていたコードをそのまま使っただけなので何も手を動かしていないけど。
何時間か動かして5万件くらいは消せた。
研究していなくてピンチ!これからやります。
こどふぉのGood bye 2020は出ません。