0.はじめに
気合を入れて土曜日に待ち構えていたら日曜開催で
肩透かしを食らった今日この頃
今回なんとかC問題は解け、D、Eも行けそうな気がして
チャレンジしましたが失敗。
レートは-8の694とついに600点台まで落ちていきました・・・。
最近解答力が落ちすぎなので、今回は試験後
DとEも解説を見ながら自分で解いてみました。
1. A - What month is it?
素直にXとYを足した値Zが12より大きければ
Z-12をそうでなければZを出力して終了でACでした。
https://atcoder.jp/contests/abc420/submissions/68734509
2.B - Most Minority
B問題にたまにあるプログラミング的には簡単だけど
内容がややこしい問題。（あくまで個人の感想）
一旦Sをすべて読み込んでから投票ごとの得点者を
加算していき最後に最高得点者を判別して出力して終了でACでした。
https://atcoder.jp/contests/abc420/submissions/68747865
3.C - Sum of Min Query
制約から、単純に更新毎に出力する値を計算していると
間に合わなくなるので以下のような工夫。
【考え方】
・AとBの小さい方を保持するリストCとその合計SCを用意
・クエリ毎にCの値の更新を判断し、更新された場合はSCも更新し出力
上記考え方ですんなりACとなりました。
https://atcoder.jp/contests/abc420/submissions/68759312
4.D - Toggle Maze
コンテスト中はスイッチでの切替ごとに条件が変わる部分を
どのように通過済とするかに悩んでいるうちに時間切れ。
解説を見てスイッチon/off毎の通過フラグを持てばよいことが分かり
その手があったかと感心しました。
が、その内容で実装してもTLEが消えず解答例を参照し
移動回数を関数に引き渡す→移動回数は別表で保持
移動後に移動回数を加算→移動前に加算
移動判断を関数化→while処理内に含める
等々工夫を重ね、何とかACとなりました。
https://atcoder.jp/contests/abc420/submissions/68796196
#5.E - Reachability Query
こちらはコンテスト中は手が回らず、後からみて解きました。
とはいえ、解説を見ないと考え方もピンときませんでした。
過去問で使用したユニオンファインド木の関数を用意し
・unite（枝の結合）関数に以下機能を追加
・ルート毎の黒石数を合計する
あとは、クエリ毎に
タイプ１の時は枝の結合
タイプ2の時は頂点の色変化を行い
黒→白の時はルート毎の黒石数を減少
白→黒の時はルート毎の黒石数を増加
タイプ3の時は対象頂点のルートに
黒石が含まれればYes、含まれなければNoを出力して終了
といった感じでACとなりました。
https://atcoder.jp/contests/abc420/submissions/68798816
以上