ABC-303 振り返り
日鉄ソリューションズプログラミングコンテスト2023（AtCoder Beginner Contest 303）
問題ページ: https://atcoder.jp/contests/abc303/tasks 解説動画: https://www.youtube.com/watch?v=_toS2Czj1to
当面の目標
水色
全体の振り返り
D問題まで、そんなに悩むことはなかったが実装時間が足りていなかった。 E問題以降はまともな時間内で解ける感じがしなかったので解法の勉強が必要。
時間はD問題完了時点で90分。 重複不可集合(set)の使い方とか調べ方読みながらやっていたので、このあたりに慣れたら早くなりそう。 あと実装中にprintデバッグするのが効率悪いので、デバッガで実行できるようにしておいたほうが良い。
各問題振り返り
A問題
10分。
特に悩む点はなかった。
dictで文字の対応マップを作って判定していたが、解答例では文字列をそのままreplaceしていた。
確かのそちらのほうが実装早そう。
B問題
24分。
発生していない組み合わせを探す問題。
問題文の理解と、itertools.combinationやsetの使い方を調べながら実装するのに時間がかかってしまった。
discardで削除。
解答例は全ての(x,y)の組を取り上げて、文字列中に出てくるかをスキャン。 下手に言語の機能使うよりこっちのほうが実装早かったかも。
C問題
26分。
移動させながらHPを回復させて移動完了できるか判定の問題。
実装方法について迷いはなかったが、アイテムが使用済みかの管理をSetでやるかdictでやるかを迷ってコーディングが少しウロウロした。
hpのリセット処理に関して、利用する変数が間違っているポカミスに気が付かずにタイムロス。
D問題
30分。
aとAからなる文字列を最速でタイピングする時間計算の問題。
capsの状態を分けた1つのリストでDPすれば良さそうだなというのはすぐに検討がついた。
ゆっくりやったのもあったがちょっと時間かかりすぎている。
状態遷移時の操作が6通りぐらい出てしまってややこしかったが、解答例や解説動画ではそんなにパターン多くない。
caps → a → caps の操作は考慮しなくても大丈夫っぽいのだがなぜだろう。
値が入力されるiに関して、その情報源になるi-1をループして最小値を持ってきていたが、
解答例では情報源側をiにして、次ステップのi+1に対して書き込んでいた。
この解答の書き方だとi+1の値を更新する際にmin処理で値を残すようにできるので、ちょっとだけ実装がシンプルになるかも。
iの対象をどっちにするか切り替えるのは別の問題でも役に立つことありそう。
E問題
10分、解ききれず。
スターグラフが連結してツリーになったものから、元のスターグラフ形状を算出する問題。
問題文読むのに時間かかってしまった。一番上の単語定義の文章をしっかりと読み込んでおくべきだった。
頂点数が多いノードを探せば行けるかな? → k=2の場合がめんどくさそうだな、からの、
次数が1のノードから順に消し込んでいく処理をすれば行けそうだなーと考えたところで終了。
解答的には、上記の方法でも行けるが、DFSないしBFSしてmod 3 = 1のものを取り出すのが楽、と。
復習で実装。 隣接表現リストでの実装はやりやすかった。 DFSは再帰関数で親のノード名だけ渡しておけば、2重にたどる処理を弾けるから実装が楽だな。
