京セラプログラミングコンテスト2022(AtCoder Beginner Contest 271)
まとめ
A,B,C,D,E,F の6完で大満足の結果!
6完は2回目で、前回は ABC244 でした。ほぼ半年ぶり!
結構くだらないミスを数回やっちゃっているのでそこは反省ポイントです。
でも序盤にこういうミスをすると後半思い切って動けるみたいな気持ちもある。
A - 484558
10 -> 16進数 の変換は大体の言語にはライブラリがあるはず。
D言語の場合は writefln("%02X", A) です。
B - Maintain Multiple Sequences
入力がやや複雑なので、頑張って受け取りましょう。
受け取れたらその時点でほぼゴールです。
C - Manga
結構難しい問題。ARCのA問題とかに出題されそうなやつです。
ソートしておいて、巻数の小さいやつから舐めていきます。欲しいやつがあるなら良し、不要なやつ(重複)があるなら売却用のストックにしておきます。
欲しい巻がなくなったら、売却用のストックを使います。ストックがない場合、巻数の大きいやつも使います。
手が滑ってA問題のコードを提出してしまいWA。
D - Flip and Adjust
カードごとにmapを使うタイプのDPで解きました。
総和をキー、表か裏かを値にしてメモ化します。表か裏かはどっちでも良い場合もあるので、そういうときは表優先とか雑に扱っても困りません。
表か裏かのフラグ逆転させてしまってるのに気づかずWA。
E - Subsequence Path
「良い経路」を示す数列により順番が制限されるので、それをどう扱うかが難しいと思いました。
解法としては、ダイクストラ法を応用したような実装になりました。
E を頭から1辺だけグラフに追加してダイクストラをやり、終わったらその辺を削除する、を繰り返しました。
解けてるか不安だったのですが、サンプルの答えは一致しました。提出でAC。
F - XOR on Grid Path
Nが小さいのでDPで素直に実装しても間に合いそうな気がしましたが、無理な気がして少し考えました。
左上、右下と対角線で2つの三角形に分けて、合流点で XOR の結果が 0 であることを見ると効率良さそうに感じました。
これは公式解説と一致していて想定解だったようです。
実装しながら半分全列挙っぽいな〜という印象を覚えていました。
答えのオーバーフローで2WAだしてしまった。