0.はじめに
先週はコロナに倒れ参加できませんでした。
まだ本調子ではありませんが、何とか参戦。
Ａ～Ｃの難易度はそれほどでもなく
Ｄもちょっとした工夫でＡＣとなり、4問クリア。
レートも+21の758。このペースで行けば再入緑も
見えてきました。
1.A - Lucky Direction
4つの方角を変換する辞書を用意し
入力文字をその辞書に従い変換して出力しました。
https://atcoder.jp/contests/abc391/submissions/62260259
2.B - Seek Grid
Bにしてはやや複雑な問題。
とはいえ、パターンとしてはよくあるし、SにTが含まれることも
保証されているので素直に実装。
Sの左上から、始点をずらしていき、始点ごとに
Tと一致するかをチェックする形で実装しました。
https://atcoder.jp/contests/abc391/submissions/62269993
3.C - Pigeonhole Query
素直に実装すると、TLEになりそうな問題。
複数の鳩がいる巣は列挙ではなく、数だけ分かればよいので
出力用の変数を用意し、クエリーごとの処理で
巣の数の増減を巣の状態と別に管理することで高速化を実現しました。
【実装】
1.以下変数を用意
・変数ans ：複数の鳩がいる巣の数。クエリ２の時個の数を表示
・辞書Ｄ ：巣ごとの鳩の数、KEYに巣の番号(初期値は１～N)、値にその巣にいる鳩の数(初期値は１)
・辞書Ｐ ：鳩毎のいる巣の位置：ＫＥＹに鳩の番号(初期値は１～N)、値にその鳩がいる巣の番号(初期値は１～N)
2.クエリ1の時に以下の処理（入力は変数p(移動する鳩番号)、変数d(移動先の巣の番号)）
-1.変数pd（鳩がもとにいた巣）にP[p]をセット
-2.P[p]にdをセット（鳩を移動）
-3.D[pd]が2の時(鳩の出ていく事に伴い、鳩が元居た巣の鳩の数が複数出なくなる時)、ansから1減算
-4.D[pd]から1減算
-5.D[d]が1の時（鳩が入ってきた事に伴い、鳩の移動先の巣が複数いる巣になるとき）、ansに1加算
-6.D[d]に1加算
3.クエリが2の時ansを出力
https://atcoder.jp/contests/abc391/submissions/62278858
4.D - Gravity
こちらも、素直な実装だと、TLEとかMLEになりそうな問題。
色々複雑な印象を受けましたが、以下が分かればあとは、クエリ毎に
Ｔ秒時点でブロックＡが消えているかを判定すればよいことが分かりました。
Ａ．対象ブロックが消されるか
Ｂ．対象ブロックが（消されるとしたら）いつ消されるか
（ＡとＢをまとめて、対象ブロックがいつ消されるか、消されない場合いつが無限大になる
としてもよかったのですが、実装の都合上分けました）
【考え方】
１.Ａ（対象ブロックが消されるか）の求め方
-1.全体で何列削除されるかを求める
-各列毎のブロック数をカウントする
-カウントの最小値が消される列数となる（例題1の場合、2、2，1となるので1列消される）
-2.対象ブロックが列内の下から何番目かを求める（読み込み時に保持しておく）
-3.対象ブロックが下からｘ番目で、全体でｙ列削除される場合、ｘ＜＝ｙの時、対象ブロックは削除される
2.Ｂ（対象ブロックがいつ消されるか）の求め方
-1.消される列が何秒時点で消されるかを求める
-ブロックの列数毎の初期位置ｙのうち、一番大きい値を保持しておく（例題１の1列目の場合、1，2，2となるので2）
-上記値が対象列が消される秒数となる
-2.対象ブロックが列内の下から何番目かを求める（読み込み時に保持しておく）
-3.対象ブロックが下からｘ番目で、ｘ列目が削除されるタイミング＝対象ブロックが削除されるタイミング
3.クエリ毎の判断
・クエリ秒数時点で、ブロックＡが消されていればＮｏ、消されていなければＹｅｓとなる。
https://atcoder.jp/contests/abc391/submissions/62297645
以上