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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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