7K12 blog

猫でも分かるアルゴリズム解説

グラフ

ABC025C - 双子と○×ゲーム

ゲーム系の最善手は逆算 木のDFSだが「間違えて元の局面に戻る」ようなDFSが絶対に発生しないので根への遷移かどうかのチェックは不要 問題文を誤読しないよう注意、直大さんのスコアは「マス[i][j] = o かつ マス[i][j] = マス[i+1][j]」でなく単純に「マス…

SoundHound Inc. Programming Contest 2018 D - Saving Snuuk

選択肢の少ない状態から考察すると楽 後ろから考えると値を流用できる https://atcoder.jp/contests/soundhound2018-summer-qual/submissions/25168114 0日目から考えると全ての都市で両替できるので最善を考えるのが大変だが n-1 日目なら選択肢は1通りしか…

ABC132 E - Hopscotch Addict

頂点を増やすことでmodの遷移を判定する https://atcoder.jp/contests/abc132/submissions/24017041 愚直な考察をすると頂点に移動回数のmod情報を持たせたくなるが、実装が複雑で難しいので逆転の発想をする。具体的には頂点を増やすことで、modの情報を持…

ZONE2021 E - 潜入

https://atcoder.jp/contests/zone2021/submissions/23283470 辺の張り方とコストが特殊なとき、辺の数を減らして同値な移動を再現可能 コストを増やしたい→階層化して辺を追加すれば再現可能 上下左右1マス移動しかないなら単純にダイクストラ法をするだけ…