ABC194のバチャをした。難易度的には今の自分にちょうどいい感じだったと思う。あと少しでFが解けなかったのが悔しい。バチャ終了後5分くらいでACした。
Bで1WAした。(i % 2) xor (isupper(s[i])という条件式を書いたのだが、それを(i % 2) != (isupper(s[i]) ? 1 : 0)に変えたら通った。マジ？
どうやら調べてみるとisupperが返す値は規格上「0か1」ではなく「0か0以外」らしい。手元だと通ったのだが、おそらくその勘違いとたまたま一致した挙動をしてくれてしまっていた。規格厳密合致プログラムへの道は険しい。
Dに思わぬ苦戦を強いられた。掛け算&不等式でのオーバーフロー対策(競プロフレンズの匂いがプンプンするぜ)の他、「n進法とみなして得られる値でm以下となるものの種類」を「n進法とみなして得られた値がm以下となるnの種類」と勘違いしていたのが原因でバグらせた。
2桁以上の数字であれば、異なるnでn進法として解釈すれば必ず異なる数値になるが、1桁の数字だと逆に何進法でも同じ数値になる。ここだけ場合分けしてちょっとだけアドホックな実装が必要になる。
Eがアフターコンに弾かれた。何かと思ったのだが、自分のダイクストラのライブラリがバグっていることに気付いた。これは思わぬ収穫だった。危ない危ない。
どうやら「この頂点はすでに訪れた(=最短距離が確定した)」フラグを今まで管理してなかった。そのせいで無限ループになっていたのだった。考えてみればダイクストラは一回確定した頂点はもう考えなくていいのが売りなわけで、それをふいにする実装をしていたわけだ。何で今まで落とされなかったんだこれ？
ダイクストラに手を入れるような問題が緑diffとは怖い環境になったもんだと思う。
DPテーブルの値が有効な値かどうかを判定するためのフラグを別のDPテーブルで管理する、ということを覚えた。
Fで$dp[m][i][k][r] := i番目までの素材からk種類とって\mod mでの余りが r の場合の最大値$というDPを考えたのだが、当然$i < k$はありえないし$k=0, r > 0$という場合もありえない。当初こういうケースを一々そういう式で弾いていたのだが、値の有効性を管理する別のテーブル$dpe[m][i][j][k]$を考えた方が楽で確実なことに気付いた。値のDPテーブルの遷移と一緒に遷移すればいいだけで簡単に対応がとれる。
DPを久しぶりに書くとやっぱりちょっと手間取る。といっても結局ちょっと考えれば書けるのでそんなでもないけど。自転車に乗るみたいだ。
DPの小手先テクとダイクストラのライブラリ修正で結構得るものがあったコンテストだった。出場してたら(+Eのアフターコンが元からあったら)コンテスト後に発狂してたと思う。
掛け算不等式を割り算にしてオーバーフロー回避するやつの正当性を二度と考えたくないでござるという精神でこういうライブラリを作った。
bool ineq(lint a, lint b, int op, lint c) {
if (op == '<=')
return !ineq(a, b, '>', c);
if (op == '<')
return !ineq(a, b, '>=', c);
if (op == '>') {
if (a == 0)
return 0 > c;
if (a >= 0 && c < 0)
return ineq(a, -b, '<', -c);
if (a < 0 && c < 0)
return ineq(-a, b, '<', -c);
if (a < 0 && c >= 0) {
a *= -1;
b *= -1;
}
return b > c / a;
}
if (op == '>=') {
if (a == 0)
return 0 >= c;
if (a >= 0 && c < 0)
return ineq(a, -b, '<=', -c);
if (a < 0 && c < 0)
return ineq(-a, b, '<=', -c);
if (a < 0 && c >= 0) {
a *= -1;
b *= -1;
}
if (c % a == 0)
return b >= c / a;
return b > c / a;
}
static_assert("unknown operator");
}a*b>cを判定したいときにineq(a, b, '>', c)とか書ける。
ABC186のバチャをした。A~Dは言うことなし。
EはCRT(中国剰余定理)だった。最近CRT流行ってるの？ABC193-Eで履修したので解けた。
CRTだと分かればもう一瞬で解けてしまうかに思われたが、$S\geq K$の場合があるのでS%Kをとらなければならないとか、$0 \mod lcm(K, N)$になる場合があるのでそのときは0ではなくlcm(K,N)を使わなければならないとか、そのへんの調整がパッとできずに苦戦した。CRTをだいたい理解はしたがまだ慣れてはいないらしい。
Fはまあ、ちゃんと考えて解けたのでそこは楽しかったけど、今一つどのへんに学びを見出せばいいのか分からない。学べるものはあると思うんだけど。
包除で「右→下の順で行けるマス」∪「下→右の順で行けるマス」を「右→下の順で行けるマス」+「下→右の順で行けるマス」-「両方の順で行けるマス」に変換するのはもうちょっと素早くというかノータイムで発想できてよかったかなと思う。ちょっとそこに時間がかかってしまった。
そこからセグ木を使ってX軸とY軸を総合して考えていく部分はなんとか自力で思いつけたのだが、どういう思考回路をもっていたら早めに答えに辿り着けたんだろうかと思う。答えを知って考えれば自明も自明なんだけど。
ABC187のバチャをやった。
Dで得と損の差をとってソートがスッと出てきたのが良かったと思う。かなりシンプルな問題ではあるけど、シンプルな問題でちゃんと出せたのはより難しい問題でもその発想が出せる自信になる。
Eは基本の発想はすぐに出たのに実装でかなり手間取ってしまった。全方位木DPみたいな感じで根まで吸い上げる→枝葉まで分配みたいなコードを書いたが、添え字ガチャガチャしてバグらせまくって死んだ。なんとか通せたがあまりにも遅すぎる。
解説見ると葉から根に向かって足していく工程は根から葉に下ろしていくコードに書き換えられることが書いてあった。なるほどだけどそれは気づけん…
Fは良く分かんない。適当に部分グラフから完全グラフを見つけて取り去っていけばいいかと思ったが、取り去る順序によっては最小値が得られない。日を改めて考える。
Categories: 未分類