0.はじめに
調子が悪いせいか、問題が難しいせいか最終的にA・Bだけしか解けませんでした。
C・Dは解説を読みながらTLEを解消するテクニックを学びなんとか解けました。
レートガタ落ちかなーと思ったらDDos攻撃があったようで
レーティング対象外になったようです・・・。
この記事書いてる時も503エラーとか出ていたので
攻撃とかつづいてるのかなー。。。
1.A - Job Interview
いろんな解き方あるだろうなと思いつつ、以下の実装。
最初はフラグに0をセット。
一文字目から見ていって
"o"かつ、フラグが0だったらフラグに１をセット
(2だった場合はより上位の不合格を上書きしないようにフラグをチェック)
"x"ならフラグに２をセット
最後まで見終わった後
フラグが１なら"Yes"を出力
それ以外なら"No"を出力して終了
https://atcoder.jp/contests/abc298/submissions/40638151
2.B - Coloring Matrix
B問題にしてはややこしいな・・・と思いつつ考察
・1：最初の位置、2：90度回転した位置、3：180度～、4：270度～の4つのフラグを用意し1をセット
・Aの表を順番に読んでいき、1が入っていた場合、
・1：A表の位置に対応するB表の値が0だったら、フラグ1に0をセット
・2：A表の90度回転した位置に対応するB表の値が0だったら、フラグ2に0をセット
・3：A表の180度回転した位置に対応するB表の値が0だったら、フラグ3に0をセット
・4：A表の270度回転した位置に対応するB表の値が0だったら、フラグ4に0をセット
・最後に4つのフラグのうちどれかが1だった場合Yes、そうでない場合Noを出力して終了
初めに答えた時、１～３までしかチェックしていなかったため
正解せず、悩んでしまいました。
https://atcoder.jp/contests/abc298/submissions/40664516
3.C - Cards Query Problem
最初、以下の考えで取り掛かりました。
当該箱に入っているカードを管理する集合群Bと
当該カード番号が入っている箱を管理する辞書C(キーをカード番号、値を箱番号の集合)を用意
クエリーが1の時は
箱B［i］にjのカード番号をセットと
カードC［i］にiの箱番号をセット
クエリーが2の時は
箱B［i］の内容をソートして表示
クエリーが3の時は
カードC［i］の値をsetに格納して
ソート＆重複削除して表示
と、単純に実装。
はじめ、重複削除にsetを使って行いましたが
TLEが出てしまい、工夫してもどうしても縮まらず
コンテスト時間が終了しました。
解説をみてもあまり自分の解答と違いがなく
他の方の解答を見たところ集合群C自体をset型にしていて
そのような実装にしたところ、TLEを回避できました。
先週覚えたsetの新たな使い方を学べました。
https://atcoder.jp/contests/abc298/submissions/40689070
4.D - Writing a Numeral
初めは、以下の考えで実装
初期処理
Qを入力
Sを文字列で定義し、"1"をセット
文字列の開始位置stに0をセット
メイン処理(Q回繰り返し)
クエリー内容を読み込み
クエリー番号が1の時
文字列Sの末尾に、xを付加
クエリー番号が2の時
stに1を加算
クエリー番号が3の時
文字列Sのst文字目以降をint型に変換し
998244353のmodを取り出力
どやっと実装しましたが、4/20TLEが出てしまいました。
以降、Sを数値にし、
クエリー番号1の時 SにS*10+xをセット
クエリー番号2の時 Sを10のlen(S)乗で割った余りをSにセット。
クエリー番号3の時 S％998244353を出力
としてみたらTLE増加。
コンテスト終了後解説を見てもやっぱりピント来ず
他の方の解答を見て以下の工夫を加えてACとなりました。
・クエリー番号１・２毎にmodo値を計算
・クエリー番号2で先頭を削る操作用にdequeを利用
【実装】
初期処理
Qを入力
出力用変数ansに1をセット
デキューdqを用意
dqに1を追加
変数MODに998244353をセット
メイン処理(Q回繰り返し) クエリー内容を読み込み
クエリー番号が1の時
ansにans10+xをセット
ansにans%MODをセット
dqにxを追加
クエリー番号が2の時
xにdq.popleft()をセット
ansから、xpow(10,len(dq),MOD)をマイナス
ansにans%MODをセット
クエリー番号が3の時
ansを出力
クエリー2の操作とansを常にmodを取ることで
小さ目の数値で推移するようにすることで
速さを実現しているのかなと思いました。
https://atcoder.jp/contests/abc298/submissions/40689991
以上