LeetCode:940. Distinct Subsequences II

問題 https://leetcode.com/problems/distinct-subsequences-ii/ 文字列 の部分文字列の個数を で求めよ 考え方 部分文字列DPのverify問題。公式のeditorialでは文字列の重複を許して部分文字列を生成した後、重複分の文字列数を差し引く...という解法になっ…

DISCO presents ディスカバリーチャンネル コードコンテスト2016 予選:C - ロト2

問題 https://atcoder.jp/contests/ddcc2016-qual/tasks/ddcc_2016_qual_c なる の組を求める問題。 考え方 単純に では間に合わないので工夫が必要である。数学をするのだが、以下の式が成り立つ。 直感的には は の素因数のみが の倍数に寄与するので最大…

codeFlyer (bitFlyer Programming Contest)オープンコンテスト:B - 交通費

問題 https://atcoder.jp/contests/bitflyer2018-final-open/tasks/bitflyer2018_final_b 考え方 各クエリに で答える必要がある。 交通費の条件に着目すると、 のとき 円であり、そうでない場合は 円であることから区間 に含まれる値の個数を求めたい。絶対…

AISing Programming Contest 2019 / エイシング プログラミング コンテスト 2019:D - Nearest Card Game

問題 https://atcoder.jp/contests/aising2019/tasks/aising2019_d 考え方 まず、ゲームがすすんだときにどのようにカードが選ばれているか確認する必要がある。高橋くんは上から大きい数を選んでいくので簡単である。青木さんは に近い数から順にとっていく…

DISCO presents ディスカバリーチャンネル コードコンテスト2019 本戦:B - 大吉数列 (Array of Fortune)

問題 https://atcoder.jp/contests/ddcc2019-final/tasks/ddcc2019_final_b 考え方 条件の数式 をぐっと睨む。条件を満たす個数が大きくなる場合は になるべく大きい数を置く場合である。 の大きい順に左から考えていくと なる について条件を満たす数列の個…

AtCoder Beginner Contest 009:D - 漸化式

問題 https://atcoder.jp/contests/abc009/tasks/abc009_4 考え方 難しい。半環上に定義される演算は行列の演算と同じことができる。フィボナッチ数列を行列で表すと以下のようになる。 これと同様の考え方でビット演算のANDとXORをANDは 、XORは に対応させ…

AtCoder Regular Contest 074:F - Lotus Leaves

問題 https://atcoder.jp/contests/arc074/tasks/arc074_d 考え方 最小カットということがわかるので、最大フローを求めればよいのだが、辺の張り方が難しい マス について、o のとき から へコスト1の辺 マス S のとき src から と へコストINFの辺 マス T …

全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019:C - Different Strokes

問題 https://atcoder.jp/contests/nikkei2019-qual/tasks/nikkei2019_qual_c 考え方 サンプルが自明すぎて、最適なケースがよくわからない。最適化問題(最大化/最小化)では簡単なケースで実験することが重要。 以下の つの料理があるケースを考える。 この…

AtCoder Regular Contest 093:E - Bichrome Spanning Tree

問題 https://atcoder.jp/contests/arc093/tasks/arc093_c 考え方 サンプル2から、MSTの重みが 未満に含まれる辺はすべて同じ色で塗らないといけないことが分かる。そこで MSTの重みが 以下である辺を同色でぬるときの条件を満たす塗り方 とすると、求めたい…

Indeedなう(オープンコンテストB):D - Game on a Grid

問題 https://atcoder.jp/contests/indeednow-finalb-open/tasks/indeednow_2015_finalb_d 考え方 よりなるべく多くの点 に訪問することが最適であることがわかる。つまり全頂点に訪問する。また最大値を最小値と読み替えると、グリッドグラフ上で最小全域木…

Mujin Programming Challenge 2018:E - 迷路

問題 https://atcoder.jp/contests/mujin-pc-2018/tasks/mujin_pc_2018_e 考え方 辺を拡張してダイクストラ法を適応させる拡張ダイクストラ法の問題である。ある時刻 において、文字列 の情報から次に上下左右に進むまでにかかる時間が分かる。まずこの各時…

WUPC 2012:E - 会場への道

問題 https://atcoder.jp/contests/wupc2012-closed/tasks/wupc2012_5 考え方 頂点 から頂点 への最短経路(時間)を求める問題である。ただし頂点 の最短経路(時間)が か で割り切れる必要がある。頂点の情報だけでDijkstra法を適応してもうまくいかない。解…

拡張ダイクストラ(Dijkstra)法

拡張Dijkstra法 グラフを拡張してDijkstra法を適応すること 「拡張ダイクストラ法」っていう言い方は、ダイクストラ法自体が拡張されている印象を受けるのでちょっとどうかと思う。「拡張グラフでのダイクストラ法」の方が適切では(まあこれを省略したのが…

牛ゲー(最短経路問題の双対問題が線形計画問題)

牛ゲー 最短経路問題の双対問題を考えると線形計画問題になるということ 最短経路が定まっており、始点 からの頂点 への最短距離を とする。またコスト の から への辺を とすると と表すことができる。逆にこのような制約式で定式化される問題は最短経路問…

AtCoder Beginner Contest 116:D - Various Sushi

問題 https://atcoder.jp/contests/abc116/tasks/abc116_d 考え方 の項をなんとかしたいので、まず食べる種類数 個を固定することを考えたい。 種類を選ぶときの最大値を考えよう。まず確実に 種類のなかで、それぞれ一番おいしさの高い寿司は選ばれているは…

CODE FESTIVAL 2017 qual B:C - 3 Steps(500)

問題 https://atcoder.jp/contests/code-festival-2017-qualb/tasks/code_festival_2017_qualb_c 考え方 距離 の頂点間に辺を張ることでもともとの距離が 縮まる。よって、もともとの頂点間のパスの長さが奇数長である頂点間の距離を にすることができ、任意…

AtCoder Regular Contest 036:D - 偶数メートル

問題 https://atcoder.jp/contests/arc036/tasks/arc036_d 考え方 考えていたこと 偶数メートルで到達できればよいので、各辺の長さ については偶奇のみが重要そう。しかし偶数長の辺どおしでの UnionFind、奇数長の辺どおしでの UnionFind を考えてもうまく…

Codeforces Round #263:C. Appleman and Toastman

問題 https://codeforces.com/contest/462/problem/C 考え方 なるべく小さい数から分割して捨てていくという貪欲法が思いつく。小さい数から捨てていくとすると、そのとき は 回たされることになる。ただし のときは 回。 なるべく数列の個数が均等になるよ…

AtCoder Beginner Contest 009:C - 辞書式順序ふたたび

問題 https://atcoder.jp/contests/abc009/tasks/abc009_3 考え方 ヒントの通り。辞書順最小を目指すときは、文字列の先頭から順にできるだけ最小になるように文字列を構成することになる。実際に文字列の の 番目の文字を としたとき、残りの文字列で 個以…

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 を回す最大値は 未満まででよい。 そのとき以下のよう…