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 …