- やった回: ABC330
- 成績: ABD3完 / 2ペナ(＋未AC6ペナ) / 97:36(ペナ込み)
- パフォーマンス: 637
緑復帰が遠い……このC問題が解けなかったのはだいぶ悔しかったです。
問題文の理解が追いつかず、B問題で地味に2ペナ食らっているのも悲しいところ。
Dは何とか解けて良かったけど、競プロ女子部の感想会で話を聞いていたらもっと話がシンプルに出来る案件で悲しかった。(でも知れてよかった)
A問題: ABC330-A Counting Passes
素直に点数がL以上の数をカウントしました。
B問題: ABC330-B Minimize Abs 1
題意がつかめないまま解いて無駄に食らった2ペナが悲しい。
最初に愚直にL-R間を二重ループしてTLE、その後解の規則性にうっすら気付いたけど詰めが甘くてWA、落ち着いてサンプルコードを改変してパターンを確認し、ちゃんと直してようやくAC。正直まだ題意がよく分かっていないのは秘密
C問題: ABC330-C Minimize Abs 2
(upsolveコード) atcoder.jp
Xの候補を1からMath.sqrt(D)まで探索していって、逆算で求められるYの候補を実際に計算して最小値を見つければいいよね、まではわりと真っ当なタイムでたどり着いており、実際大まかな方針としては間違っていなかった。が、条件反射でMath.sqrt(Y**2)をto_iしており、そこで探索対象を漏らしてしまいWAを重ねていたパターン。この手のミスがとてもつらい。
sqrtを取った後にfloor と ceilの両方を見る必要があることをRails Girls競プロ同好会での感想戦でいしりば～さんに教えていただき、あっさりACしたときは「えぇ…」って声が出ました。
探索対象としてfloor と ceil の両方を見ないといけない直感的な理解としてはwriterの方の解説動画が大変分かりやすかったです。
D問題: ABC330-D Counting Ls
私の解法としては累積和、数え上げ対象となる3つのoの組み合わせはL字状になるので、注目する点をL字の真ん中(？)に固定して、L字を90度ずつ回転させた4通りの組み合わせを検証すればいいよね、というのが基本のアイディア。
A方向にあるoの個数とB方向にあるoの個数を掛ければよいので、ある一方のL字でありうる組み合わせはシンプルに掛け算で求めることが出来る。あとはそれを残り3方向ぶんについても考えればよい。
あらかじめ累積和の個数を求めておけば計算コストとしては(これでも)シンプルになるので、N*Nのマスを全部見ていっても十分間に合う。
…んだけど、もうちょっと落ち着いてこの計算を式変形していくともっと簡単な計算で求められることを知ったのが競プロ女子部の感想会でのお話。
(row[0..i-1] * col[0..j-1]) + (row[0..i-1] * col[j+1..n-1]) + (row[i+1..n-1] * col[0..j-1]) + (row[i+1..n-1] * col[j+1..n-1]) = row[0..i-1] * (col[0..j-1,j+1..n-1]) + row[i+1..n-1] * (col[0..j-1,j+1..n-1]) = row[0..i-1,i+1..n-1] * col[0..j-1,j+1..n-1]
要するに縦横のoの個数から注目している点の分の1個をそれぞれ引いて掛けちゃえばよいのでは？ということで、累積和しなくてもよかったんですね。この手のコードをバグらせずに書くのちょっと苦手なので、すごい頑張ってバグ取りしたんだけどなぁ……
ということで、よりシンプルな計算でのコードはこっち。 atcoder.jp
今週も対ありでした、悲しみまくったこの回が後の糧になると信じるしかない回でした。
