問題ページ C - Coins 考えたこと dp[i番目まで][金をもらった人数][銀をもらった人数][銅をもらった人数] みたいな愚直DP 金をもらった人数 + 銀をもらった人数 + 銅をもらった人数 = i なので銅をもらった人数は状態に持たなくても良さそう だからといって…

問題ページ Aizu Online Judge Arena 解法 s-t間の最短経路に使われない辺をいくら伸ばしたところで最短経路は伸びない。したがって最短経路に使われる辺だけを抜き出したグラフを考えればよい。辺を抜き出す部分の判定は dist[i][j] = (iからjの最短経路) …

問題ページ Aizu Online Judge Arena 解法 部分木についてのクエリなのでオイラーツアーをしたくなる。オイラーツアーをした列に対して遅延セグ木を使って更新するいつものをしたい。updateが区間xor、queryが区間和の遅延セグ木を使えばその木にGとWのどち…

問題ページ Aizu Online Judge Arena 解法 dp[i][j] = (i番目までで今までに使った最大の素数がj) みたいなDPを書きたくなる。しかしこれでは状態数がO(N*(max(q)以下の素数の数))となり間に合わない。ここで連続した2数が指数の方になることはありえないこ…

問題ページ Aizu Online Judge Arena 解法 やること自体は簡単で与えられた二次元グリッド上でつながっている頂点同士をつないだグラフをつくり、あとはdijkstraなりワーシャルフロイドを貼るだけ。ただし実装が非常にバグらせやすいので要注意。 以下に示し…

問題ページ Aizu Online Judge Arena 解法 答えが1以下になるようならば式を一つも評価せずに1とするのが答えが最大でなおかつ最も短い部分列となるので最善となる。つまり、a[i]=0を使う意味はない。またa[i]=1を使ったとしても値が変わらずに部分列の長さ…