数え上げ
問題 https://beta.atcoder.jp/contests/arc102/tasks/arc102_c K 面サイコロを N 回振る。サイコロは区別しない。各 i (2, 3, ..., 2K) について以下の条件を満たす場合の数を求めよ。 どの異なる2つのサイコロの出目の和も i にならない 制約 1 <= K <= 20…
問題 正整数 が与えられる。 となる a の数列が何通りあるか求めよ。 考え方 例として とする。 まずは を素因数分解をする。それぞれの因数ごとに独立して考えることができる。因数ごとのべき乗の数がポイントである。 を x x x x のような つのマスに配る…
問題 https://beta.atcoder.jp/contests/abc003/tasks/abc003_4 制約 1 <= R, C <= 30 1 <= X <= R, 1 <= Y <= C 0 <= D, L, 1 <= D, L <= X * Y 考え方 包除原理である。まず、R * C から X * Y の長方形のとり方を求める。次に X * Y の長方形に D + L 個…
問題 https://beta.atcoder.jp/contests/abc104/tasks/abc104_d 長さ の文字列 が与えられる。 のうち つ文字を選んだときに左から となっている組み合わせの数を求めよ。 制約 考え方 場合の数である。文字を つ選ぶときに真ん中の を固定して数え上げるこ…
問題 https://beta.atcoder.jp/contests/arc044/tasks/arc044_b N 頂点のグラフが与えられる。頂点 1 から頂点 i への最短路を a_i とするように辺を張るとき、辺の張り方は何通りか求めよ。 考え方 自明なケースを除く。まず 1 から 1 への最短路は 0 であ…
問題 https://beta.atcoder.jp/contests/abc041/tasks/abc041_d N 頂点上のグラフに、M本の有向辺が与えられる。M本の有向辺の条件を満たし、N 個の頂点を左から右へ横一列に並べる並べ方は何通りか。 制約 2 <= N <= 16 1 <= M <= N(N-1)/2 考え方 トポロジ…
問題 https://beta.atcoder.jp/contests/agc005/tasks/agc005_b N個の数 {1, 2, 3, ..., n} の任意の順列 a_n が与えられる。 を求めよ。 考え方 ナイーブにシミュレーションするとO(N2)となり間に合わない。 N2 つの区間の最小値を求めて和を求めるのではな…
問題 https://beta.atcoder.jp/contests/arc091/tasks/arc091_b 1 <= a, b <= n である a, b が与えられる。a % b >= k である個数を求めよ。 制約 1 <= n <= 105 1 <= k <= n-1 入力値は整数 考え方 a_n = {1, 2, 3, ..., n}, b_n = {1, 2, 3, ..., n} の2…
A.YahooYahooYahoo(400) 問題 方針 雑記 A.YahooYahooYahoo(400) 問題 文字列 S が与えられる。yahooの文字列を0個以上繰り返してできる文字列との編集距離を求めよ。 1 <= |S| <= 105 方針 ポイントは大きく2つ。他は普通の編集距離DPと変わらない(遷移に…
問題 https://beta.atcoder.jp/contests/arc092/tasks/arc092_b [0<= i <= n-1], [0<= j <= n-1] の i, j について a_i + b_j のそれぞれの xor をとった結果を求めよ。 方針 「桁ごとに独立して考えること」がポイントである。xor演算は繰り上がりがないの…