問題 https://beta.atcoder.jp/contests/agc028/tasks/agc028_b 考え方 難しすぎる。 通りの除く順番のうち、それぞれで が何回加算されるか？がわかれば嬉しい。 通りの順番は当然シミュレーションできないので以下を考えることがこの問題を解くうえでのポ…

問題 https://beta.atcoder.jp/contests/arc072/tasks/arc072_b 考え方 実験すると解が見えてくる。負けるマスを 、勝つマスを で表すことにする。ゲームの条件より明らかに である。 勝敗判定 マスからマスに移動するときに、少なくとも 1 つの負けるマスに…

問題 https://beta.atcoder.jp/contests/arc030/tasks/arc030_2 サイズ n の木と数列 {h_n} が与えられる。 h_i = 1 となる頂点 i には宝石がある。頂点 x からはじめてすべての宝石を回収するのに必要な辺のコストを求めよ。 考え方 x を根として考える。宝…

問題 https://beta.atcoder.jp/contests/abc113/tasks/abc113_d 制約 考え方 あみだくじについて上 から順番に組み合わせを決めていく。以下のようなDPを考える。 高さ で横から 番目にいるときのあみだくじの組み合わせの数 とする。あみだくじの横棒の線の…

問題 https://beta.atcoder.jp/contests/soundhound2018-summer-final-open/tasks/soundhound2018_summer_final_a 制約 考え方 の区間と の区間が交差するときの整数解の個数を求める問題。 つの区間が交差する区間は下図からもわかるように で求めることが…

問題 https://beta.atcoder.jp/contests/s8pc-4/tasks/s8pc_4_b N つの建物がある。それぞれ i 番目の建物は色 i で塗られており、高さは a_i である。左から見たときに K 色以上の建物が見えるようにしたい。 いくつかの建物の高さを増やすことによって K …

問題 https://beta.atcoder.jp/contests/cf16-exhibition-final-open/tasks/cf16_exhibition_final_a N つの座標 a_i と N つの座標 b_i がある。最短の長さで a_i と b_i をマッチングさせるとき、何通りの方法で最短の長さでマッチングすることができるか…

問題 https://beta.atcoder.jp/contests/cf16-exhibition-final-open/tasks/cf16_exhibition_final_c A, Bで Nim をする。Aが先手である。Bはゲームが始まる前に山に不正をすることができ、それはそれぞれの山から 0個または1 個の石を取り除くということで…

問題 https://beta.atcoder.jp/contests/arc029/tasks/arc029_2 縦 A センチ、横 B センチのノートが与えられる。また N 個の箱が与えられ、箱 i は縦 C_i, 横 D_i センチである。ノートを回転させて箱に入るかどうか求めよ。 考え方 座標の回転が必要かと思…

問題 https://beta.atcoder.jp/contests/arc047/tasks/arc047_b 座標平面上に つの格子点がある。これらの点はある点 とマンハッタン距離が同じである。 としてありうる点を求めよ。 考え方 座標平面上のある点からのマンハッタン距離が同じ点の軌跡は、座標…

問題 https://beta.atcoder.jp/contests/arc049/tasks/arc049_b N 点が与えられ、各座標は(x_i, y_i) である。また定数 c_i が与えられ、i 番目の点について、ある点(X, Y) に移動するためには c_i * max(|X-x_i|, |Y-y_i|)の時間がかかる。座標(X, Y)に集ま…

問題 https://beta.atcoder.jp/contests/agc028/tasks/agc028_c 頂点の重み付き有向グラフが与えられる。各頂点に つの整数が与えられており、 である。頂点 から頂点 への辺の重みは である。すべての頂点をちょうど 回通る有向サイクルの辺の重みの最小値…

問題 https://beta.atcoder.jp/contests/arc038/tasks/arc038_b 考え方 結果が決まる状態から逆算して考えていく。遷移できないマスは負けるマスである。逆に負けるマスに遷移できるマスは勝つマスである。 のマスの遷移を考えたときに、 から勝つマスに遷移…

問題 https://beta.atcoder.jp/contests/tenka1-2018/tasks/tenka1_2018_d 整数 が与えられます。 の部分集合の組 であって、以下の条件を満たすものが存在するか判定し、 存在する場合はひとつ構成してください。 のうちどの整数も、 のうちにちょうど つに…

問題 https://beta.atcoder.jp/contests/tenka1-2018/tasks/tenka1_2018_c 要素の数列 が与えられる。 を任意の順番に並べ替えて隣接項の差の合計を最大にするとき、最大値を求めよ。 考え方 隣接項の差をなるべく大きくするには以下のように数列を並べ替え…

