- やった回: ABC332
- 成績: ABCD4完 / 0ペナ(＋未AC1ペナ) / 50:01(ペナ込み)
- パフォーマンス: 1343🎉
いやー、久々の緑復帰です、めでたい！あとRatedでは初めての水色パフォ*1でびびりました。
D問題が競プロ始めたての頃にバチャって2完で終わってしまったトラウマC問題をちゃんと乗り越えた結果取れている、というのが個人的には感慨深いです。
入緑4回目なのでそろそろ緑で安定したいーー
余談としてABCEのグッズ問題で都度SUZURIの商品ページにリンク張ってあるのが何だか面白い。
A問題: ABC332-A Online Shopping
購入金額の合計を取り、送料無料ラインを超えていなければ送料を足す。
Rubyはこういう条件式＋代入を1行でするっと書けるのが気持ちいい。
B問題: ABC332-B Glass and Mug
作業回数の上限が100回だそうなので、素直にシミュレーションしました。
C問題: ABC332-C T-shirts
文字列を0で区切っていって必要な情報を集めていく。
- とにかく1か2のどちらかが連続で続く日数の最大値
- とにかく1か2のどちらかが連続で続く期間の中で、競プロイベントが入る日数の最大値
- ただし、1が最大値になる期間と2が最大値になる期間は一致しない可能性があるので個別に加算処理をする必要がある
上の2つが求められたら、必要そうなTシャツの枚数を算出する。
- 1の値から無地シャツの枚数を引き、1以上になったら何でもいいのでTシャツを増やさないといけないが、無地のTシャツは増やせないのでロゴTシャツを増やすしかない。
- 2の値はそのまま必要なロゴTシャツの枚数になる
で、↑の値のうちどちらか大きい方が答えになる。
D問題: ABC332-D Swapping Puzzle
行と列の組み合わせ全探索と、バブルソートのシミュレーションによる転倒数の算出の組み合わせ。
問題のサンプルだと列入れ替え→行入れ替え→列入れ替えの順で処理しているんだけど、これ別に行の入れ替えやった後に列の入れ替えをまとめてやってもよいので、まずはとにかく行と列でそれぞれインデックスの並べ替えをして、もう片方と一致するかを調べる。ここまでの類題はこのときのやつかな。
一致する組み合わせが見つかれば処理をする回数の最小値が分かればよいので、例のトラウマ問題を思い出しつつバブルソートをシミュレーションして転倒数を出せばOK。
ところでちゃんと計算してないんだけど、バブルソートの計算量を考えると実はansの初期値をh * w + 1にするのはわりとデタラメなのでは？という感じがするんですが最悪ケースで確認したら一応それよりは多い値になるっぽいので安心しました。でもこういうのはよっぽど考察の余裕がない限り Float::INFINITY にしておくのが無難でよいと思います。
こういう、ちゃんと過去の精進が実を結ぶ感じの正解はとてもうれしいですね。
BFSで解く別解があるみたいなので、それも出来るようにしておいた方がいいんだろうなぁとも思っています。
E問題: ABC332-E Lucky bag
(コンテスト中にWAしたコード) atcoder.jp
何となくARC167-Aを連想しつつ、ソートして二分探索してみたんだけどやっぱりそうじゃないよねぇと言う感じで諦めました。どうやらDPするらしい。 ちょっと現時点で解説を理解しきれる自信がないので、後日やろうと思います。
ということで、今週も対ありでした！
*1:Unratedの推定パフォとしてはARC167で取った
