0.はじめに
1年3か月の休暇最後のコンテスト。
C問題までは順調に進むもDでてこずりました。
とはいえなんとか時間以内に回答でき、4問正解で終了。
レートは+9の795と先週の枚なうが取り戻せました。
1. A - 455
455にちなんだ問題。
A,B,Cを読み込み、AとBが異なり、BとCが同じなら
Yesを出力、そうでなければNoを出力して終了としてACでした。
https://atcoder.jp/contests/abc455/submissions/75228467
2.B - Spiral Galaxy
Aから急に難易度アップ。
とはいえB問題であり、Nが10までなので素直に実装。
問題文通りに、h1、h2、w1、w2の範囲を定義し
その中で、iとjの全組み合わせについて、
S[i][j]とS[h1+h2-i][w1+w2-j]が一致するかをチェック
全て一致する組み合わせの場合は回答用変数ansに1を加算し
最後にansを出力して終了としてACとなりました。
https://atcoder.jp/contests/abc455/submissions/75235347
3.C - Vanish
pythonのカウンター関数を使えば楽な問題。
【考え方】
1.リストAについてカウンター関数により数字とその個数を求める
2.数字掛ける個数をリストLに格納
3.リストLを降順ソート
4.リストLのK+1番目以降の値を集約して出力
Cにしてはあっさりと回答できました。
https://atcoder.jp/contests/abc455/submissions/75244505
4.D - Card Pile Query
問題の内容はわかりやすいけど、解き方が難しい良い問題。
【考え方】
・一回でも移動した数字の山は、最終的にカード数０枚
→リストMでカードが動かされたかを管理
・各カードの上に載っているカードを管理しリストMでカードが残っている
山のカードに乗っているカードを数えれば答えることができる
→辞書Uで対象カードに乗っているカードを管理
・途中の移動で、上に載っているカードがなくなることがあるので
移動対象カードの下にあるカードを把握しておく必要がある
→辞書Dで対象カードの下にあるカードを管理
移動クエリーで箱の辞書を参照し辞書Uの関係を削除する
【実装】
1.N、Qをよみこむ
2.デフォルト辞書U（キー：対象カード、値：対象カードの上にあるカード）
D（キー：対象カード、値：対象カードの下にあるカード）を値intで定義
3.リストM（カードが移動されたかを管理）を値１掛けるN+1で初期化
4.以下Q回繰り返し
-1.C,Pを読み込む
-2.Cが辞書Dにある場合(既にどこかのカードの上に移動されていた場合)
辞書UからD[C]を辞書DからCを削除(前回移動時の連結情報をクリア)
-3.辞書UにキーP値Cを登録
-4.辞書DにキーC値Pを登録
-5.リストMのCを0に変更
5.回答用リストansを空で定義
6.以下iを１～Nまで繰り返し
-1.M[i]が0以外の時
-1.変数now(山iに乗っているカードの枚数)に1をセット
-2.変数x(今見ているカード番号)にiをセット
-3.xが辞書Uにある限り、xにU[x]をセットし、nowに1加算
-4.ansにnowを追加
-2.M[i]が0の時、ansに0を追加
7.ansを出力して終了
解き方のイメージはすぐできたのですが、UとDの関係が頭の中で
整理できず時間がかかってしまいました。
https://atcoder.jp/contests/abc455/submissions/75270613
以上