実現したいこと ある条件下の最大の index を二分探索で取得 ある数以下 upperBound で実現できる。 public void solve(int testNumber, InputReader in, PrintWriter out) { int[] a = {18, 37, 75, 80, 80, 93, 107, 144, 163, 196}; int num = 40; int id…

問題 https://beta.atcoder.jp/contests/colopl2018-qual/tasks/colopl2018_qual_d 考え方 dpを考えるのは自然である。 dp[i][k] := 個までの時刻のうち、 回起動しているときの知力の最大値 とする。ナイーブなDP遷移を考えると dp[i][k] = (0 <= j < i) ma…

問題 https://beta.atcoder.jp/contests/qupc2018/tasks/qupc2018_e 個の要素をもつ数列 が与えられる。たぴさを数列の連続する部分列のうち、総和が である個数とする。数列のある つの要素を任意の数に変更できるとき、たぴさの最小値を求めよ。 制約 考え…

問題 ある数 と つの組 が与えられる。 つの組からいくつか を選び、価値の総和を とする。選んだそれぞれの の or が を超えないようにするとき、価値の最大値を求めよ。 考え方 満たすべき条件について考える。条件は「選んだ の or が 以下にならなければ…

問の問題があり、それぞれ難易度は である。以下の条件を満たすように 問選ぶときの選び方の数を求めよ。 問目の難易度は 問目の難易度の 倍以上である。 問目の難易度は 問目の難易度の 倍以上である。 問目の難易度は 問目の難易度の 倍以上である。 考え…

解いた問題を振り返ります。 A.Make a triangle! 問題概要 Problem - A - Codeforces 3 辺 a, b, c が与えられる。a, b, c の各辺にいくつか数を足して三角形になるようにするとき、足す数の最小値はいくつか？ 制約 1 <= a, b, c <= 100 考え方 三角形の成…

問題 https://beta.atcoder.jp/contests/agc013/tasks/agc013_b N 頂点 M 辺の単純無向連結グラフが与えられる。以下の条件を満たすパスを構築してください。 2 個以上の頂点を通る 同じ頂点を 2 度通らない パスの少なくとも一方の端点と直接辺で結ばれてい…

問題 https://beta.atcoder.jp/contests/arc102/tasks/arc102_c K 面サイコロを N 回振る。サイコロは区別しない。各 i (2, 3, ..., 2K) について以下の条件を満たす場合の数を求めよ。 どの異なる2つのサイコロの出目の和も i にならない 制約 1 <= K <= 20…

問題 https://beta.atcoder.jp/contests/agc019/tasks/agc019_b 文字列 が与えられる。i <= i <= j <= n なる i, j を選んで部分文字列 a_i...a_j を反転させるという操作をするとき、操作によって何通りの文字列を得ることができるか。 考え方 求めるものは…

問題 https://beta.atcoder.jp/contests/agc023/tasks/agc023_c 個のマスがあり白く塗られている。ある操作で を黒く塗ることができる。順列 によってすべてのマスを黒く塗るとき、はじめてすべてのマスが黒く塗られるまでの回数 が何通りあるかそれぞれ求め…

問題 https://beta.atcoder.jp/contests/agc009/tasks/agc009_b 考え方 木DPだが、遷移が重要。今ある親 u から 4 個の子 (v_1, v_2, v_3, v_4)をもつ部分木の場合を考える。ある頂点の深さを cost[p] としておく。 このとき、トーナメントの割当としては以…

問題 D - ネタだけ食べたい寿司 つの寿司と 個の皿がある。シャリのみを食べる時、皿を消費する。シャリのみを食べるのは 回実施することができるが、 回実施したタイミングでその後は寿司を食べることができない。幸福度の最大値を求めよ。 考え方 個までの…

問題 https://beta.atcoder.jp/contests/agc016/tasks/agc016_b N 匹の猫がいる。猫 i は「自分の除く猫がかぶっている帽子の色の種類数は a_i である」といっている。すべての猫の発言に矛盾しないように帽子を割り当てることができるか判定せよ。 考え方 …

問題 https://beta.atcoder.jp/contests/agc003/tasks/agc003_c 長さ N の数列 a_N が与えられる。以下の操作をして、数列を単調増加にするよう並べ替える時、操作 1 の最小回数を求めよ。 数列の連続する 2 つの要素を選び、その 2 つの順番を反転する。 数…

問題 https://beta.atcoder.jp/contests/abc093/tasks/arc094_b [1, 10^(10^10)] の参加者がいるプログラミングコンテストがある。高橋君は1回目で A 、2回目で B 位になった。参加者のスコアは 2回のコンテストの順位の積で与えられる。高橋君よりもスコア…