ABC参加記 298
結果
A~Eまでの5完でした。
Fはコンテスト後に解説見て解答しましたが、ここまで解きたかったな。
A - Job Interview
bool f1 = false, f2 = trueで初期化する。
Sに順にアクセスしその文字が'o'ならf1=true, 'x'ならf2=falseにする。
最終的にf1 && f2で結果が判定できる。
↓提出
B - Coloring Matrix
コンテスト中は正誤条件をすべての値が等しいと勘違いしていたため、無駄に時間を食ってしまった。
問題文はよく読もう!
↓提出
C - Cards Query Problem
- 番号iが入ってる箱をvector<set<int>> sで管理
- 箱jに入ってるカードをvector<multiset<int>> boxsで管理
クエリ1
s[i]にjをinsert、boxs[j]にiを追加する
クエリ2
boxs[i]内のデータをすべて出力
クエリ3
s[i]内のデータをすべて出力
D - Writing a Numeral
現在のSの文字列はqueueで管理する。
現在のSの値(つまりクエリ3で答える値)をvalueとする。
(MOD = 998244353)
クエリ1
value = (value * 10 + x) % MOD
queueにxを追加
クエリ2
先頭を削除するということは,現在の値から
よって、
a = queue.pop(), d = queue.size()
value = (value-a*pow(10,d))%MOD
クエリ3
valueをそのまま表示
クエリ2で10の累乗を計算する際は，各累乗を前計算しておくか高速指数計算用いる必要があるため注意。
↓提出
E - Unfair Sugoroku
定義：dp[i][j] := 高橋君がマスi,青木君がマスjにいるときの高橋君の勝率
遷移：dp[i][j] =
初期化：dp[N][i] = 1, dp[i][N] = 0, dp[N][N] = 1 ( 0 <= i <= N )
上記のようにdpを定義できるため、i,jを降順に埋めていけば求める解dp[a][b]が得られる。
PQの逆元はフェルマーの小定理などで事前に計算しておく。
解説にある累積和使えば早いのはその通りであり、コンテスト時はそれは考えていなかったためちょっと反省。
↓提出
F - Rook Score
列、行ごとに合計を分けて考え、各列ごとの最適な行を求められればよいのではないかというとこまでは考えられた。また、行を入れ替えても解に影響はないため、総和の降順に行をソートすることも思いついた。
(score(C) := 列Cの総和, score(R) := 行Rの総和)
であるため、行を降順にアクセスすることでx(R,C)=0であればそれ以降の行を検査する必要がないことに思い至らなかった。( score(R) > score(R')であり、x(R,C) >= 0 ) であるため) 各列で追加で確認する際はx(R,C)!=0である必要があるため、追加の確認数の総和はNとなる。よってO(N)で全列の最適値を探索できる。
↓提出
Discussion