0.はじめに
今回は、土日で旅行に行っていたのでバーチャル参加となりました。
ABは軽く、Cはちょっとてこずりながらも行けましたが、Cでブレーキ。
なんとなく解法は見えてきたところで時間切れとなりました。
レート変動はありませんが、点数時間ベースだと3800位程度の結果となりました。
1. A - Grandma's Footsteps
単純にX秒分ループを回すだけの簡単な作業。
Xが0になるまでのループを作成し
XがA+B以上なら、その周回ではA秒進めるので、SAを進む距離に加算
XからA+B秒マイナス
XがA+B未満かつ、A以上なら、SAを進む距離に加算
Xを0に置換
XがA未満なら、S*Xを進む距離に加算
Xを0に置換
という感じで進む距離を計算し、最後に出力して終了でACとなりました。
https://atcoder.jp/contests/abc428/submissions/70345655
2.B - Most Frequent Substrings
やり方は色々ありそうだけど、検討時間を短くするため
素直な実装。
【考え方】
1.Sの中にある文字列tを列挙
2.Sの中にtがそれぞれ何回出現するかをカウント
3.tの最頻出値の取得
4.最頻出tをリストに格納
5.リストをソートして出力して終了
https://atcoder.jp/contests/abc428/submissions/70345819
3.C - Brackets Stack Query
たまに出てくる括弧の組み合わせ問題。
足したり消したりするたびに判定をしているとTLEになるので
今までの統計をもとに、足したり消したりした場合の
良い括弧列を計算していく感じで実装しました。
【実装】
1.Qを読み込む
2.各カウント用変数を0で初期化：GL(ペアのある左括弧),GR(ペアのある右括弧),BL(ペアのない左括弧),BR(ペアのない右括弧)
3.デキューq（括弧とその括弧のペアの有無を格納し、削除対象となる括弧を取得）を定義
4.以下Q回繰り返し
-1.クエリを読み込み（リストAで読み込み、以下クエリ１の括弧はCに格納する前提）
-2.クエリ1の時
-1.Cが左カッコの時
-1.最後が左カッコの時は、よい文字列たりえないのでＢＬに1加算
-2.ｑにＣと0：ペアの無い括弧を格納
-2.Ｃが右括弧の時
-1.ＢＬが1以上の時（ペアができる）
-1.ＢＬから1減算し、ＧＬとＧＲに1ずつ加算
-2.ｑにＣと1：ペアのある括弧を格納
-2.ＢＬが0の時（ペアができない）
-1.ＢＲに1加算
-2.ｑにＣと0：ペアの無い括弧を格納
-3.ＢＬ+ＢＲが1以上（ペアの無い括弧があるとき）Ｎｏをそれ以外の時Ｙｅｓを出力
-3.クエリ2の時
-1.ｑからＣとｘ（取り出したＣがペアがあるかないか）を取り出す
-2.Ｃが左カッコの時（最後尾が左カッコの場合はペアはない）
-1.ＢＬから1減算
-2.ＢＬ+ＢＲが1以上（ペアの無い括弧があるとき）Ｎｏをそれ以外の時Ｙｅｓを出力
-3.Ｃが右カッコの時
-1.Ｘが0の時（取り外した括弧にペアが無かった時）
-1.ＢＲから1減算
-2.ＢＬ+ＢＲが1以上（ペアの無い括弧があるとき）Ｎｏをそれ以外の時Ｙｅｓを出力
-2.Ｘが1の時（取り外した括弧にペアがあった時）
-1.ＧＲ、ＧＬから1をマイナスし、ＢＬに1加算
-2.Ｎｏを出力（ペアがある括弧を取り外すのでかならず良い括弧列にならない）
試行錯誤したので、2回ほどＷＡを出してしまいましたが何とかＡＣをとれました。
https://atcoder.jp/contests/abc428/submissions/70346653
#4.D - 183184
とりあえず素直に1ずつ加算しながら平方数を数えたところ例題すらTLEでクリアできず。
ディスプレイしながら確認すると、f(x,y)の桁数毎に平方根が固まるので、そこら辺から
手を付けました。何とかACにはなりましたが、時間には間に合いませんでした。
【考え方】
1.f(x,y)のｙが取りうる値はＣ＋1～Ｃ＋Ｄ
2.Ｃ＋１の桁数をsS、C+Dの桁数をsEとすると
f(x,y)は、Cの桁数+sS～Cの桁数+sEの桁数を推移
3.f(x,y)の桁数毎の取りうる値は
①f(x,y)の桁数がCの桁数+sSの時
(1)f(x,y)はstr(C)+str(C+1)～(2)str(C)+str(9)sS
②f(x,y)の桁数がCの桁数+(sS+1)の時
(1)f(x,y)はstr(C)+str(10*(sS))～(2)str(C)+str(9)*(sS+1)
~略～
③f(x,y)の桁数がCの桁数+(sE)の時
(1)f(x,y)はstr(C)+str(10**(sE-1))～(2)str(C)+str(C+D)
4.上記各桁ごとの(1)、(2)の平方根を求めその差がその桁数に存在する
条件を満たす数となる
平方根を求める方法や、端値の調整をちょろちょろとしてACとなりました。
https://atcoder.jp/contests/abc428/submissions/70350414
以上