atcoder.jp 動的計画法で1枚目から順に数えていく 枚目のカードまで条件を満たしていたとき、 枚目のカードを加えたときに 条件を満たしたままかどうかは、枚目と 枚目のカードの表/裏の向きだけに依存します。 そこで、動的計画法のdp[flag][i] は、枚目の…
atcoder.jp N頂点の木の特徴 「木」は連結で閉路を持たない(無向)グラフです。 頂点の木は、本の辺を持ちます。 1本の辺は、両端の頂点の次数にカウントされるので、頂点の次数を合計した値は になります。 また、連結しているという条件から、次数 0 の頂点…
atcoder.jp 部分文字列 与えられた長さ の数列 の全ての連続部分列を対象としています。 部分文字列の最初の位置を 、最後の位置を とする部分文字列については、 , , を見て、異なる数であれば変更する必要があります。 つまり、次のようなコードで答えが求…
atcoder.jp 手順 i だけ考える 手順 i だけを考えると、手順を 回繰り返したときの変数 の値は、 になります。変数 の値にダブりがでるまでの手順 i の繰り返し回数を考えてみます。 と の最大公約数を として、 と表します。( は互いに素) は の倍数になり…
atcoder.jp 問題設定を整理 点 を中心として、点と対称な位置をとします。 すると、 より、 となります。この式から、 が偶数のとき は偶数、 が奇数のとき は奇数ということがわかります。 についても同じです。 そのため、スタート地点とゴール地点の座標…
atcoder.jp 二人の位置を一つの状態にしよう 高橋君が頂点 1 から頂点 N に移動し、青木君が頂点 N から頂点 1 に移動するまでのグラフの最短距離を求める問題ですが、 二人が同時に動き、かつ同色の頂点に移動できないという制約条件があります。そのため、…
atcoder.jp 動的計画法の基本問題 段目にのぼることが可能かどうかを配列 に記録していきます。 ロボットは上にしか進めないので、下の段から順に可能かどうかを確定してゆくことができます。「 段目に到達可能なら、 段目に到達可能」 または、 「 段目のい…
atcoder.jp 具体例で考える 入力例 2の 5915 は、次のように計算されます。 桁の数は、切れ目を入れられる部分が 個あり、それぞれについて切れ目を入れる/入れないの どちらかになるため、[2^{N-1}] 通りの掛け算の和を求めることになります。 は大きな数に…
atcoder.jp 欲しい商品だけを購入する場合 商品を購入するとき、定価＋追加金額 が必要になります。 定価はどのように商品を購入しても変わりませんが、追加金額 は商品の購入順序によって変わります。 そこで、まず追加金額が最小になる買い方を考えます。…
atcoder.jp 累積和の考えを利用する 連続する区間に、同じ数字を加える操作をします。これを繰り返すときは、累積和の考え方 （「競技プログラミングの鉄則」2.2 一次元の累積和(2) ）が利用できます。 前の数字との差を表す配列を用意すると、 番目から連続…
atcoder.jp 木の特徴 木＝連結で閉路を持たない(無向)グラフn 個の点からなる木は、 本の辺を持ちます。誘導部分グラフ＝グラフから一部の頂点を取り出し、その頂点間の辺の有無は元のグラフと全て同じグラフ木の誘導部分グラフは、閉路を持ちませんが、連結…
atcoder.jp LCP ( = Longest Common Prefix, 最長共通接頭辞) N 個の文字列が与えられます。その中の一つの文字列に選び、他の N-1個の文字列と比べます。その中で先頭から一致する文字数が最大になるケースを見つけることが求められています。先頭から一致…
atcoder.jp 2つの文字列が"マッチ"するか調べる 文字列 S の先頭 文字と 文字列 T の先頭 文字 が"マッチ"している。 文字列 S の末尾 文字と 文字列 T の末尾 文字 が"マッチ"している。 この2つの条件を満たしていれば "Yes" 、どちらか一方でも満たしてい…
atcoder.jp 動的計画法(DP)を考える 問題：N 種類の硬貨を組み合わせて、ちょうど X 円にできるか。これは、動的計画法(DP)を使うとよい問題です。（「競技プログラミングの鉄則」4.4 ナップザック問題 ） 「1,2,...,p の p 種類の硬貨で q 円 にできるかど…
atcoder.jp グラフの最短経路 問題：有向グラフの最短＋頂点の重みの和の最大経路を求めるグラフの最短経路を求める代表的なアルゴリズムには次の3つのアルゴリズムがあります。 ダイクストラ法 (特定の始点から全頂点, 辺の重みが負でない) ベルマン–フォー…
atcoder.jp どんな操作が行われるか具体例で考える ジャッジ側の操作を具体的に考えてみます。 を渡すとします。つまり、 です。 N=1 の場合、 と Aと同じ数字が返ってきます。 N=2 の場合、 より が返ってきます。 N=3 の場合、 より が返ってきます。 N=3 …
