コンテストでの時間切れや解けなかった過去問を振り返って供養していく 3/15: パナソニックプログラミングコンテスト2020 E - Three Substrings 供養 問題 Difficulty: 2366 (記事作成時点) 解法 を固定したときに の相対的な開始位置を としたとき、矛盾な…
コンテストでの時間切れや解けなかった過去問を振り返って供養していく 3/8: diverta 2019 Programming Contest E - XOR Partitioning 供養 問題 Difficulty: 2371 (記事作成時点) 解法 とする である で 個の区間に分割するとする 分割した区間のXORが全て …
コンテストでの時間切れや解けなかった過去問を振り返って供養していく 3/1: AtCoder Grand Contest 024 D - Isomorphism Freak 供養 問題 Difficulty: 2342 (記事作成時点) 解法 もとの木の直径を とすると、少なくとも 色が必要 直径を だけ増加させるよう…
コンテストでの時間切れや解けなかった過去問を振り返って供養していく 2/22: AtCoder Grand Contest 014 D - Black and White Tree 供養 問題 Difficulty: 2293 (記事作成時点) 解法 木 が完全マッチング可能な場合かつその限りにおいて後手が勝つ ある完全…
概要 あるパラメータをとったときの状態が2値で表せる 更新処理が比較的単純な論理演算で表せる 連続する複数の値を同時に更新できる 上記のようなDPをするときに、いくつかのbitをまとめて数値として計算してしまうことで高速化する、いわゆる定数倍高速化…
コンテストでの時間切れや解けなかった過去問を振り返って供養していく 2/15: AtCoder Regular Contest 090 E - Avoiding Collision 供養 問題 Difficulty: 2282 (記事作成時点) 解法 - 間の最短距離を取るパス全ての組み合わせから高橋君と青木君が遭遇する…
コンテストでの時間切れや解けなかった過去問を振り返って供養していく 2/8: AtCoder Regular Contest 025 C - ウサギとカメ 供養 問題 Difficulty: 2258(estimated) (記事作成時点) 解法 について、 を始点とする各点への最短路を探索し、 である各点への最…
コンテストでの時間切れや解けなかった過去問を振り返って供養していく 2/1: AtCoder Regular Contest 074 F - Lotus Leaves 供養 問題 Difficulty: 2205 (記事作成時点) 解法 最小カットに帰着する方法と、 間の局所点連結度を求める方法がある 解法1: 最小…
概要 各辺に容量を持ち、始点と終点のあるグラフが与えられたとき、始点から終点までの最大フローを求める 最大フロー最小カット定理により、グラフの最小カットを求めることとも同値 グラフ中の辺 の容量が で、 から に だけフローが流れているとき、 に …
コンテストでの時間切れや解けなかった過去問を振り返って供養していく 1/22: AtCoder Beginner Contest 152 F - Tree and Constraints 供養 問題 Difficulty: 1903 (記事作成時点) 解法 条件のどれか1つでも満たさないようなパターンを数える 条件 を満たさ…
コンテストでの時間切れや解けなかった過去問を振り返って供養していく 1/15: AtCoder Beginner Contest 151 F - Enclose All 供養 問題 Difficulty: 1698 (記事作成時点) 解法 最小包含円の半径を求める問題 互いに異なるある2点 について、それぞれから距…
コンテストでの時間切れや解けなかった過去問を振り返って供養していく 1/8: AtCoder Beginner Contest 140 F - Many Slimes 供養 問題 Difficulty: 2066 (記事作成時点) 解法 以下の条件を満たす完全二分木を考える 葉に の各要素の値を重複なく持つ 葉以外…
概要 記号列 とパターン が与えられたとき、 と一致する の部分列を探してその位置を返す 部分一致テーブル を事前に計算しておくことで、不一致となったときに次の探索を先頭からではなく途中までは既に部分一致したものとして一部スキップできる（場合があ…
概要 要素の更新がありうる数列について、区間和の計算が高速にできる 同様に更新ありの任意区間の区間和を高速に計算可能なSegment Treeと比較して空間計算量が半分程度 ただしSegment Treeのように最小値などの計算に使うといったような応用力はない Segme…
コンテストでの時間切れや解けなかった過去問を振り返って供養していく 1/1: AtCoder Beginner Contest 149 E - Handshake 供養 問題 Difficulty: Undefined (記事作成時点) 解法 「左手で握手する相手を固定したときに幸福度上昇値が 以上となる右手の相手…
コンテストでの時間切れや解けなかった過去問を振り返って供養していく 12/28: AtCoder Beginner Contest 147 E - Balanced Path 供養 問題 Difficulty: 1656 (2019/12/28現在) 解法 各マス について とする マス の時点で偏り のパスを作れるか、というBool…
概要 組合せ数 の素数 による剰余を求める なので、それぞれの による剰余を求めればよい と帰納的に求めていくことで を求めることができる フェルマーの小定理より なので、両辺を で割ると が言える であることから残りは帰納的に求められる もしくは、 …
概要 要素の更新がありうる数列について、任意区間におけるあらかじめ定義した演算が高速にできる 最大値/最小値 一定値以上/以下の要素数 区間和 数列の各要素が葉となるような木構造をとる 木を構成する各nodeは自身の子node（葉の場合は自分自身）が表現…
概要 グラフの連結成分について調べるために使用する Union()関数とFind()関数からなる 連結成分同士の結合をUnion()関数で実施する 同じ連結成分に属する頂点はFind()関数で同じ代表点が返ってくる Find()関数で経路圧縮すると、ならし計算量がAckerman関数…
概要 通常のキューは最初にPushしたアイテムを最初にPopする(FIFO) 優先度付きキューの場合、あらかじめ指定した任意の優先度に基づく順番でPopさせることができる 優先度はキューにPushされる任意のアイテム2つについて、その二者間に順序付けができるもの…
続きもの。 準備 Googleフォームの回答と編集URLを取得する Googleドキュメントでチケットを作成する Gmailでメールを送信したりLINEにPushメッセージを送ったりする まとめ ←今ココ まとめと称して色々と思ったところを書く。 成果物 前記事までで紹介した…
続きもの。 準備 Googleフォームの回答と編集URLを取得する Googleドキュメントでチケットを作成する Gmailでメールを送信したりLINEにPushメッセージを送ったりする ←今ココ まとめ (2019/11/05更新) 用語 以降、特に説明なくこれらの用語を使う。 ユーザID…
続きもの。 準備 Googleフォームの回答と編集URLを取得する Googleドキュメントでチケットを作成する ←今ココ Gmailでメールを送信したりLINEにPushメッセージを送ったりする (2019/11/01更新) まとめ (2019/11/05更新) Googleドキュメントでチケットを作成…
続きもの。 準備 Googleフォームの回答と編集URLを取得する ←今ココ Googleドキュメントでチケットを作成する (2019/10/31更新) Gmailでメールを送信したりLINEにPushメッセージを送ったりする (2019/11/01更新) まとめ (2019/11/05更新) Googleフォームに回…
続きもの。 準備 ←今ココ Googleフォームの回答と編集URLを取得する (2019/10/30更新) Googleドキュメントでチケットを作成する (2019/10/31更新) Gmailでメールを送信したりLINEにPushメッセージを送ったりする (2019/11/01更新) まとめ (2019/11/05更新) …
