yu/logs/*

技術メモ など

AtCoder ABC263 C 解説の深さ優先探索をデバッグ実行しながら理解した

ABC263にて、C問題が解けませんでした。

atcoder.jp

(↓無茶苦茶に実装しようとして結局実装しきれなかったもの)

atcoder.jp

上記ゴリ押し実装の修正も試みたものの、どんどん肥大化してバグを取り切れませんでした・・・

仮に次に同じ問題が出たときにもうまく対応できる気がしなかったため、解説を確認して解くことにしました。

いくつかある解説の中では、↓の深さ優先探索で解く方法が比較的実装量も少なく、自分の経験値的にも理解しやすかったのでこちらを選択しました。

atcoder.jp

ただ自分の力量だと単純に再帰しているだけに見えてしまい、上限値の処理をどこでしてるのかが分からなかったため、入力例2を対象としてデバッグ実行しながら追いかけて確認してみました。

再帰処理の確認結果

ループ範囲のfrom,toが逆転してループが廻らなくなることによって対象外の組み合わせが出力されなくなるのを確認しました。なるほど・・・

最終的にKotlinで書き直した↓の回答を提出。

atcoder.jp