2018-12-01から1ヶ月間の記事一覧

AtCoder Grand Contest 030:B - Tree Burning

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

yukicoder No.524 コインゲーム

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

第7回日本情報オリンピック 本選(オンライン):C - ダーツ

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

AtCoder Grand Contest 004:D - Teleporter

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

AtCoder Grand Contest 004:C - AND Grid

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

CADDi 2018:C - Product and GCD(300)

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

CADDi 2018:D - Harlequin(500)

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

JOI2018/2019 予選ページ:E - イルミネーション (Illumination)

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

CODE FESTIVAL 2018 qual B:C - Special Cake for CODE FESTIVAL(500)

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

ABC114-D:756(400)

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

PG Battle 2018 企業 ましゅまろ4:旅(難易度5)

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

JOI2018/2019 予選ページ D:日本沈没 (Japan Sinks)

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

2891 C: な◯りカット (Namo.. Cut)

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

GRL_4_A:有向グラフの閉路検査

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

CODE FESTIVAL 2016 Grand Final(Parallel) B:Inscribed Bicycle(500)

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

第14回日本情報オリンピック 本選1:鉄道旅行 (Railroad Trip)

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

ABC108-D:Robot Arms

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

ABC111-C:/\/\/\/

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

ABC108-C:Triangular Relationship

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

CODE THANKS FESTIVAL 2018(Parallel):E-Union(400)

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

第9回 日本情報オリンピック本選2:お菓子の分割

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

第9回 日本情報オリンピック本選3:つらら

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