問題 https://atcoder.jp/contests/agc030/tasks/agc030_b 制約 考え方 円周上の最長距離を求めるわけだが、以下のように円を切り開いて直線上で考えるほうが見通しがよくなる(気がする)。 円を切り開いて直線にするイメージ図 距離が長くなるように進むわけ…

問題 https://yukicoder.me/problems/no/524/ 制約 考え方 Nimであるから なる とのXORをとって かどうか判定すれば良い。ナイーブに計算すると で間に合わない。 各ビットごとに計算して、それぞれ であれば負け。そうでなければ勝ち。と考えることにする。…

問題 https://www.ioi-jp.org/joi/2007/2008-ho-prob_and_sol/2008-ho.pdf から重複を許して 点選び、それが合計得点 となる。ただし が を超えた場合は となる。合計得点の最大値を求めよ。 制約 考え方 「複数変数あるときに、ある つを全探索して他をいい…

問題 https://atcoder.jp/contests/agc004/tasks/agc004_d 制約 考え方 首都 (頂点 ) は自己ループを持たないといけないことは感覚的にすぐわかる。そのとき葉から考えて、高さが 未満の場合はそのまま辺をつけておいて、高さが になる場合は、その辺を首都…

問題 https://atcoder.jp/contests/agc004/tasks/agc004_c 制約 考え方 構築はサンプルを捨てるが基本原則なので、サンプルは気にしない。また、INPUTに応じて臨機応変に赤いマスと青いマスを構築するのではなく機械的に処理できるように構築したい。 この時…

問題 https://atcoder.jp/contests/caddi2018/tasks/caddi2018_a 個の 以上の整数 がある。 であるとき、 を求めよ。 制約 考え方 こういうのは として考えるとよい。 となるので与式は となる。 また を素因数分解して と表せたとする。するとそれぞれの素…

問題 https://atcoder.jp/contests/caddi2018/tasks/caddi2018_b つの山があり、それぞれ石が 個ある。以下のルールでプレーヤーAとBが順番にゲームをする。Aが先手である。 それぞれの山から 個以上石を取り除く。一度に選ぶ山はすべて異なる山である必要が…

問題 https://www.ioi-jp.org/joi/2018/2019-yo/2019-yo-t5-review.html 数列 と 個の区間 が与えられる。数列 からいくつかの要素 を選び、その総和を求める。ただし 個の区間に含まれる要素は つしか選ぶことができない。 この時、総和の最大値を求めよ。 …

問題 https://atcoder.jp/contests/code-festival-2018-qualb/tasks/code_festival_2018_qualb_c 制約 考え方 盤面の最大の大きさは でマスは 個ある。一回のスプレーで最大 マス埋めることができるので常に マス埋まるとすると である。このことからほぼ無…

問題 https://atcoder.jp/contests/abc114/tasks/abc114_d 整数 が与えられます。 の約数のうち、約数をちょうど 個もつ正の整数は何個あるでしょうか。 制約 考え方 という整数に着目する解法*1と一般的に解く方法がある。一般的に解く方法を考える。 まず…

問題 町が 個あり、 本の双方向に移動可能な道で結ばれています。町には から までの番号が、道には から までの番号が付いています。 番目の道は、町 と町 の間を結んでいて、通ると の幸福を得ることができます。町 と町 を を満たすように選び、同じ町を…

問題 https://beta.atcoder.jp/contests/joi2019yo/tasks/joi2019_yo_d 制約 考え方 海面を一番上から順番に下げていく方針で考える(日本出現)。 海面が下がったときに、陸地が新たに出現する場合を考える。ある区画 について の場合に新たに出現することに…

問題 https://onlinejudge.u-aizu.ac.jp/problems/2891 頂点と 辺からなる連結無向グラフ が与えられる。また以下のクエリが 回与えられる。クエリのそれぞれに回答せよ。 グラフ の 頂点 を非連結にするために削除する必要がある辺の最小本数を求めよ 制約 …

問題 https://onlinejudge.u-aizu.ac.jp/courses/library/5/GRL/4/GRL_4_A 有向グラフ上の閉路を求める問題 制約 考え方 与えられた有向グラフを とする。 に閉路が存在する場合は与えられた有向グラフは ではない。ここで トポロジカルソートが可能 のテク…

問題 https://beta.atcoder.jp/contests/cf16-exhibition-final-open/tasks/cf16_exhibition_final_b つの座標が与えられる。 点が三角形をなすとき、三角形に内部に存在する同じ半径をもつ つの円の最大の半径を求めよ。 つの円は重なってはいけない。 制約…

問題 https://joi2015ho.contest.atcoder.jp/tasks/joi2015ho_a 制約 考え方 ある鉄道の区間 を何回か通ることになる。そのたびにコストがかかるので鉄道 を通る回数を とすると、 で求めることができる。各鉄道の通る区間の回数は の区間に される。連続区…

問題 https://beta.atcoder.jp/contests/abc111/tasks/arc103_b 制約 考え方 必要条件を考える まず、構成するための必要条件を考える。 つの腕を定めたときに つの点が同時に到達できないといけない。これはそれぞれの点の距離 についてその偶奇が一致して…

問題 https://beta.atcoder.jp/contests/abc111/tasks/arc103_a 数列 が与えられる。以下の条件を満たすように数列を書き換える時、書き換える最小の数列の要素の個数はいくつか？ 数列に現れる数はちょうど 種類 制約 は偶数 考え方 が奇数の項と偶数の項に…

問題 https://beta.atcoder.jp/contests/abc108/tasks/arc102_a が与えられる。 以下の整数の組 で がすべて の倍数であるような組の個数を求めよ。 制約 考え方 一つの変数を全探索することを考える。 について で の範囲を全探索する。 が定まると はそれ…

問題 https://beta.atcoder.jp/contests/code-thanks-festival-2018-open/tasks/code_thanks_festival_2018_e 制約 考え方 DPをする。 := 数 を 個余るような場合の数 とする。この時 が 個余っていれば に 個余るようにすることができる。また が 個もとも…

問題 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0550 制約 考え方 DPで数え上げする。 dp[i][j][k] := 今 i 番目で A が j 個で、今 k であるときにかかる最小の時間 とする。 切る位置に対してそれぞれ、切る or 切らない の2通りを考える…

問題 https://www.ioi-jp.org/joi/2009/2010-ho-prob_and_sol/2010-ho.pdf 制約 考え方 つららはいずれすべて cm になる。つららの長さ が大きいものから降順に考えていく。 が伸び始めることができるのは のつららよりも のつららの長さが大きいときである…

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