問題 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回のコンテストの順位の積で与えられる。高橋君よりもスコア…

問題 https://yukicoder.me/problems/no/741 10進数表示をしたときに桁が昇順に並んでいる数字を AscNumber とする。 10N 未満の AscNumber がいくつあるか求めよ。 考え方 [0, 9] の数字から重複を許して N 個選んだ時の数を昇順に並べると1つの AscNumber …

問題 題材は以下の問題です。 https://codeforces.com/contest/1047/problem/C 概要 ある数 を素因数分解をするとき、通常は までの素数で順に割ればよい。これは計算量 で求めることができる。 今回の場合は、配列 に含まれる のすべての数について素因数分…