ABC290E Warshall-Floyd. \(O(N^{3})\) が間に合う．(最短距離，お土産の最大化) の優先順位で同時に処理する． つまり，辞書順を用いればよく，pair を使えばよい． 最大化の方は，マイナスをつければ最小化に帰着できる．実装パスの頂点すべてでお土産を買…

ABC287E LCPに関する問題．先頭から貪欲に考えるのが基本．Binary Trie に近い．とりあえず，\(n\) 個は多いので 2つで考える． 2つの文字列 \(s,t \) の LCP は，先頭から貪欲に調べれば求まる．次に複数の文字列を同時に判定することを考える． これは tre…

ABC284E Simple path の個数DFS で求まる．今の頂点 \(cu\) からの遷移が終わった後に， \(vis[cu] = false\) に戻す． 別の path で同じ頂点 \(cu\) に来た場合，区別して数えるから．実装戻り値に答えを入れた． つまり，戻り値に対して \(chmin(cnt, 1e6)…

ABC285E 素直に dp を考えると，\(dp_{i,j} := \) \([0,i)\) まで見て，最後の休日が \(j\) 日目 のときの min. しかし，これは失敗する． なぜなら，生産性は，今決めている日だけでなく，先の日の割り当て次第で 今日の近傍の生産性が変わってしまうから．…

ABC288E Key:買うときの値段を決めているのは何か．買う順序によって値段は変わる． しかし，よく見ると，今買うか決めようとしている商品の値段は， 既に何個買ったか だけに依存している． 買う順序や，どれを買ったかの集合には依存しない． 実装:あまり…