atcoder.jp 二分法探索 N本とM本の組み合わせですが、最大で となりうるため、すべての組み合わせを計算して、ソートして 番目を求めるのは時間がかかりすぎます。 番目を求めたいけれど、ソートするのが大変な場合、二分法で探索することを考えます。ある濃…

atcoder.jp 範囲で調べる 圧縮された配列を元に戻して (最大長さ ) 2つの配列の各要素を比較するのは時間がかかりすぎるため、圧縮した情報のまま数えていきます。ある値が、配列の何番目から何番目までの範囲になるかは、 の累積和から決まります。 ごとに…

atcoder.jp 問題文の内容把握 問題設定がわかりずらいですが、整理すると、各人について 3つの状態があります。 (A) 呼ばれていない (B) 呼ばれて、受付前 (C) 受付済イベントは3種類ありますが、イベント1 は状態(A) ⇒ (B) への遷移、イベント2は状態 (B) ⇒…

atcoder.jp b 進法での表記 N を b 進数に変換するには、それ以上割れなくなるまで繰り返し b で割り、余りを逆順に並び替えます。この結果が、 0 , 1 のみで表される場合に条件を満たすことになります。2進法は、必ず条件を満たします。N進法では 10, N-1進…

atcoder.jp 等比数列の和の公式が使えるか 問題は、 の を求めよというものです。 これは等比数列の和の公式から となり、 を計算すればよいように思えます。 この計算は、 と を求めて掛け合わせる計算になります。 は の逆元で、 を満たす のことです。こ…

atcoder.jp 連結成分を調べたいときは Union-Find 木 Union-Find 木 (「競技プログラミングの鉄則」 9.6 Union-Find 木) の考え方を利用します。 ロープを頂点とみなして、同じグループに属する頂点を木構造で表現することを考えます。Union-Find 木の表現と…

atcoder.jp二分探索で求める方法もありますが、ここでは直接求めていきます。平面上で (0,0), (A,0), (A,B), (0,B) を頂点とする長方形の内部に入る正三角形を考えていくことにします。 1辺の長さが の正三角形の頂点の一つを原点(0,0) におくと、残りの2つ…

atcoder.jp 単純グラフ：多重辺も自己ループももたないグラフ 有向グラフ：辺に向きがある（矢印）グラフ条件から、「頂点 b を中心として、"入ってくる辺 a → b"と"出ていく辺 b → c"の各ペアについて、 bの相手の頂点を直接結ぶ辺 a → c が無ければ追加す…

atcoder.jp 連結成分を調べたいときは Union-Find 木 Union-Find 木 (「競技プログラミングの鉄則」 9.6 Union-Find 木) の考え方を利用します。 同じグループに属する頂点を木構造で表現することにして、頂点 x の親を parent[x] に記録していきます。 頂点…

atcoder.jp 通れない都市があるという制約を考えないとき 移動は一方向で逆方向には進まないため、番号が小さな都市から順に「都市1から都市iに移動するまでのテレポート回数の最小値」を決定する動的計画法が使えます。 都市 i から 都市 i+k に直接移動可…

atcoder.jp 有向グラフとみなしてみる 数の大小関係 を小さいほうから大きいほうへ向かう向きを持った辺と考えると、有向グラフとして扱うこともできます。 問題は、有向グラフをトポロジカルソートして、順序が一意に定まるかどうかです。頂点 が出力辺のみ…

atcoder.jp 動的計画法で1枚目から順に数えていく 枚目のカードまで条件を満たしていたとき、 枚目のカードを加えたときに 条件を満たしたままかどうかは、枚目と 枚目のカードの表/裏の向きだけに依存します。 そこで、動的計画法のdp[flag][i] は、枚目の…

atcoder.jp N頂点の木の特徴 「木」は連結で閉路を持たない(無向)グラフです。 頂点の木は、本の辺を持ちます。 1本の辺は、両端の頂点の次数にカウントされるので、頂点の次数を合計した値は になります。 また、連結しているという条件から、次数 0 の頂点…

atcoder.jp 部分文字列 与えられた長さ の数列 の全ての連続部分列を対象としています。 部分文字列の最初の位置を 、最後の位置を とする部分文字列については、 , , を見て、異なる数であれば変更する必要があります。 つまり、次のようなコードで答えが求…

atcoder.jp 手順 i だけ考える 手順 i だけを考えると、手順を 回繰り返したときの変数 の値は、 になります。変数 の値にダブりがでるまでの手順 i の繰り返し回数を考えてみます。 と の最大公約数を として、 と表します。( は互いに素) は の倍数になり…

atcoder.jp 問題設定を整理 点 を中心として、点と対称な位置をとします。 すると、 より、 となります。この式から、 が偶数のとき は偶数、 が奇数のとき は奇数ということがわかります。 についても同じです。 そのため、スタート地点とゴール地点の座標…

atcoder.jp 二人の位置を一つの状態にしよう 高橋君が頂点 1 から頂点 N に移動し、青木君が頂点 N から頂点 1 に移動するまでのグラフの最短距離を求める問題ですが、 二人が同時に動き、かつ同色の頂点に移動できないという制約条件があります。そのため、…

atcoder.jp 動的計画法の基本問題 段目にのぼることが可能かどうかを配列 に記録していきます。 ロボットは上にしか進めないので、下の段から順に可能かどうかを確定してゆくことができます。「 段目に到達可能なら、 段目に到達可能」 または、 「 段目のい…