自力で解けたの1問しかない。
再帰関数って理解できるの天才だけでは、という気分になった。
https://not-522.appspot.com/contest/5153769102770176
A: jumping!!
https://atcoder.jp/contests/tkppc4-2/submissions/10063040
やるだけだけど、細かい条件に気づけず2WAした。
B: stalker
https://atcoder.jp/contests/tkppc4-2/submissions/10077919
24時間以内に理解できず30時間ほど費やした。
簡単に言うと再帰関数でDFSすれば解ける。再帰関数の教育的問題と言える。
- DFS関数の最初にローカル変数を宣言すると頂点v以下の部分木の値を保持できる
- 自身の頂点vの処理は辺の遷移の後ろに書く
- 全ての子の部分木情報を得るには辺の遷移処理の後に処理を書いてRun()を戻り値で返す
- diff4桁から自身の頂点vと子の部分木を両方使って処理する問題が生える
上記を意識して暗記すると良いかもしれないと思った。実際に処理を書くときはCのうち1つをスタート地点として選ぶと分かりやすくなる気がする。基本的には2つの分岐先に写真があったらNGで良い。
ただし、注意点としてスタート地点(赤)の処理だけは2つの分岐先に緑頂点があってもパスは1つになる。スタート地点だけNG条件が3つの分岐になる。よって、引数を1つ増やしてスタート頂点も渡して特殊ケースとして処理する。これに気づけない場合は諦めるしかない。なお、自分は初見で気づくのに30時間かかった。才能なくて萎える。
2問で力尽きて3問目以降やってない。というより物理的に時間がないので不可能。
