Codeforces Round #296:B. Clique Problem

問題 https://codeforces.com/contest/528/problem/B 考え方 各点について辺でつながることができる点を考えると間に合わないので工夫が必要である。辺でつながることのできる条件の余事象を考えてみる。 の余事象は絶対値を展開して となる。 ここで実は以…

KEYENCE Programming Contest 2019 / キーエンス プログラミング コンテスト 2019:D - Double Landscape

問題 https://atcoder.jp/contests/keyence2019/tasks/keyence2019_d 考え方 一番大きい数から置いていくとして考えていく。これは後ろの数ほど制約が厳しいことから、後ろの数のほうが置きやすいことから分かる。またすべての場合の数を求めることからそれ…

AISing Programming Contest 2019 / エイシング プログラミング コンテスト 2019:C - Alternating Path(300)

問題 https://atcoder.jp/contests/aising2019/tasks/aising2019_c 考え方 コンテスト中に考えていたこと グリッドグラフの問題。ぱっとみ二部グラフにしたくなる。過去の企業コンでも似たような問題があった。 各黒い点から dfs して白→黒→白→...とたどった…

Educational DP Contest / DP まとめコンテスト

とても楽しいコンテストだった。本番は 完だった。解けていない問題についてはゆっくり更新していく。 A (Frog 1) 今いる位置から飛べる位置への最小コストをまとめる。 B (Frog 2) A とほぼ同じ。遷移先が増えるだけ。 C (Vacation) 日連続で同じ活動ができ…

Typical DP Contest:I - イウィ

問題 https://atcoder.jp/contests/tdpc/tasks/tdpc_iwi 制約 考え方 制約的に で間に合う。文字列の問題は 文字列の問題は何となくrec(0,n)という再帰関数を呼び出したら答えが求まるようなイメージがあります。 という考え方もあるよう。 さて区間 [l, r) …

マスターオブ整数:2-2

問題 がちょうど小数第 位までの有限小数となるような はいくつあるか? 考え方 既約分数で考える。既約分数を小数に変換する時にどのような形になるかは既約分数の分母に依存する。 分母を素因数分解した時、素因数に 以外の数がある場合は循環小数になる。…

2018年の振り返りと2019年の目標

もう2019年だが、2018年の振り返りと2019年の目標を立てたいと思う。 2018年の振り返り 仕事面ではインフラエンジニアっぽいことをやっていた。VMwareとAnsibleを組み合わせたDR環境構築だったり、NetflowとElasticStackを組み合わせたネットワーク可視化基…

Typical DP Contest:H - ナップザック

問題 https://atcoder.jp/contests/tdpc/tasks/tdpc_knapsack よくあるナップザック問題の制約に色の数 がついた問題である。 考え方 愚直に色の数を集合として持つと となる。工夫が必要である。 色ごとに順番にナップザックしていくことを考える。DPとして…

Typical DP Contest:F - 準急

問題 https://atcoder.jp/contests/tdpc/tasks/tdpc_semiexp 考え方 単純に 駅 にいて連続する到着する駅の長さが の組み合わせの数というDPを考えると となるため、メモリも時間も足りない。 「状態数が多すぎるので、工夫して状態数を減らす」というテクニ…

Typical DP Contest:C - トーナメント

問題 https://atcoder.jp/contests/tdpc/tasks/tdpc_tournament 考え方 が優勝するときは 連勝する必要がある。以下のようにDPを定義する。 が 連勝するときの確率 が 連勝するときは、 が 連勝する確率に、対戦相手 が 連勝して、 が に勝つ場合であるから…

Maximum-Cup 2018:D - Many Go Round

問題 https://atcoder.jp/contests/maximum-cup-2018/tasks/maximum_cup_2018_d 考え方 部分和問題に帰着する。 のうちいくつか選んだときにその和の が に等しくなれば良い。 上で考えればよいので DP を回す最大値は 未満まででよい。 そのとき以下のよう…

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 が与えられる。 以下の整数の組 で がすべて の倍数であるような組の個数を求めよ。 制約 考え方 一つの変数を全探索することを考える。 について で の範囲を全探索する。 が定まると はそれ…