0.はじめに
最近若干調子上向きの中臨んだABC372。
A・B・Cを解いた後、Dは解き方が思いつかず
Eは何とか行けそうだったので挑戦しましたが
TLEは消せずあえなく時間切れ。
それでも今のレートでは3問解けただけで+9と
微増でした。
1.A - delete .
pythonだと地味にめんどくさい文字列操作系問題。
素直に以下の手法で解きました。
入力する文字列をリスト化してリストSに読み込み
回答用文字列ansを空で定義
Sから一文字ずつ読み出し、”."以外をansに加えていき
最後にansを出力して終了
https://atcoder.jp/contests/abc372/submissions/57953706
2.B - 3^A
Bにしては難しくない？と思った問題。
回答を見たら3進数に変換して解くとあり
目からうろこでしたがまぁ、思いついた以下の実装。
【実装】
1.Mをインプット
2.回答用リストansを空で初期化
3.添え字iを10→0で1ずつ減らすfor文で以下の処理
-1.Mが3のi乗以上の間以下を繰り返す
-1.ansにｉを追加
-2.Ｍから3のｉ乗を減算
4.ansにM回0を追加(試行錯誤中に入れたロジックなので実際は不要)
5.ansの長さと、中身を出力して終了
https://atcoder.jp/contests/abc372/submissions/57961871
3.C - Count ABC Again
普通にクエリーごとにABCをカウントしていたら間に合わないので
クエリーで変更される部分だけABCが減ったり増えたりしないかをチェックすることで
高速化を図りました。
【考え方】
1.N、Q、リストMを読み込む
2.回答用変数ansを0で初期化
3.Mを頭からチェックし、ABCの数を数えansにセット
4.以下、クエリーをQ回繰り返し
-1.X、Cを読み込み
-2.置き換え先M[X]がAorBorCの時
置き換える前の状態で置き換え先を含む文字列がABCをなしており、かつ
Cが置き換え先の文字と異なる場合はansから１減算
-3.置き換え文字(C)がAorBorCの時
置き換える前の状態で置き換え先を含む文字列がABCをなしておらず、かつ
Cを置き換えた場合の文字列がABCとななる場合はansに１加算
-4.M[x]をCに置き換えてansを出力
なんとなく冗長になっている気もしますがまぁACを頂けました。
https://atcoder.jp/contests/abc372/submissions/57973376
4.D - Buildings
コンテスト時は後ろから見ていくとよさそうだなくらいしか
回答方法がピンときませんでした。
解説でスタックを使うと見て、なるほどと、解き方が分かりました。
【考え方】
1.N、Aを読み込む
2.チェックしたビルから見えるビルのリストsを空で定義
sは後ろから格納し、格納時に見えなくなるビルは省く
3.チェックしたビルから見えたビル数のリストansを空で定義
後ろからチェックして格納するので、出力時は順番を入れ替える
4.for文でリストAを後ろから取り出し変数aに格納
-1.aのビルから見えるビル数はsの長さなので、sの長さをリストansに追加
～以下、aの1個後のビルから見た時のビルを整備する処理
-2.aの1個前から見た場合、aより低いビルは見えなくなるので、while文でリストsから
aより小さいビルをpopで除去
-3.sにaを追加
5.ループ後ansを後ろから表示
https://atcoder.jp/contests/abc372/submissions/58001762
5.E - K-th Largest Connected Components
コンテスト中はユニオンファインド木を使うんだろうなと思いつつ、簡易的に
ユニオンファインド木的な実装を軽量化しつつ行い
何とかなるかと思いましたが、TLEが30とダメダメでした。
コンテスト後5分解説を見ると、ベスト10だけ管理すればよいと
説明があり、目からうろこでした。
ABC370で使ったユニオンファインド木クラスを使い
根毎にベスト10を管理する事で、簡単に実装できました。
https://atcoder.jp/contests/abc372/submissions/57999722
以上