問題 https://www.ioi-jp.org/joi/2008/2009-yo-prob_and_sol/2009-yo-t4/2009-yo-t4.html 制約 考え方 始点を全探索する。始点から再帰的に進めるだけ進み、進んだ数の最大値で解を更新すれば良い。 どこに着目して考察するべきだったか 考え方の通り 何が…

問題 https://beta.atcoder.jp/contests/dwacon5th-prelims/tasks/dwacon5th_prelims_c 制約 考え方 k-DMC数の数え上げは「We Love ABC」に似た要領でDPで求めることができる。また数え上げの対象になるのは の連続区間に含まれる k-DMC数である。よってこれ…

問題 https://beta.atcoder.jp/contests/dwacon5th-prelims/tasks/dwacon5th_prelims_b 制約 考え方 まず部分列のすべての和を で求めておく。bitの最大値は最上位ビットから貪欲に決めていけば良い。 ビット目について つ以上の数が存在するとき、 ビット目…

問題 https://codeforces.com/contest/1080/problem/C 市松模様の 行 列の表が与えられる。 で囲まれる長方形を中をまずすべて白で塗りつぶす。その後 で囲まれる長方形の中を黒で塗りつぶす。白マスと黒マスの数を求めよ。 制約 考え方 の表に含まれる黒と…

問題 https://beta.atcoder.jp/contests/ddcc2019-qual/tasks/ddcc2018_qual_c 考え方 条件を整理すると、以下を満たすような数え上げである。 の最大値を の最大値を とすると である。 を全探索し とするとき は と一意に定まる。また で となるような組み…

問題 https://beta.atcoder.jp/contests/dwacon2018-prelims/tasks/dwacon2018_prelims_c 制約 考え方 の要素数 に を割り当てていくことになるが、 の値が同じ場合は、 数が昇順になるようにいけない条件が面倒である。 なお分割数は既知とし、数 を つに分…

A. Minimizing the String 問題概要 Problem - A - Codeforces 長さ の文字列 s が与えられる。1文字削除して辞書順最小の s' を出力せよ。 制約 考え方 辞書順最小の文字列を求めるには、前から順番に辞書順最小の文字列で構成していくことになります。よっ…

解いた問題を振り返ります。 A.Frog Jumping 問題概要 Problem - A - Codeforces 以下の操作を k 回実施したときの値を求めよ。 それまで実施した回数の操作が偶数回の場合 現在の値 x に a を足す それまで実施した回数の操作が奇数回の場合 現在の値 x に …

問題 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)に集ま…