定義 1. 環・体・分配法則 集合 $R$ に加法 $+$ と乗法 $\cdot$ の二つの二項演算が定められているとする。次の条件を満たすとき、$R$ を環という。 $(R,+)$ はアーベル群である。 乗法は結合的である。すなわち、すべての $x,y,z\in R$ に対して $(xy)z=x(yz)$ が成り立つ。 乗法は加法に対して左右両側に分配する。すなわち、す...

集合論、代数学、解析学で使う基本的な定義をまとめる。 1. 集合 集合とは、互いに区別できる対象を集めたものであり、その対象を元という。$x\in X$は、$x$が集合$X$の元であることを表す。 2. 外延的定義と内包的定義 集合は、元を列挙する外延的定義、または元が満たす性質を示す内包的定義によって表せる。例えば、英小文字全体の集合は [{a,b,c,\ldots,z}] と...

定理 相異なる始点 $s$ と終点 $t$ を持つ有限有向ネットワーク $G=(V,E)$ を考える。各有向辺 $e$ には有限かつ非負の容量 $c_e$ が与えられている。実行可能なフローとは、各辺に値 $f_e$ を割り当て、 [0\leq f_e\leq c_e] を満たし、$s,t$ 以外のすべての頂点で流入量と流出量が等しくなるものである。フロー...

フローネットワークと実行可能フロー フローネットワークとは、互いに異なる始点(source) $s$ と終点(sink) $t$ を指定した有限有向グラフ $G=(V,E)$ である。各辺 $e$ には有限かつ非負の容量 $c_e$ が与えられる。端点が同じでも辺はそれぞれ別のものとして扱う。これは平行辺や互いに逆向きの辺がある場合に重要である。 フローとは、元の各辺 $e$ に実数 $...

入れ子区間定理 実数全体の集合 $\mathbb{R}$ における、空でない閉区間の列 $(I_n)_{n\in\mathbb{N}}$ を考える。各区間を $I_n=[a_n,b_n]$ とし、その 長さを $|I_n|=b_n-a_n$ と表す。 次の二つの条件を仮定する。 すべての $n\in\mathbb{N}$ について $I_{n+1}\subseteq I_n$ で...

定理 $(a_n)$を実数列とする。 $(a_n)$が単調非減少で上に有界ならば、$\sup{a_n:n\in\mathbb{N}}$に収束する。 $(a_n)$が単調非増加で下に有界ならば、$\inf{a_n:n\in\mathbb{N}}$に収束する。 したがって、実数の単調列が有限な実数極限を持つことと、有界であることは同値である。 単調非減少列の場合の証明 $(...

数列についての定理 $d\geq 1$とし、有限次元ユークリッド空間$\mathbb{R}^d$の有界な数列$(x_n)$を 考える。このとき$(x_n)$は収束する部分列を持つ。その極限は$\mathbb{R}^d$の点 であるが、数列の項のいずれかと一致するとは限らない。 数列に必要な仮定は有界性だけである。特に、数列の項全体からなる集合が閉集合 である必要はない。 証明 $x_...

フロイド–ワーシャル法 フロイド–ワーシャル法は、重み付き有向グラフにおけるすべての順序付き頂点対の最短距離を求める。負の辺重みも扱えるが、対象の頂点対の経路に影響する負閉路がない場合に限り、最短距離は有限値になる。この動的計画法では、中継頂点の候補を決められた順に一つずつ許可していく。 動的計画法の漸化式 頂点に 0 から V - 1 まで番号を付ける。D^(k)[i][j] を、中...

ユークリッドの互除法は、2つの非負整数を、共通の約数を保ったままより小さい組へと繰り返し置き換え、最大公約数（gcd）を求める方法である。 基本となる等式 $b>0$である非負整数$a,b$を考える。ユークリッドの除法により、次を満たす整数$q,r$が一意に存在する。 [a=bq+r,\qquad 0\le r<b.] 重要な性質は次の等式である。 [\gcd(a,b)...

BOJ 3653: 映画コレクション 映画番号ではなく位置を管理する 映画をリクエストするたびにDVDの位置が変わるため、映画番号だけを添字にしても、その映画より上に何枚あるかを直接表せない。そこで、各位置が使用中かどうかを管理する。DVDがある位置を 1、空いている位置を 0 とし、Fenwick treeでその区間和を求める。 1ケースの映画数を N、リクエスト数を M とする。先...

BOJ 19565 - 数列の作成 有向グラフによるモデル化 数列の各要素は $1,\dots,N$ のいずれかで、先頭と末尾はどちらも 1 でなければならない。また、同じ順序付き隣接ペアを二度以上使うことはできない。$(x,y)$ と $(y,x)$ は異なるペアであり、$(x,x)$ のように同じ値からなるペアも使える。 値ごとに頂点を一つ作り、すべての順序付きペア $(x,y)$...

BOJ 1395 - スイッチ 問題とセグメント木 スイッチが $N$ 個あり、最初はすべてオフである。各命令では $1\le S\le T\le N$ を満たす区間を指定する。0 S T は両端を含む区間 $[S,T]$ のすべてのスイッチを反転し、1 S T はその区間でオンになっているスイッチの個数を出力する。 区間内のスイッチを一つずつ変更すると、命令一回に線形時間がかかる場合...

BOJ 1035: Moving Pieces 方針: 配置全体を状態とする幅優先探索 盤面は25マスで、駒は最大5個です。状態では、すべての駒の位置をまとめて表します。各マスの占有状態を25ビット整数で表し、(r, c) に駒があれば r * 5 + c 番目のビットを立てます。駒に区別はないため、駒の並び順を考える必要はありません。 状態グラフの辺は、ルールに従った1回の移動そのも...

問題ページ 問題のモデル 敵が配置された2行N列の円形グリッドがある。部隊1つは1マスを担当するか、敵の数の合計がW以下である隣接する2マスをまとめて担当できる。すべてのマスを担当するために必要な部隊数の最小値を求める。隣接するマスは同じ列の上下、または同じ行の隣り合う列である。同じ行ではN列と1列も隣接する。 円周をまたぐ2組が、通常のプロファイルDPをそのまま適用する際の障害になる...

整数に対するベズーの恒等式 $a,b\in\mathbb Z$ は同時に 0 ではないとし、 [g=\gcd( a , b )>0] とおく。このとき、次の等式を満たす整数 $x,y$ が存在する。 [ax+by=g.] さらに、$a,b$ のすべての整数線形結合からなる集合は、ち...

BOJ 5373番: キュービング モデルと回転方向 各ステッカーをキューブ片の位置 $(x,y,z)$ と外向き法線で表します。軸はキューブに固定し、$+x$ は右、$+y$ は上、$+z$ は前を向くものとします。位置の各座標は ${-1,0,1}$ のいずれかで、法線は6方向の符号付き軸ベクトルのいずれかです。色はステッカーに属するため、層を回すと位置と法線が一緒に移動します。 ...

問題リンク 元の方法が遅い理由 (値, インデックス) の組を一度ソートする処理は O(N log N) ですが、その後、各区間クエリで全 N 要素を走査するため、クエリ処理には最悪 O(NM) 時間がかかります。変数をローカルではなくグローバルに宣言しても保存期間が変わるだけで、必要な処理量は変わらず、漸近計算量にも影響しません。 永続セグメント木 配列の値を、ソート済みの異なる値...

BOJ 1520 - 下り坂の道 解法：DAG上の動的計画法 各マスを頂点とみなします。上下左右に隣接するマスのうち、現在のマスより低いマスへ向かう有向辺を張ります。辺をたどるたびに高さが下がるため、有向サイクルは存在せず、このグラフはDAGです。高さが等しい隣接マスの間には辺を張りません。 左上から右下までの有向経路数を求めます。メモ化付きの再帰DFSなら漸化式をそのまま表せますが、...

問題 ダイヤルの操作規則と動的計画法 ダイヤルには左から順に番号を付けます。ダイヤルiを正の回数だけ回すと、i番目とその下にあるすべてのダイヤルが左に回転します。負の回数だけ回すと、i番目のダイヤルだけが右に回転します。出力する回転数は符号付き整数で、正数は左回転、負数は右回転を表します。 左から順に処理します。dp[i][carry]を、i番目まで処理したときの最小回転数とします。c...

問題リンク モデル化: 交差グラフと連結成分 入力された各線分をグラフの頂点とし、2つの閉線分が交差するときに限り、その頂点間に辺を張ります。グループはこのグラフの連結成分です。直接交差していなくても、交差する線分の列でつながっていれば同じグループに属します。そこで、すべての線分の組を調べ、交差する組を素集合データ構造（DSU）で併合します。すべての判定後、DSUの根の個数がグループ数、...

問題リンク 交差部分の面積 2つの円の中心を $C_1=(x_1,y_1)$、$C_2=(x_2,y_2)$、半径を $r_1,r_2$ とし、中心間の距離を $d=\sqrt{(x_1-x_2)^2+(y_1-y_2)^2}$ とする。円の位置関係に応じて交差部分の面積を求める。 $d\ge r_1+r_2$ なら、円は離れているか外接しているため、交差部分の面積は $0$ で...

問題リンク 出発地点から目的地までの距離を $D_0=\sqrt{x^2+y^2}$ とする。歩いて直行する場合の時間は $D_0$ である。ジャンプは方向にかかわらず必ず距離 $D$ だけ移動し、時間 $T$ がかかる。残りの距離は歩いて移動できる。 $q=\lfloor D_0/D\rfloor$、$r=D_0-qD$ とおくと、$0\le r<D$ である。候補となる時間は次...

問題ページ 向きの判定と線分交差 3点 A、B、C の向きを表す値を次のように定義する。 cross(A, B, C) = (B.x - A.x)(C.y - A.y) - (B.y - A.y)(C.x - A.x) 値が正なら、C は有向直線 AB の反時計回り側にあり、負なら時計回り側にある。0の場合は3点が一直線上にある。 入力では2本の線分 AB と CD が与えられる...

BOJ 17387: Crossing Lines 2（線分の交差 2） 方針: 向き判定と閉じた線分の範囲 3点 $P$、$Q$、$R$ に対する外積 $(Q-P) \times (R-P)$ の符号から、点 $R$ が有向直線 $PQ$ のどちら側にあるかが分かります。値が正なら反時計回り、負なら時計回り、0なら3点は同一直線上です。 線分を $AB$、$CD$ とします。$C$ ...

問題ページ 問題モデル N人の社員とM件の仕事があり、各社員が担当できる仕事の一覧が与えられる。各社員は通常最大1件を担当でき、追加割り当ての総数はK以下である。追加割り当ては社員1人につき最大1件なので、各社員の担当数は最大2件となる。各仕事は高々1人にだけ割り当てる。この条件のもとで、割り当てる仕事数を最大化する。 最大フローモデル 頂点はソース、N人の社員、ボーナス頂点、M件の...

問題ページ 問題のモデル N人の社員とM件の仕事があり、各社員が担当できる仕事の一覧が与えられる。各仕事は高々1人の社員に割り当て、各社員には高々2件の仕事を割り当てる。この条件で、割り当てる仕事数を最大化する。 二部グラフで社員ごとにマッチング用のスロットを2つ作り、両方のスロットをその社員が担当できるすべての仕事につなぐ。マッチングでは各スロットと各仕事を高々1回しか使わないため、...

BOJ 11375: 情熱的なカンホ 方針: 二部マッチング 左側の頂点を社員、右側の頂点を仕事とします。社員が担当できる仕事ごとに、社員から仕事へ辺を張ります。有効な割り当てはマッチングです。選んだ辺の中で、同じ社員や仕事が複数回現れてはいけません。求めるのは最大マッチングのサイズです。 社員を1人ずつ処理し、深さ優先探索で増加路を探します。現在の社員が担当できる仕事のうち、この探索...

問題ページ 着眼点 文字列 S の部分文字列のうち、回文ではないものの最大長を求める。S 自体が回文でなければ、文字列全体が答えなので N。S が回文で、すべての文字が同じなら、すべての部分文字列も回文なので -1。それ以外、つまり回文だが文字がすべて同じではない場合の答えは N - 1 である。 証明 文字列全体が回文でなければ、S が長さ N の回文ではない部分文字列なので答えは...

問題: BOJ 16235 — 木の投資 · 한국어 · English 毎年、春、夏、秋、冬の順に処理します。春には各マスの木を若い順に処理します。木は年齢と同じ量の栄養を消費してから、年齢が1増えます。栄養が足りなくなると、その木と同じマスでまだ処理していないより年上の木はすべて枯れるため、そのマスの処理を止めます。夏には枯れた木ごとに、年齢の floor(年齢 / 2) に相当する栄...

問題: BOJ 1240 — ノード間の距離 · 한국어 · English 入力グラフは木なので、任意の2頂点間には経路がちょうど1つだけ存在します。そのため、最短距離はその唯一の経路に含まれる辺の重みの合計です。一般的な最短経路アルゴリズムを使う必要はありません。 各クエリでは、開始頂点から明示的なスタックを使って探索します。スタックの各要素には現在の頂点、親頂点、開始点から現在の頂...

問題 解説 各時間の開始時に、ボード外側に追加した空白の枠からBFSを行い、外気と つながっている空気マスを調べます。外気に隣接するチーズはその時間に溶けます。 まず溶けるマスをすべて集めてから同時に取り除くため、取り除いた後に初めて 露出するチーズが溶けるのは次の時間です。 各融解ラウンドの直前に残っているチーズの総数を保存します。あるラウンドで 最後のチーズが溶けたとき、保存した数...

問題: BOJ 14890 — 滑走路 · English · 한국어 隣り合うマスの高低差が 0 または 1 で、高さの差が 1 の場所すべてに長さ L の傾斜路を置けるなら、その行または列に道を作れます。傾斜路 1 つは低い側の L マスを占有します。その区間の高さはすべて同じで、線の範囲内に収まり、ほかの傾斜路がすでに使ったマスと重なってはいけません。 1 本の線を左から右へ調べ、...

問題: BOJ 11437 — 最近共通祖先 · English · 한국어 木の根を頂点 1 とします。再帰ではなく幅優先探索を使い、各頂点の深さと直上の親を記録します。根の親は 0 とし、この番兵頂点の祖先もすべて 0 です。入力は木なので、根以外の各頂点は親からちょうど一度だけ訪問されます。再帰 DFS の代わりにキューを使うため、頂点 50,000 個が一直線につながった木でも呼び...

問題: BOJ 5052 — 電話番号リスト · English · 한국어 電話番号をすべて辞書順にソートし、隣り合う番号だけを比較します。ある番号が別の番号の接頭辞なら、短い番号が長い番号より辞書順で前に並びます。短い番号が終わった位置で、長い番号にはまだ数字が残っているためです。したがって、接頭辞の関係にある番号の組は、ソート後には必ず隣り合います。2 つの番号が完全に同じ場合も、一...

問題: BOJ 17144 — Fine Dust Simulation · English · 한국어 毎秒、ほこりのあるマスは floor(ほこり / 5) の量を、上下左右に隣接するマスのうち盤面内にあり空気清浄機ではないマスへ拡散します。すべてのマスは同時に拡散するため、ほこりの量を書き換える前に、別の配列へ各マスから移動する量を加算します。拡散後、元のマスには移動しなかった分が残...

問題: BOJ 1339 — 単語の数学 · English · 한국어 各文字には、その文字が現れるすべての位置で同じ数字を割り当てます。単語の一の位にある文字はその数字を1回分だけ加算し、十の位なら数字の10倍を加算します。さらに左の位も同様です。たとえば ABC の値は 100 * value[A] + 10 * value[B] + value[C] です。すべての単語について各桁...

問題: BOJ 2169 — ロボットコントロール · 한국어 · English ロボットは N × M のグリッドの左上のマスから出発し、右下のマスに到達しなければなりません。通過した各マスの値をスコアに加算します。移動できる方向は左、右、下のみで、上には移動できず、同じマスを二度通ることもできません。通過したマスの値の合計を最大化することが目標です。 ポイントは、グリッドを1行ずつ...

問題: BOJ 15683 — 監視 · 한국어 · English CCTVは種類ごとに定められた方向を監視し、90度ずつ回転できます。タイプ1は1方向、タイプ2は互いに反対の2方向、タイプ3は隣り合う2方向、タイプ4は3方向、タイプ5は4方向すべてを監視します。異なる向きの数はそれぞれ4、2、4、4、1通りです。監視の光線はほかのCCTVや空きマスを通過しますが、壁または盤面の端で止ま...

問題: BOJ 16234 — 人口移動 · English · 한국어 1 日の間、隣り合う 2 つの国の人口差が L 以上 R 以下なら国境を開きます。開いた国境を通じてつながった国々が連合となり、2 か国以上からなる各連合では、連合の平均人口の小数点以下を切り捨てた値を全ての国に適用します。その日の連合はすべて、人口を更新する前の盤面をもとに判定してから一斉に更新します。国境が一つも...

問題: BOJ 13460 — ビーズ脱出 2 · English · 한국어 盤面には壁、穴、赤と青のビーズがあります。盤面を一方向に傾けると、ビーズは壁に当たるか穴に落ちるまで移動します。10 回以内の傾斜で赤いビーズを穴に入れ、青いビーズは落とさないことが目標です。 状態は 2 つのビーズの現在位置 (赤, 青) です。各状態から 4 方向をそれぞれ試します。傾ける方向により前方に...

問題: BOJ 14500 — テトロミノ · English · 한국어 N × M の盤面で、辺を共有してつながる4マスを覆うテトロミノを置きます。覆ったマスの値の合計の最大値を求めます。5種類のテトロミノについて、すべての回転・反転を考慮します。 隣接するマスを1つずつ追加する単純パスの深さ優先探索では、棒・L・S・Z型は見つけられますが、T型は作れません。T型の分岐点では、1本の...

問題: BOJ 3190 — ヘビ · English · 한국어 ヘビは盤面の左上のマスから右向きにスタートします。毎秒 1 マス進み、頭が盤面の外に出るか、胴体が占めているマスに入ると、その秒にゲームが終了します。進む先にリンゴがあればヘビは伸びます。リンゴがなければ尻尾が 1 マス進みます。移動が完了した後、その秒に予定されている方向転換を適用します。 胴体を尻尾から頭の順に de...

問題: BOJ 14503 — ロボット掃除機 · English · 한국어 ロボットは現在のマスを掃除してから、左へ90度回転して前方を確認します。4方向を順に調べ、未掃除の空きマスが見つかったらその方向へ1マス進み、現在マスの掃除から再開します。4マスすべてを確認しても移動先がなければ、向きを変えずに後方へ1マス下がります。後方が壁、または部屋の範囲外なら停止します。すでに掃除したマ...

問題: BOJ 14499 — サイコロを転がす · 한국어 · English サイコロの6面の値を、固定方向の配列 TOP、BOTTOM、NORTH、SOUTH、EAST、WEST に保持します。不変条件は、各配列要素が常にその方向を向いている面の値を表すことです。転がすたびに回転軸まわりの4面だけが入れ替わり、残りの2面はそのままです。 東へ転がすと、元の西面が上面になり、元の上面...

問題: BOJ 16236 — 赤ちゃんザメ · 한국어 · English サメが現在いる位置から、食べられる魚を探すたびに BFS を行います。サメより大きな魚がいるマスには入れません。空きマスとサメ以下の大きさの魚がいるマスには入れます。食べられる魚はサメより厳密に小さい魚です。つまり、同じ大きさの魚は通過できますが、食べることはできません。 BFS は距離の小さいマスから順に訪問...

問題: BOJ 15686 — チキン配達 · English · 한국어 都市には家が H 軒、チキン店が C 店あります。ちょうど M 店を残すとき、各家のチキン距離は、残したチキン店のうち最も近い店までのマンハッタン距離です。都市のチキン距離は全ての家のチキン距離の合計であり、この合計を最小化します。 順列ではなく組み合わせを列挙します。DFSではチキン店のインデックスを昇順に選ぶ...

問題: BOJ 13275 — 最長回文部分文字列 · 한국어 · English Manacher アルゴリズムでは、考えられる各中心について回文の半径を記録します。奇数長の回文の中心は1文字です。radiusOdd[i] は中心の文字を含む半径なので、回文の長さは 2 * radiusOdd[i] - 1 です。偶数長の回文の中心は i の直前にある隙間です。radiusEven[i]...

問題: BOJ 17131 — キツネが情報島にやってきた理由 · 한국어 · English キツネのトリプルで中央となる点を p とすると、1点は p より厳密に左、もう1点は厳密に右にあり、どちらの点も y 座標が p より大きくなければなりません。この条件を満たす左側の点の数を L(p)、右側の点の数を R(p) とすると、p を中央とするトリプルは L(p) * R(p) 個です...

問題: BOJ 10999 — 区間和を求める 2 · English · 한국어 配列には N 個の値があります。タイプ1の操作では、1-indexed で両端を含む区間 [B, C] のすべての要素に D を加算します。タイプ2では同じ形式の区間の合計を出力します。配列サイズは最大100万で、区間和は32ビット整数の範囲を超えるため、セグメント木とすべての計算に long long を...

問題: BOJ 1725 — ヒストグラム · English · 한국어 各棒を高さとする長方形のうち最も幅広いものは、その棒が区間内で最も低い棒となる範囲にあります。その範囲の左右の境界は、対象の棒より厳密に低い最も近い棒です。左から単調スタックで走査すれば、低い棒に出会った時点で境界を確定できます。 スタックには高さが非減少となるよう棒のインデックスを格納します。現在の棒がスタック...

問題: BOJ 2268 — 数の合計 7 · English · 한국어 配列の要素数は N で、初期値はすべて 0 です。0 a b は、1 始まりで両端を含む区間 [min(a, b), max(a, b)] の合計を出力します。1 a b は a 番目の要素に b を代入し、以前の値を置き換えます。問題の代入値は 0 以上で、0 の場合もあります。区間和は 32 ビット整数の範囲を...

問題: BOJ 1275 — コーヒーショップ2 · English · 한국어 配列はクエリごとに変化します。各クエリでは x から y までの和を求め、その後、位置 a の値を b に代入します。反復型セグメント木では、配列の各値を葉に置き、内部ノードには左右の子ノードの和を保存します。 木の配列にはサイズ 2N を使います。0始まりのインデックス i の葉は N + i に置き、各...

問題: BOJ 10868 — 最小値 · English · 한국어 各クエリでは 1 始まりの両端を含む区間 [a, b] が与えられ、その区間の最小値を求めます。反復型セグメント木では、N 個の値を tree[N..2N) に格納します。内部ノードは 2 つの子の最小値として下から順に構築します。このコンパクトな配列配置は、N が 2 のべき乗でなくても使えます。 クエリを 0 始...

問題: BOJ 2836 — 水上タクシー · English · 한국어 タクシーは位置 0 から出発し、位置 M まで移動しなければなりません。乗客は一直線上の経路に沿って、どちらの方向にも移動できます。タクシーはまず 0 から M に向かって進みます。出発地点より右側が目的地の乗客は、通過時に降ろせるため、必ず進む距離 M 以外の追加距離は発生しません。 一方、目的地 destin...

問題: BOJ 5419 — 北西風 · English · 한국어 各テストケースで、x1 <= x2 かつ y1 >= y2 を満たす点の組 (x1, y1)、(x2, y2) の数を数えます。左から右へのスイープ順で各組を一度だけ数えます。そのため、x 座標が同じ点は y 座標の大きい順に処理します。また、座標が完全に同じ点も入力中の別々の点なので、同じ座標のコピーを 2...

問題: BOJ 2170 — 線分の長さの合計 · English · 한국어 各線分は、両端の座標の間にあるすべての点を覆います。少なくとも1本の線分に覆われる部分の合計の長さを求めます。区間を左端の昇順に並べ、左から順に見ながら、現在まとめている区間の最も右の端点を保持します。次の区間の左端が現在の右端以下なら、重なるか端点が接しているため、必要に応じて右端を伸ばします。次の左端が現在...

問題: BOJ 4013 — ATM · English · 한국어 解法 開始地点から出発し、レストランに到着する経路で集められる金額の最大値を求めます。強連結成分（SCC）の内部ではすべての頂点を相互に行き来できるため、その成分にある金額をすべて回収できます。各SCCを構成頂点の金額の合計を重みとする1頂点に縮約すると、有向非巡回グラフ（DAG）になります。 開始SCCから到達でき...

問題: Codeforces 1638A — Reverse · 한국어 · English 配列は 1..n の順列です。1つの区間を選んで反転し、辞書順で最小の順列を作ります。 左から調べ、p[i] != i + 1 となる最初の位置 i を探します。それより前の位置には、すでに置ける最小の値が入っているため、そのまま固定します。値 i + 1 は順列中にちょうど1回現れるので、その...

問題: BOJ 11281 — 2-SAT - 4 · English · 한국어 反復型Kosaraju法による2-SAT 入力節 (a ∨ b) は、含意 ¬a → b と ¬b → a に変換できます。符号付きリテラルをそれぞれ頂点として表します。正のリテラル x のインデックスは x - 1、負のリテラル ¬x のインデックスは N + x - 1 です。リテラルの否定はインデッ...

問題: AtCoder ARC 135 C — XOR to All · English · 한국어 各添字 i について sum_j (A[i] XOR A[j]) を計算し、すべての i の中から最大値を求めます。ビット位置 b ごとに考えます。A[i] の b ビット目が 0 なら、XOR の結果でそのビットが 1 になるのは、同じビットが 1 である count[b] 個です。一方...

問題: AtCoder ARC 135 B — Sum of Three Terms · English · 한국어 長さ N の配列 A が与えられます。長さ N + 2 の非負整数配列 B が存在し、すべての 0 <= i < N について A[i] = B[i] + B[i + 1] + B[i + 2] を満たすか判定します。存在すれば任意の配列を Yes とともに...

問題: AtCoder ARC 135 A — Floor, Ceil Decomposition English · 한국어 正の整数xについて、x <= 4ならf(x) = xです。それ以外の場合、xをfloor(x / 2)とceil(x / 2)に分け、対応する関数値の積を998244353で割った余りとして定義します。 f(x) = f(floor(x / 2)) * f...

問題: Codeforces 1637B — MEX and Array · 한국어 · English 配列を連続した空でない区間に分割します。分割のコストは区間数と各区間のMEXの合計であり、配列の値は可能な分割のうち最大のコストです。与えられた配列のすべての空でない部分配列について、その値の合計を求めます。 公式制約は 1 <= t <= 30、1 <= n &l...

問題: BOJ 3648 — アイドル · English · 한국어 各テストケースでは、すべての節を満たし、変数 1 を真にする必要があります。節 (a OR b) は、含意 ¬a → b と ¬b → a の2本の辺に変換します。変数 1 を真にする条件は単位節 (1 OR 1) として追加し、他の節と同じように ¬1 → 1 の辺を作ります。 入力リテラルは符号付き整数です。変数...

問題: Codeforces 1637A — Sorting Parts · English · 한국어 各テストケースでは、1 <= k < n を満たす分割位置 k を選びます。接頭部分 a[1..k] と接尾部分 a[k+1..n] をそれぞれ独立にソートします。この操作後、配列全体が非減少順にならないような有効な分割が存在するかを判定します。任意の部分区間を 1 つ選ぶ...

問題: Codeforces 1637C — Andrew and Stones · English · 한국어 1回の操作では i < j < k を満たす3つの添字を選び、中央の山 j に石が2個以上あれば、そこから石を2個取り出して山 i と山 k に1個ずつ置きます。目標は、最初と最後の山だけに石を残すことです。 最小操作回数 各操作は1つの内部の山を中心に行い、そ...

問題: BOJ 11280 — 2-SAT - 3 · English · 한국어 各節 (a OR b) は、含意 ¬a → b と ¬b → a の2本の辺に変換できます。入力のリテラルは符号付き整数です。変数 i の正リテラル i は頂点 i - 1、負リテラル -i は頂点 N + i - 1 に対応させます。したがって否定リテラルの頂点は、v < N なら v + N、それ...

問題: BOJ 4196 — ドミノ · English · 한국어 各テストケースでは、有向グラフが与えられます。ドミノ u を倒すと、有向辺に沿って u から到達できるドミノがすべて倒れます。すべての頂点を倒すために最初に倒すドミノの最小数を求めます。 まず頂点を強連結成分（SCC）に分けます。同じSCC内ではどの頂点からもほかのすべての頂点に到達できるため、その成分のドミノを一つ倒...

問題: BOJ 3977 — サッカー戦術 · English · 한국어 グラフを強連結成分（SCC）に分けると、各SCCを頂点とし、異なるSCC間の辺を残した縮約グラフが得られます。入次数が0のSCCは、ほかのSCCから到達できない始点です。そのようなSCCが1つだけなら、その中の頂点すべてが答えです。2つ以上ある場合は Confused を出力します。 Kosarajuの2回の探索...

問題: BOJ 13511 — 木とクエリ 2 · English · 한국어 頂点1を根とし、反復処理で木を探索します。各頂点の深さと親を記録します。根の親は根自身とすることで、祖先テーブルの値をすべて有効に保ちます。up[v][j] は v から辺を 2^j 本たどって上がった祖先で、weight[v][j] はその辺の重みの合計です。2^j 本のジャンプを、連続する二つの 2^(j-...

問題: BOJ 1509 — 回文の分割 · English · 한국어 長さ N の文字列 s を連続する回文の部分文字列に分割するとき、部分の数の最小値を求めます。まず palindrome[l][r] を計算します。これは両端を含む部分文字列 s[l..r] が回文かどうかを表します。部分文字列の長さが短い順に計算すると、両端の文字が一致し、長さが2以下であるか、内側の部分文字列がす...

問題: BOJ 11003 — 最小値 English · 한국어 方針 各位置 i で求める区間は [max(0, i - L + 1), i] です。そのため最初の L - 1 個の区間には、そこまでに入力された値だけが含まれ、存在しない要素で埋めることはありません。 候補のインデックスを単調増加する順にデックへ格納し、値は別のプリミティブ配列に保持します。A[i]を追加する前に...

問題: BOJ 3176 — 道路ネットワーク · English · 한국어 頂点1を根とし、明示的なスタックで木を走査して、各頂点の深さ、直近の親、1つ上へ登る辺の最小・最大重みを記録します。その後、2^j 個分のジャンプを2つの 2^(j-1) 個分のジャンプに分け、祖先・最小値・最大値のテーブルを構築します。根の祖先は根自身とし、根の空の経路には中立となる極値を設定します。これらは...

問題: BOJ 11438 — LCA 2 · English · 한국어 頂点1を根とし、各頂点 v の深さと up[v][j] を記録します。up[v][j] は v から辺を 2^j 本たどって上がった祖先です。根はすべての段階で自分自身を祖先とします。この規則により祖先テーブルの値は常に有効になり、根でのジャンプも安全です。 祖先テーブルは up[v][0] = parent[v...

問題: BOJ 17435 — 合成関数とクエリ English · 한국어 解法 入力では整数 1..M 上の関数 f が与えられ、各クエリは開始値 x に関数を K 回適用した値、つまり f^K(x) を求めます。関数を1回ずつ適用すると、クエリごとに最大500,000回の処理が必要になるため、二分リフティングで関数のべき乗を前計算します。 up[b][x] を、x に f をち...

問題: BOJ 3584 — 最近共通祖先 · English · 한국어 各テストケースでは、N 個の頂点を持つ根付き木と、最近共通祖先（LCA）を求める頂点のペアが与えられます。テストケースごとにクエリはちょうど 1 つです。入力の辺は親から子の向きで与えられるため、各子の親を parent 配列に保存します。親を持たない唯一の頂点が根です。 クエリの最初の頂点から parent を...

問題: BOJ 1086 — パク・ソンウォン · English · 한국어 部分集合動的計画法 入力には N 個の文字列があります。順列では文字列そのものではなく、それぞれの位置を順に選びます。同じ内容の文字列が複数あっても位置が異なるため別々の選択肢であり、順列の総数は N! です。 dp[mask][r] を、mask に含まれる文字列を連結したとき、その値を K で割った余り...

問題: BOJ 2098 — 旅行巡回問題 English · 한국어 ビットマスク動的計画法 出発都市を0に固定します。どの巡回路も開始位置を回転させれば、都市0から出発する形で表せます。状態(current, visited)のvisitedは、出発都市0を含む訪問済み都市のビットマスクです。dp[current][visited]は、未訪問の都市をそれぞれ一度ずつ訪問してから都市...

問題: BOJ 17404 — RGB距離 2 English · 한국어 方針 各家は赤・緑・青のいずれかで塗り、隣り合う家は異なる色にする必要があります。家は円形につながっているため、最初の家と最後の家も隣同士です。この2軒も異なる色にします。 最初の家の色を1つに固定して、線形の動的計画法を実行します。dp[c]を、現在の家まで塗ったときに現在の家を色cにする最小費用とします。...

問題: BOJ 3665 — 最終順位 · English · 한국어 前年の順位から、すべてのチームの組み合わせについて順序が分かります。順位の高いチームから低いチームへ有向辺を張ると、完全な有向グラフになります。今年順位が入れ替わった2チームについては、その組の辺の向きを反転します。隣接行列と辺の到着先の入次数を同時に更新し、トポロジカルソートに使う情報を保ちます。 Kahnのアルゴ...

問題: BOJ 1766 — 問題集 · English · 한국어 有向辺 A -> B は、問題 A を問題 B より先に解く必要があることを表します。したがって、各頂点をちょうど一度ずつ含み、すべての辺について始点が終点より前に来るトポロジカル順序を求めます。次に解ける問題が複数ある場合は、番号が最も小さい問題を選びます。 Kahn のアルゴリズムでは、未解決の前提問題数であ...

問題: BOJ 1009 — 分散処理 · English · 한국어 各テストケースについて、a^b の一の位、つまり 10 で割った余りを二分累乗法で計算します。繰り返し周期を別途探す必要はなく、底が 10 で割り切れる場合も正しく処理できます。得られた余りはコンピューターの番号を表します。ただし余りが 0 の場合は 10 番を意味します（コンピューターの番号は 1 から 10 です）...

問題: AtCoder ABC 238 C — digitnum · English · 한국어 1からNまでのすべての整数について、10進表記の桁数を合計し、998244353で割った余りを出力します。 整数を桁数ごとにまとめます。桁数がdの整数の範囲は[10^(d-1), min(N, 10^d - 1)]です。この範囲に含まれる整数の個数にdを掛け、答えに加算します。範囲の終端がN...

問題: AtCoder ABC 238 B — Pizza · English · 한국어 最初の切れ目を0°とします。指示ごとに包丁を時計回りに指定された角度だけ回すため、新しい切れ目の位置は直前の位置に回転角を加え、360で割った余りになります。こうして得られるN個の位置と0°を配列に格納します。同じ位置が複数回現れてもそのまま扱います。これは既存の切れ目と重なる切れ目ができ、幅0の間...

問題: AtCoder ABC 238 A — Exponential or Quadratic English · 한국어 · [日本語] 2^N > N^2かどうかを判定します。べき乗を実際に計算する必要はありません。N = 1では不等式が成り立ち、N = 2, 3, 4では成り立ちません（2^4 = 4^2）。N = 5以降では常に成り立ちます。あるN >= 5で2^N ...

問題: BOJ 2482 — 色環 · English · 한국어 円形に並んだ N 個の位置から、互いに隣り合わないように K 個を選びます。先頭と末尾の位置も隣り合うものとして扱います。長さ L の直線から互いに隣り合わない k 個を選ぶ方法数を line(L, k) とすると、選んだ位置の間には少なくとも1つの未選択位置が必要なので、次の式になります。 line(L, k) = C...

問題: BOJ 1005 — ACM Craft · English · 한국어 各規則 A B は、建物 A の完成後に建物 B を建設できることを表します。規則を有向辺として表すと、有向非巡回グラフになります。トポロジカル順に処理すれば、各建物を扱う時点で先行する建物はすべて処理済みです。 finish[v] を建物 v の最早完成時刻とします。先行建物 p に対する漸化式は fin...

問題: BOJ 1305 — 広告 · English · 한국어 長さ L の広告文が与えられます。この文字列全体が先頭に現れるように無限に繰り返せる、最短の文字列の長さを求めます。KMPの接頭辞関数 pi を計算します。pi[i] は s[0..i] の proper prefix（文字列全体ではない接頭辞）であり、同時に suffix でもある文字列のうち、最長のものの長さです。した...

問題: BOJ 2213 — 木の独立集合 · English · 한국어 頂点 1 を根として木を根付き木にします。各頂点 v について、in[v] は v を含む v の部分木の独立集合の最大重み、out[v] は v を含まない場合の最大重みです。頂点の正の重みを w[v] とすると、次のようになります。 in[v] = w[v] + sum(out[child]): v を...

問題: BOJ 1949 — 優秀な村 · English · 한국어 各村には人口が与えられます。隣接する村を同時に選ばないという条件のもとで、選んだ村の人口合計を最大化します。入力は N、各村の人口 N 個、そして双方向の道路 N - 1 本です。 村1を根として、木を反復処理でたどります。訪問順を保存し、その逆順で処理すれば、再帰を使わずに子から親の順で計算できます。そのため、長い...

問題: BOJ 5670 — 携帯電話のキーパッド · English · 한국어 単語を入力するとき、最初の文字は必ず入力します。それ以降の文字は、入力済みの接頭辞に対応するトライのノードに子が2つ以上ある場合、またはその接頭辞自体が単語として完成している場合にのみ入力します。ある単語が別の単語の接頭辞なら、両者を区別するためにその単語の末尾の後でもう1文字入力する必要があります。 ト...

問題: BOJ 2533 — 社会網サービス(SNS) English · 한국어 解法 頂点 0 を根として、反復処理で根優先の順序を作ります。この順序を逆順に処理すると、すべての子を先に計算できるため、再帰呼び出しは不要です。そのため、最大 10^6 頂点の一本鎖の木でも呼び出しスタックがあふれません。 各頂点 u について、notAdopter[u] は u がアーリーアダプタ...

問題: BOJ 10266 — 時計の写真 · English · 한국어 時計の角度位置は 0 から 359999 までの 360000 個で、各位置の単位は 1/1000 度です。各写真を長さ 360000 の Boolean 配列で表し、時計の針がある位置だけを true にします。同じ位置に針が複数あっても、この表現と照合方法で問題ありません。 一方の写真を回転してもう一方と重ね...

問題: AtCoder ABC 237 E — Skiing · English · 한국어 頂点 1 から頂点 v までの経路で、登った高さの合計を U、下った高さの合計を D とします。この経路での幸福度の変化は D - 2U です。1 だけ下ると幸福度が 1 増え、1 だけ登ると 2 減るためです。経路全体の高さの変化は H[v] - H[1] = U - D なので、D = U +...

問題: AtCoder ABC 237 D — LR insertion · English · 한국어 最大 500,000 個のノードを再帰で中順巡回すると、呼び出しスタックがあふれる可能性があります。代わりに、両端キュー（deque）で答えを直接構築します。まず N を入れ、S を右から左へ処理します。各インデックス i について、S[i] が L なら i を deque の末尾に...

問題: AtCoder ABC 237 C — kasaka English · 한국어 · [日本語] 操作でできるのは文字列の先頭に a を追加することだけなので、末尾の文字は変えられません。先頭に連続する a の個数を leadingA、末尾に連続する a の個数を trailingA とします。leadingA > trailingA なら、先頭にある a と対応する末尾の ...

問題: AtCoder ABC 237 B — 行列の転置 · English · 한국어 H 行 W 列の行列 A が与えられるので、その転置行列 B を出力します。転置後の行列は W 行 H 列で、各要素の行番号と列番号を入れ替えます。つまり、すべての 0 <= i < H、0 <= j < W について B[j][i] = A[i][j] とします。正方行列と...

問題: AtCoder ABC 237 A — Not Overflow English · 한국어 · [日本語] 入力値は32ビット符号付き整数の範囲を超える可能性があるため、longとして読み込みます。32ビット符号付き整数の範囲はInteger.MIN_VALUE（-2^31）からInteger.MAX_VALUE（2^31 - 1）までで、両端を含みます。longで読み込んだ値を...

問題: BOJ 1786 — 見つける · English · 한국어 文字列 T の中にパターン P が現れるすべての位置を求めます。KMPでは不一致が起きても、比較済みの T の部分を再び走査しません。問題の制約ではパターンは空ではありませんが、以下の検索関数も空パターンの場合はインデックス参照をせず、結果なしとして扱います。 接頭辞関数と検索 pi[i] は P[0..i] の ...

問題: BOJ 4354 — 文字列のべき乗 English · 한국어 · 日本語 接頭辞関数と周期の候補 長さLの各入力文字列sについて、接頭辞関数piを計算します。pi[i]はs[0..i]の接尾辞でもある最長の真の接頭辞の長さです。最後の値pi[L - 1]は、文字列全体で最長のボーダー（接頭辞かつ接尾辞）の長さを表します。このボーダーを除いた長さp = L - pi[L - ...

問題: BOJ 14725 — アリの巣 · English · 한국어 各入力行は、アリの巣のルートから始まる1つの経路です。各トークンをトライに挿入すると、すでに存在する接頭辞は共有されます。ノードの子は、その接頭辞の次に続く食べ物です。TreeMap は子を辞書順に保持するため、深さ優先探索では事前に子をソートしたりコピーしたりせずに、兄弟ノードを必要な順序で訪問できます。 探索で...

問題: BOJ 14425 — 文字列集合 · English · 한국어 N個の文字列を保存し、M個の文字列を確認します。確認する文字列のうち、保存した文字列に含まれるものがいくつあるか数えます。すべての文字列は英小文字のみで構成されます。 ハッシュセット 入力文字列をHashSet<String>に保存します。同じ文字列を複数回挿入してもセットの内容は変わらないため、保...

BOJ 2470: 二つの溶液 · English · 한국어 異なる2つの溶液を選び、和の絶対値を最小にします。値をソートし、両端にポインターを置きます。各ステップでポインターが指す異なる2要素の和を候補として調べ、これまでの最小絶対値より小さければインデックスを保存します。和が負なら和を大きくするため左ポインターを右へ進め、正なら和を小さくするため右ポインターを左へ進めます。和が0にな...

問題: BOJ 1450 — ナップサック問題 ミート・イン・ザ・ミドル N = 30 のとき、すべての部分集合を列挙すると O(2^N) の時間がかかります。そこで品物を二つのグループに分け、それぞれの部分集合の合計を列挙します。各リストの要素数は最大 2^(N/2) です。右側の合計をソートし、左側の各合計 s に対して C - s より大きい最初の右側合計の位置を二分探索します。そ...

問題: BOJ 3273 — 2つの数の和 N個の互いに異なる正の整数と目標値Xが与えられます（1 ≤ N ≤ 100,000、各数は最大1,000,000）。和がXになる、異なる2つの入力要素からなる順序を区別しないペアの数を求めます。 ソートとツーポインタ 数をソートし、未確認の範囲の最小値と最大値に2つのポインタを置きます。2つの数の和がXより小さい場合、左の数は残りのどの数と組...

問題: BOJ 1806 — 部分和 すべての数が正なので、右端の排他的境界を右へ動かすと区間和は増加し、左端を右へ動かすと区間和は減少します。排他的な右端を1つずつ拡張し、合計が S 以上になったらその区間を答えの候補として記録します。その後、合計が S 以上である間は左端を進めます。同じ位置で終わるより長い区間が答えをより小さくすることはありません。区間は [left, right) ...

問題: BOJ 1094 — 棒 English · 한국어 目標の長さは1から64です。最初の棒の長さは64で、棒を半分ずつ切ると作れる棒の長さは64、32、16、8、4、2、1のような2のべき乗になります。 目標の長さを2進数で表すと、立っているビットに対応する異なる2のべき乗の和になります。選んだ各サイズの棒はそれぞれ1本ずつ必要です。例えば23 = 16 + 4 + 2 + 1な...

問題: BOJ 2252 — 列を並べる 入力される各組 A B は、学生 A が学生 B より前に並ぶ必要があることを表します。この条件を有向辺 A -> B として表します。有効な列はトポロジカル順序であり、すべての辺で始点が終点より前に並びます。順序関係のない学生同士はどちらが先でもよいため、答えは一意な順序ではなく、条件を満たす順序の1つです。 カーンのアルゴリズムでは、入...

問題: BOJ 1311 — 仕事の割り当て N人にN個の仕事を1つずつ割り当てます。それぞれの仕事をちょうど1回使い、割り当てコストの合計を最小化します。 ビットマスク動的計画法 dp[mask]を、maskでビットが立っている仕事を最初のInteger.bitCount(mask)人に割り当てたときの最小コストと定義します。次に割り当てる人のインデックスはInteger.bitCo...

問題: BOJ 11049 — 行列積の順序 · English · 한국어 区間動的計画法 dp[i][j] を、行列 i から j までを順番に掛け合わせるために必要なスカラー乗算回数の最小値とします。行列が1つだけなら乗算は不要なので、dp[i][i] = 0 です。複数の行列からなる区間では、最後に掛け合わせる境界 k を選びます。まず左の区間 i..k と右の区間 k+1..j...

問題: BOJ 1644 — 連続する素数の和 エラトステネスのふるいとスライディングウィンドウ まずエラトステネスのふるいで N 以下の素数をすべて求めます。次に、添字 left から right までの連続する素数の区間と、その合計を管理します。合計が N より小さい間は右端を伸ばします。合計が N 以上になったら、等しい場合は答えに加え、最も左の素数を区間から取り除きます。素数はす...

ビットマスク 集合に含まれる整数は 1 から 20 までなので、1つの int で各要素の有無を表せます。値 x をビット位置 x - 1 に対応させます。1 << (x - 1) はそのビットだけが1のマスクを作ります。シフト位置は0から始まるため、値から1を引きます。全要素を表すマスク (1 << 20) - 1 は下位20ビットがすべて 1 で、0 は空集合で...

問題: BOJ 2150 — Strongly Connected Component 反復型コサラジュ法 コサラジュ法は2回の深さ優先探索で強連結成分（SCC）を求めます。この実装では再帰呼び出しの代わりに明示的な整数スタックを使うため、頂点数10,000の長い経路でもJavaの呼び出しスタックを使い切りません。 1回目の探索は元のグラフで行います。各スタックフレームに頂点と次に調べ...

問題: BOJ 15681 — 木とクエリ · English · 한국어 反復による根付けと逆順の集計 無向木を R を根として探索します。スタックを使った走査で各頂点の親を記録し、訪問順を order 配列に保存します。頂点は親から発見されたときだけスタックに追加し、現在の頂点から親へ戻る辺は無視します。そのため各頂点はスタックに一度だけ入り、順序配列にも一度だけ記録されます。親は子...

問題: BOJ 17472 — 橋の建設 2 English · 한국어 方針 連結した陸地の各まとまりを、グラフの頂点として扱います。まずフラッドフィルで島ごとに番号を付けます。次にすべての行と列を調べます。各島のマスから一方向へ水上を進み、次の陸地または地図の端まで確認します。異なる島に到達し、間の水マスが2個以上の場合だけ橋の候補になります。この処理で横・縦の両方向をすべて調べら...

問題: BOJ 2887 — 惑星トンネル クラスカル法のための疎な候補辺 惑星 u と v を結ぶトンネルの費用は min(|x[u] - x[v]|, |y[u] - y[v]|, |z[u] - z[v]|) です。すべての惑星ペアを辺にすると N(N - 1) / 2 本になり、N が大きい場合には効率的ではありません。そこで、各座標軸ごとに惑星をソートし、その順序で隣り合うペア...

問題リンク · English · 한국어 クラスカル法 全域木は、すべての頂点を閉路なしで連結する木です。最小全域木（MST）は、全域木のうち辺の重みの合計が最小のものです。クラスカル法では、辺を重みの昇順に並べ、両端点が異なる連結成分に属するときだけ辺を採用します。端点がすでに連結されているかどうかの判定と、成分の併合には素集合データ構造（DSU）を使います。 この貪欲な選択は安全...

問題リンク · English · 한국어 DVD の順列を扱う反復型セグメント木 配列は最初 0, 1, ..., N - 1 の順列です。タイプ0の操作では2つの位置の値を交換し、タイプ1の操作では現在の区間 [A, B] に番号 A から B までの DVD がちょうど含まれるかを調べます。 配列が順列であるため、この条件は min(A..B) == A かつ max(A..B)...

問題: BOJ 1168 — ヨセフス問題 2 1番からN番まで番号の付いた人が円形に並んでいます。次の人から数えてK番目の人を順に取り除き、取り除いた順序を<a, b, ...>の形式で出力します。 生存者数を管理するFenwick tree 各位置には、その番号の人がまだ円にいれば1、取り除かれていれば0を保持します。Fenwick treeの接頭辞和から、その位置まで...

固定された値域 [1, 2_000_000] に挿入された値の多重集合を、フェニック木で管理します。tree[i] には最下位ビット i & -i によって定まる区間の頻度の合計を格納します。値を挿入するときはその頻度に 1 を加え、指定された順位の値を見つけて削除するときは 1 を引くため、同じ値も別々の要素として数えられます。 k 番目に小さい値を選ぶには、フェニック木の二分探...

BOJ 2618: 警察車両 2台の警察車両が最後に担当した事件による動的計画法 dp[a][b] を、警察車両1が最後に担当した事件番号が a、警察車両2が最後に担当した事件番号が b のとき、残りの事件をすべて担当する最小移動距離とします。0 はまだ事件を担当していないことを表します。そのため a = 0 の車両1の位置は (1, 1)、b = 0 の車両2の位置は (N, N) で...

BOJ 16975: 数列とクエリ 21 Fenwick Tree と差分配列による区間加算 初期値は基底配列に保持し、その後の加算は差分配列で表します。1-based で両端を含む区間 [left, right] のすべての位置に x を加えると、差分配列で変わるのは2か所だけです。left に x、right + 1 に -x を加えます。したがって差分配列の i までの累積和は位置...

問題: AtCoder ABC 235 D — Multiply and Rotate · English · 한국어 整数 1 から始め、次のいずれかの操作を行います。現在の整数に A を掛けるか、最後の10進数字を先頭に移します。回転操作は、2桁以上で末尾の数字が0ではない場合だけ行えます。N に到達するための最小操作回数を求め、到達できなければ -1 を出力します。たとえば 120 ...

問題: AtCoder ABC 235 C — The Kth Time Query · English · 한국어 各クエリ (x, k) について、配列内で x が k 回目に現れる位置（1 始まり）を求めます。x の出現回数が k 未満なら -1 を出力します。 値から出現位置のリストへのマップを作ります。配列を左から順に走査し、その値のリストに i + 1 を追加します。位置は昇...

問題: AtCoder ABC 235 B — Climbing Takahashi English · 한국어 各地点の高さは、進む順に並んでいます。高橋は最初の地点から出発し、次の地点の高さが現在の地点より厳密に高い場合にだけ進み続けます。初めて同じ高さまたは低い高さの地点に来たら、その地点には到着せずに止まります。求めるのは最後に到着した地点の高さです。 答えを最初の高さで初期化し...

問題: AtCoder ABC 235 A — Rotate · English · 한국어 3桁の十進整数が与えられます。百の位から順に A、B、C とすると、左に1桁ずつ回転してできる3つの数 ABC、BCA、CAB の合計を求めます。回転とは3つの数字の順番を入れ替えることなので、同じ数字が複数あったり 0 が含まれたりしても、そのまま同じ方法で扱えます。たとえば入力が 123 なら...

問題: BOJ 11780 — フロイド 2 正のコストを持つ有向グラフについて、すべての都市の順序対間の最小コストと、その最小経路を1つ求めます。同じ向きに複数の辺がある場合は、最も安い辺だけを保持すれば十分です。対角成分は、都市から自分自身への空の経路を表す0で初期化します。 次の都市の行列を使うフロイド–ワーシャル法 distance[i][j] は、i から j までに見つかっ...

問題: BOJ 11779 — 最小費用の求め 2 辺の重みが非負の有向グラフで、指定された始点から終点までの最小費用と、その費用を実現する経路を一つ求めます。各有向辺は隣接リストに格納します。平行辺も有効であり、特別な処理をせずすべて保持できます。 ダイクストラ法 distance[v] は始点から v までに見つかった最小費用、parent[v] はその距離を最後に更新した経路での...

解法 0から9999までの整数をそれぞれグラフの頂点として扱います。DSLRの4つの命令は、現在の値からその命令を適用した値へ向かう辺です。すべての命令のコストは1なので、幅優先探索（BFS）は開始状態からの命令数が少ない状態から順に探索します。 各状態からの遷移先をD、S、L、Rの順に訪問します。BFSは最短経路を先に見つけ、同じ長さの経路はこの命令の優先順位に従って探索します。状態を...

問題リンク スビンの位置を x とすると、範囲 [0, 100000] 内での移動先は x - 1、x + 1、2 * x です。各移動のコストは1秒なので、幅優先探索（BFS）は開始位置からの移動回数が少ない位置から訪問します。位置を初めて発見したときの距離が最小であり、その位置を発見した直前の位置を親として記録すれば最短経路も保存できます。 開始位置を距離0として一度だけキューに入れ...

問題 dp[i][j] を、文字列 a の先頭 i 文字と文字列 b の先頭 j 文字の最長共通部分列の長さとします。空の接頭辞とのLCSの長さは0です。両方の接頭辞の末尾文字が一致する場合、その文字を1つ前の接頭辞同士のLCSに追加できます。一致しない場合は、末尾文字の少なくとも一方を使わない必要があります。 dp[0][j] = dp[i][0] = 0 dp[i][j] = dp...

BOJ 14003: 最長増加部分列 5 解法 各入力値について、tails[length] には長さ length + 1 の増加部分列が取り得る最小の末尾値を保存し、tailIndices[length] にはその末尾値を持つ入力インデックスを保存します。現在の値以上となる最初の末尾値を二分探索（lower_bound）し、現在の値で置き換えます。tails の値だけでは実際の部分列...

問題リンク 各入力値について、tails[length] にその長さの増加部分列が取り得る最小の末尾値を保持し、その末尾値を与えた入力インデックスも保存します。現在の値以上となる最初の末尾値（lower_bound）を二分探索し、その位置を現在の値で置き換えます。tails 配列そのものが実際の部分列とは限りません。実際の列を復元するためにインデックスを記録します。 最初の末尾値 >...

解法 dp[x] を x を 1 にするために必要な最小操作回数とします。x に対して最後に行える操作は、1 を引く、2 で割り切れる場合に 2 で割る、3 で割り切れる場合に 3 で割る、のいずれかです。したがって、2 から N まで順に各 x について、有効な遷移先の dp の最小値に 1 を加えます。遷移先はすべて x より小さいため、すでに計算済みです。 最小値を与えた遷移先を各...

問題リンク 中間順ではノードが左・右の部分木の間に置かれ、後行順では各部分木の最後の値がその根になります。そのため、現在処理している 2 つの範囲では、後行順の最後の値が部分木の根です。値から中間順のインデックスを引く表を使えば、分割位置を定数時間で見つけられます。その位置より左にあるノード数で左部分木の大きさが決まり、残りの先頭側の後行順範囲が右部分木に対応します。 再帰呼び出しの代わ...

問題リンク i < j かつ A[i] > A[j] となる添字の組 (i, j) を転倒（inversion）と呼びます。バブルソートは、順序が逆になっている隣接要素を交換します。一度交換された組は正しい順序になり、再び交換されることはありません。すべての転倒が1回ずつ取り除かれるため、バブルソートの交換回数は転倒数と等しくなります。 マージソートを使えば、交換を実際に行わ...

問題リンク 各入力行にはノードとその左・右の子が記されています。ノード名は大文字 1 文字なので、label - 'A' を添字にした配列に子を保存します。子がない場合は . が入力され、その値を配列に残しておき、巡回時にこの値に出会ったらその枝を飛ばします。A から始め、先行順はノード-左-右、中間順は左-ノード-右、後行順は左-右-ノードの順で訪問します。それぞれの結果を別の文字列に蓄...

BOJ 1967: 木の直径 入力では無向辺がそれぞれ一度だけ与えられます。どちらの向きにも移動できるよう、各辺を両端の隣接リストに一度ずつ追加します。同じ向きの辺を重複して追加しないようにします。 木では、任意の2頂点を結ぶ単純路は一意であり、その路の長さが頂点間の距離です。任意の頂点 s から木全体を走査して各頂点までの距離を求め、最も遠い頂点を a とします。このようにして直径の端...

問題リンク 辺の重みが非負の木では、任意の頂点から最も遠い頂点 a を見つけ、次に a から最も遠い頂点を探すと、2回目の探索で得られる距離が木の直径です。任意の始点から最も遠い頂点は直径の端点になります。直径の経路と始点から伸びる経路を考えると、木では経路が一意で重みが非負であるため、直径の端点の少なくとも一方は始点から同じだけ以上遠く、そこから再度探索すれば直径のもう一方の端点に到達し...

BOJ 5639: 二分探索木 先行順巡回からBSTを構築する 入力は、異なるキーを持つ二分探索木の先行順巡回結果です。先行順巡回では、ノードはすべての子孫より先に現れます。ルートから直近に訪問したノードまでの経路をスタックに保持します。スタックの先頭が現在の挿入位置です。次のキーが先頭のキーより小さければ、そのノードの左の子です。そうでなければ、新しいキーより小さい祖先をスタックから取...

BOJ 2357: 最小値と最大値 反復型セグメントツリー 入力値は2つのフラットな配列のそれぞれで、葉 n + i に格納します。各内部ノードは2つの子をマージします。最小値ツリーには min(left, right)、最大値ツリーには max(left, right) を格納します。このマージ演算は結合的なので、区間を重ならない複数のツリー区間に分割し、その結果を任意の順序で結合でき...

BOJ 11725: 木の親を探す 探索で木に根を設定する 入力された無向辺を隣接リストに格納し、頂点 1 を根とします。幅優先探索のキューに 1 を入れて探索すると、現在の頂点から初めて発見した隣接頂点は現在の頂点の子です。この関係は隣接頂点をキューから取り出すときではなく、キューに追加するときに記録します。発見と同時に訪問済みにすることで、別の辺が同じ頂点の親を再設定することを防ぎま...

問題リンク 辺を入力順に処理します。辺 (a, b) を追加する前に、それまでに追加した辺からなるグラフで、両端点が属する連結成分の代表元を調べます。代表元が同じなら、すでに a と b を結ぶ経路があるため、この辺を追加するとサイクルができます。その時点のターンを1から数えてすぐに出力します。代表元が異なる場合は、2つの連結成分を併合します。経路ですでにつながっている頂点同士を結ぶ辺を加...

問題リンク 回文テーブルを事前計算してからバックトラック palindrome[left][right] を、両端のインデックスを含む部分文字列 s[left..right] が回文かどうかを表す値とする。両端の文字が一致し、長さが 2 以下であるか、内側の部分文字列も回文であれば、その部分文字列は回文である。 palindrome[left][right] = (s.charAt...

解法 各人の名前を親の名前に対応させ、各ルートにはコンポーネントのサイズを保存します。初めて登場した名前は自身をルートとし、サイズを 1 にします。友人関係を読み込んだら両者のルートを探し、小さいコンポーネントを大きいコンポーネントの下に結び、残るルートのサイズを合算します。すでに同じルートなら構造を変更せず、そのルートの現在のサイズを出力します。テストケースごとに新しい素集合データ構造を...

問題 都市を頂点、道路を無向辺と考えます。旅行計画に含まれるすべての都市が同じ連結成分に属するとき、そしてそのときに限り旅行できます。その場合、計画内で隣り合う都市の間に経路があり、それらの経路をつなげて移動できます。したがって、都市が1つだけの計画は常に可能です。 素集合データ構造（DSU）を使います。最初は各都市がそれぞれ別の集合です。隣接行列で値が 1 のすべての組について都市を併...

問題 隣り合う2つのファイルを結合するコストは、2つのファイルサイズの合計です。結合後も順序は保たれるため、最後の結合位置で最適な手順を分割できます。まず [i, k] のファイルを1つにまとめ、次に [k + 1, j] を1つにまとめてから、その2つを結合します。最後の結合コストは区間 [i, j] の合計サイズです。 dp[i][j] を0始まりの添字で i 番目から j 番目まで...

問題リンク dist[u][v] を、頂点 u から頂点 v への有向最短距離とします。すべての値を無限大に初期化し、dist[i][i] は 0 にします。同じ始点と終点を持つ直接辺が複数ある場合は、最小の重みを記録します。対角成分の 0 は Floyd–Warshall で空の経路を表し、頂点自身へ向かう直接辺はサイクル候補の計算用に別の辺行列へ保存します。 Floyd–Warsha...

解法 best[v][c] は、合計費用 c 以下で空港 v に到着する最小時間を表します。開始地点には費用をかけずに到達できるため、すべての費用上限について best[0][c] = 0 とし、その他は無限大に初期化します。チケットの新しい費用が M 以下の場合だけ緩和します。ある費用上限でより良い時間が見つかったら、それより大きい費用上限にも伝播させます。使える予算が増えても最小時間は...

問題リンク dist[i][j] を、都市 i から都市 j までの既知の最短運賃とします。初期状態では、同じ都市にとどまる経路のコスト 0 と、直接結ばれたバス路線だけが分かっています。同じ出発地と到着地を結ぶ路線が複数ある場合は、最も安い運賃だけを残します。 各都市 k を中間地点として順に考えます。k を処理する前の dist[i][j] には、すでに処理した都市だけを中間地点とし...

問題リンク 次数による判定 信頼関係 [a, b] を、人 a から人 b への有向辺として考える。町の判事は誰も信頼しないため、出次数は 0 である。また、それ以外の全員が判事を信頼するため、入次数は n - 1 となる。両方の条件を確認する必要がある。入次数だけで判定すると、ほかの人を信頼している人を誤って判事に選ぶ可能性がある。 全員の入次数と出次数を数え、両方の条件を満たす...

解法 この問題は有向グラフで負の重みを持つ辺があるため、ダイクストラ法は使えません。ベルマン–フォード法では、頂点1から各頂点までの既知の最短距離を保持し、すべての辺を最大 V - 1 回緩和します。負閉路を含まない最短路は高々 V - 1 本の辺で構成されるため、ある反復で距離が変化しなければ早期終了できます。 距離配列は本当の long の無限大値で初期化し、頂点1だけを0にします。...

問題リンク 解法 各テストケースで、始点 s と指定された辺の両端 g、h を始点としてダイクストラ法を実行します。候補頂点 x が答えになるのは、s から x への最短経路の中に指定された辺 g-h を通るものが存在する場合です。したがって最短距離は、次のどちらかの経路長と一致します。 dist(s, g) + w(g, h) + dist(h, x) dist(s, h)...

問題リンク 区間動的計画法 配列の両端に値 1 の仮想風船を追加する。dp[l][r] を、両端の境界風船 l、r は割らずに、その間にある風船をすべて割って得られる最大コイン数とする。 開区間で最後に割る風船 k を選ぶ。その時点では区間内のほかの風船はすべて取り除かれているため、k の隣にはちょうど l と r が残る。最後に得るコインは values[l] * values[...

問題ページ 解法 正の重みを持つ無向グラフで、頂点v1とv2の両方を通る最短経路を求めます。必須の2頂点を訪れる順序は1 → v1 → v2 → Nまたは1 → v2 → v1 → Nの2通りだけです。それぞれの区間の最短距離を足した2つの候補から小さい方を選び、どちらの候補も到達不能なら-1を出力します。 始点1、v1、v2からそれぞれダイクストラ法を実行します。1つ目の順序の距離は...

問題 配列の1要素を更新しながら、任意の閉区間の積を 1,000,000,007 で割った余りとして求めます。更新で変化するのは1か所だけなので、反復型セグメント木ではその葉と祖先だけを再計算します。各内部ノードには、2つの子の積を MOD で割った値を格納します。 n 個の葉を [n, 2n) に置きます。位置 p を更新するときは葉 p + n を新しい値で置き換え、親へ上がりながら...

解法 有向グラフなので、各辺は始点の隣接リストだけに格納します。すべての辺の重みが非負であるため、ダイクストラ法を使えます。距離配列には始点から各頂点までの既知の最短距離を保存します。優先度付きキューから暫定距離が最小の要素を取り出して、その頂点から出る辺を緩和すると、隣接頂点までの距離を短縮できます。より短い経路が見つかった場合は新しい要素をキューに追加し、後で距離配列と一致しなくなった...

問題リンク 解法 コンピューターを頂点、コンピューター間の直接接続を辺と考えると、無向グラフとして表せます。computers[i][j] === 1 は、コンピューター i と j が直接接続されていることを示します。求めるネットワーク数は、このグラフの連結成分数です。 すべてのコンピューターを順に調べ、未訪問のものを見つけるたびにネットワーク数を 1 増やします。そのコンピューター...

各テストグラフの頂点を2色で塗り分けます。すべての辺が異なる色の頂点同士を結ぶ場合に限り、そのグラフは二部グラフです。グラフが非連結の場合もあるため、まだ色が付いていない頂点すべてから幅優先探索を開始します。探索中に新しく見つけた隣接頂点には、現在の頂点と反対の色を割り当てます。同じ色の頂点同士を結ぶ辺が見つかった場合は二部グラフではありません。この方法で自己ループも検出できます。 不変条...

問題リンク 各テストケースについて、L × L のチェス盤で開始マスから目標マスまでナイトが移動する最小回数を求めます。1回の移動では、一方の座標が1、もう一方の座標が2変化し、それぞれの符号は異なる場合があります。ナイトは盤の外へは移動できません。 盤上の各マスをグラフの頂点、合法なナイトの移動を辺として考えます。すべての辺のコストは等しいため、幅優先探索（BFS）は開始地点からの距離...

問題リンク 方針 候補をソートし、インデックスを使って深さ優先探索します。各再帰呼び出しでは現在より後ろのインデックス（i + 1）だけを選ぶため、配列中の各要素は最大1回しか使えません。異なるインデックスにある同じ値は、それぞれ別の要素として利用できます。 同じ探索階層で直前の候補と値が同じなら、その候補をスキップします。これにより同じ値から始まる同一の組み合わせを重複して探索せ...

問題リンク r = L / 2 とします。経過時間 E における観覧車の回転角は、周期 T を使って theta = 2π * (E mod T) / T ラジアンと表せます。E が T を超える場合も、E mod T によって角度を1周分の範囲に収められます。 車輪の最下点の高さを0とすると、回転する垂直面内での乗客の座標は y = -r sin(theta)、z = r(1 - co...

問題リンク dp[x] を合計 x を作るために必要なコインの最小枚数とします。dp[0] = 0 とし、正の金額では最後に使ったコインが 3 種類の額面 A、B、C のいずれかです。したがって、次の漸化式になります。 dp[x] = min(dp[x - coin] + 1)（各額面 coin <= x について） 金額を小さい順に処理することで、dp[x - coin] はす...

問題リンク 一列に並んだ N 個の位置から、互いに隣り合わないように k 個を選ぶ方法の数を、k = 1 から N までそれぞれ求めます。各答えを 1,000,000,007 で割った余りを出力します。 選んだ位置を x_1 < x_2 < ... < x_k とします。連続する選択位置は隣り合えないため、x_(i+1) >= x_i + 2 が成り立ちます。i ...

問題リンク N 個の整数を含む 2 つの配列が与えられます。1 つ目の配列の各要素を 2 つ目の配列の要素 1 つと組み合わせ、絶対差の合計を最小化します。 両方の配列を昇順に並べ、同じ添字の要素同士を組にすると最小値になります。x <= y かつ u <= v である 2 つずつの値を考えます。同じ順序で組にする費用は |x - u| + |y - v|、交差して組にする費...

問題リンク 頂点 i の答えは、頂点1から i までの最短距離と、i から頂点 N までの最短距離の和です。グラフは無向なので、後者は N から i までの最短距離と等しくなります。頂点1を始点に一度、頂点 N を始点に一度ダイクストラ法を実行し、各頂点について二つの距離を足します。 各辺は隣接リストに格納します。辺の重みがすべて非負であるため、ダイクストラ法を使えます。負の重みがある場...

問題リンク 最初、すべてのマスは白です。マスを赤く塗る操作、または2つのマスを指定するクエリが与えられます。2つのマスがどちらも赤く、赤いマスだけを上下左右に移動して互いに到達できる場合は Yes、そうでなければ No を出力します。 各マスを素集合データ構造（DSU）の要素として扱い、赤く塗られたマスを示す red 配列を別に管理します。マスを塗る際、まだ赤くなければ赤として有効化し、...

問題リンク 各仕事には締切 D、所要時間 C、報酬 S が与えられます。仕事を締切の昇順に並べ、その順に処理します。dp[t] を、時刻 t までに終了するスケジュールの最大報酬とします。 各仕事を選ぶ場合を考え、t を D から C まで降順に走査して dp[t] = max(dp[t], dp[t - C] + S) と更新します。仕事は締切順に並べて実行できます。順序が逆になってい...

問題リンク N 人の生徒それぞれのクラスと得点が与えられます。各クエリで指定された両端を含む区間 [L, R] について、1 組と 2 組それぞれの得点合計を出力します。 クラスごとに累積和配列を 2 つ用意します。classOne[i] は生徒 1 番から i 番までの 1 組の得点合計、classTwo[i] は同じ区間の 2 組の得点合計です。各生徒のクラスに対応する配列だけに得点...

問題リンク 各点を基準点とし、その点から他のすべての点へ向かう方向を考えます。2つの方向を選ぶと基準点に角ができるため、すべての方向の組について小さい方の角を求め、その最大値を答えにします。 方向の角度を度数法の [0, 360) に正規化してソートし、ソート済み配列を複製してコピー側の各角度に 360 を加えます。m = N - 1 とすると、各方向について後続する m - 1 個の要...

文字列 S が与えられたとき、atcoder と等しい部分列の個数を数えます。部分列は、残す文字の順序を変えずに 0 個以上の文字を削除して作ります。選んだ位置が異なるものは別の部分列として数えます。 dp[j] を、これまでに処理した文字から atcoder の先頭 j 文字を作る方法の数とします。初期状態の dp[0] = 1 は空の接頭辞を作る 1 通りを表し、それ以外はすべて 0 ...

問題リンク 各クラスのレーティングが与えられます。各クエリについて、クエリの値と最も近いレーティングとの差の絶対値を出力します。まずレーティングを一度だけ昇順にソートし、各クエリでは二分探索で挿入位置を求めます。 挿入位置の直前と直後のレーティングだけを比較すれば十分です。挿入位置より前の値はすべて直前の値以下なので、それより近くなることはありません。後ろ側も同様に、直後の値より近くなる...

問題リンク S の文字の順序を保ったままちょうど K 文字を選び、辞書順で最小の部分列を作ります。 ちょうど N - K 文字を削除できます。S を左から走査し、選んだ文字をスタックに保持します。現在の文字がスタック末尾の文字より小さく、まだ削除できる文字数が残っている間は、末尾の文字を削除します。これは辞書順に関する交換です。前の位置にある大きい文字を現在の小さい文字に置き換えると結果...

問題リンク 許可された数字だけを使い、値が B で割り切れる長さ N の数字列の個数を求めます。先頭の桁は 0 でも構いません。状態は B で割った余りです。余り r の状態に数字 d を追加すると、余りは (10r + d) % B になります。 T[next][current] を、余り current から next に遷移させる許可数字の個数と定義します。つまり T[next][...

問題リンク 各マスについて、そのマスと同じ行および列にある値の合計を出力します。各行の合計と各列の合計を一度ずつ計算し、それらを使ってすべてのマスの答えを求めます。対象のマス自身は行の合計と列の合計の両方に含まれるため、一度引いて重複分を取り除きます。 rowSum[i] + colSum[j] - grid[i][j] 合計が int の範囲を超えても正しく扱えるよう、値と合計には ...

問題リンク この問題では、木の中の経路に含まれる町の数の最大値を求めます。木では任意の2頂点間の経路が一意に定まり、そのような経路のうち最長のものを木の直径と呼びます。 2回の探索で直径を求めます。任意の頂点から木を探索して最も遠い端点 u を見つけ、次に u から探索します。u から最も遠い頂点は直径のもう一方の端点なので、2回目の探索で得られる最大距離が、辺の本数で表した直径の長さで...

括弧列を左から順に作ります。どの接頭辞でも、閉じ括弧の数が開き括弧の数を超えてはいけません。そうなると、その後に何を追加しても正しい括弧列にはできません。また、長さ N の正しい括弧列には、開き括弧がちょうど N/2 個含まれます。 したがって、開き括弧を N/2 個より少なく使っている場合に ( を追加し、close < open の場合に限って ) を追加します。接頭辞で両者の数...

長さ L のようかんと、切ることのできる位置 N 個が与えられます。そのうちちょうど K 個を選んでようかんを K + 1 個のピースに分け、最も短いピースの長さを最大化します。 最小長の候補 d に対し、切断可能な位置を左から順に調べます。前回の切断位置（最初は 0）からの距離が d 以上になったら切断し、K 回切断した時点で探索を終了します。各切断位置を可能な限り左に置くことで、その後...

素集合データ構造（DSU）は、0からnまでの整数を複数の集合に分けて管理します。各集合は根で表され、find(x)は要素xが属する集合の代表元を返します。併合操作は2つの集合を1つにまとめ、連結性の問い合わせでは2つの要素の代表元が同じかを調べます。 parent配列は森を構成します。自分自身を親として指す要素が根であり、同じ集合の各要素は親リンクをたどって代表元に到達します。findは反...

問題リンク 互いに異なる正の整数 candidates と目標値が与えられる。合計が目標値になるすべての一意な組み合わせを返す。各候補は何度でも使用できる。 候補をソートしてから、深さ優先のバックトラッキングを行う。ヘルパー関数には開始インデックスと残りの合計を渡す。再帰呼び出しでは選んだ候補のインデックスから次の選択を始めるため、同じ候補を再利用できる。また、より小さい値へ戻らない...

問題ページ 迷路は N × M の格子で、0 は通行可能なマス、1 は壁です。左上のマスから出発し、右下のマスに到達する経路に含まれるマス数の最小値を求めます。壁は最大1つまで壊せます。始点と終点も経路のマス数に含め、到達できない場合は -1 を出力します。 位置だけではBFSの状態を十分に表せません。同じマスに到着しても、壁を壊す権利が残っている状態と、すでに壁を壊した状態では、その後...

フェンウィック木（Binary Indexed Tree）は部分和を保持し、1点の更新と接頭辞和の取得をそれぞれO(log N)時間で行います。元の値は別の配列に保存します。1-based index iの値がoldからnewに変わったら、その差new - oldを木のindex iに加算します。 1-based index iに対して、i & -iは最下位のセットビットを取り出し...

解法 0から100000までの整数をそれぞれ状態として扱います。状態xからは、結果が許可された範囲内であれば、1回の移動でx - 1、x + 1、2 * xへ移動できます。すべての辺のコストは1なので、幅優先探索（BFS）は開始地点からの距離が小さい状態から順に訪問します。そのため、目標を初めて発見したときの移動回数が最短距離です。 距離配列は訪問済みかどうかの記録も兼ねています。-1は...

問題リンク 解法 各数値を10進数の文字列に変換し、a + b > b + a のとき a が b より前になるように並べ替えます。たとえば "330" > "303" なので、"3" は "30" より前になります。この順に連結すると、作れる最大の数になります。 この比較規則は交換論法で説明できます。連結結果の隣り合う文字列が a と b の場合、順序によって結果に加わる...

問題 解法 最初の項 "1" から始めます。次の項を作るには、現在の項を左から右へ走査し、同じ数字が連続する最大の区間を見つけ、その長さ、続いて数字を追加します。区間全体を処理してから次の位置へ進むため、各数字は一度だけエンコードされます。この変換を n - 1 回繰り返すと、求める項が得られます。 各ラウンド終了時の項の長さを L_k とします。項の処理にはその長さに比例する時間...

問題ページ トマトの箱は3次元の格子です。熟したトマトは、軸に沿った6方向に隣接する未熟なトマトを熟させます。この変化は1日ごとに同時に起こります。未熟なトマトがすべて熟すまでの日数を求め、熟すことのできないトマトが残る場合は -1 を出力します。 複数の始点を使う幅優先探索（BFS）を行います。探索を始める前に、最初から熟しているトマトをすべてキューに入れます。キューには各マスを平坦化...

有効な数独盤面には解が1つだけあります。各行・各列・3 × 3 のボックスに 1 から 9 までの数字がそれぞれ一度だけ現れるよう、空欄を盤面上で埋めます。 問題へのリンク アプローチ 各行・各列・各ボックスについて、すでに使われている数字を9ビットのマスクで記録します。ビット d は数字 d + 1 を表し、ビットが立っていればその数字は配置できません。したがって、空欄に置ける数...

問題へのリンク 9×9の数独盤面が有効かどうかを判定する。確認するのは埋まっているマスだけでよい。空マス（.）は無視し、現在の途中状態から数独を完成できるかどうかまでは判定しない。 各行・各列・各3×3ボックスで使用済みの数字を、それぞれ9個の整数ビットマスクに記録する。数字 d は 1 << (d - '1') のビットで表す。マス (r, c) が属するボックスのインデッ...

BOJ 1655: 真ん中の数を言おう これまでに読み込んだ値を二つの優先度付きキューに分けて保持する。lower は小さい側の半分を格納する最大ヒープ、upper は大きい側の半分を格納する最小ヒープである。次の二つの不変条件を保つ。 lower のすべての値は upper のすべての値以下である。 lower の要素数は upper と同じか、ちょうど一つ多い。 各入力...

問題リンク 配列はソート済みなので、二分探索を2回行って境界を求められる。1回目は値が target 以上となる最初のインデックスを探し、2回目は値が target より大きくなる最初のインデックスを探す。1回目の境界が配列の末尾、またはその位置の値が target でなければ、対象の値は存在しない。そうでなければ、1回目の境界と2回目の境界から1を引いたインデックスが答えとなる。...

問題リンク 解法 昇順に並んだ配列を回転させた入力が与えられ、値はすべて異なります。二分探索の各ステップでは、現在の区間の少なくとも片方の半分が整列しています。整列している半分の値の範囲に target が含まれるかを確認します。含まれていれば反対側の半分を捨て、含まれていなければ整列している半分を捨てます。これにより、target が配列に存在する場合は、必ず残りの区間に保たれます...

問題 解法 文字列を左から右へ走査し、各文字のインデックスを ArrayDeque<Integer> に格納します。スタックは、有効な部分文字列の直前の境界を表すセンチネルインデックス -1 から開始します。 開き括弧を見たら、そのインデックスをスタックに積みます。閉じ括弧を見たら、最も直近の未対応の開き括弧の位置（またはセンチネル）を取り出します。その結果スタックが空...

BOJ 11279: 最大ヒープ 最大ヒープでは、すべての親の値が子の値以上であるため、最大値は常に根にある。値を挿入するときは配列の末尾に追加し、親より大きい間、上へ移動させる。最大値を削除するときは最後の値を根に移し、より大きい子と交換しながら下へ移動させる。各操作で根から葉までの経路をたどるのは最大一度なので、挿入と削除の時間計算量はそれぞれO(log N)である。プリミティブ型の配...

問題リンク 配列の転倒数とは、i < j かつ A[i] > A[j] を満たす添字の組の数である。値が等しい組は転倒数に含めない。整列済みの ArrayList に各値を挿入する場合、二分探索で挿入位置は見つけられるが、挿入時の要素移動に毎回 O(N) かかるため、全体の時間計算量は O(N²) となる。 マージソートを使えば、O(N log N) 時間で転倒数を数えられる...

問題 解法 二分探索で下限（lower bound）、つまり target 以上となる最初の値のインデックスを求めます。半開区間 [left, right) を探索範囲として維持し、最初は配列の有効なインデックスをすべて含めます。各段階で、left より前の値はすべて target 未満であり、right 以降の値はすべて target 以上という不変条件を保ちます。中央の値が ta...

問題 解法 現在の順列より大きく、なおかつ可能な限り小さい順列を作るには、右から見て増加させられる最も右側の位置を変更します。右から左へ走査し、最初に nums[i] < nums[i + 1] を満たすインデックス i を探します。i より後ろの接尾部は非増加順です。そのようなインデックスがなければ、配列全体が非増加順で、すでに最大の順列です。配列を反転して最小の順序にします...

問題 解法 すべての単語の長さは等しく、0 ではないため、単語の長さ L ずつ進むスライディングウィンドウを使えます。開始オフセットを 0 から L - 1 までそれぞれ処理します。target は words に含まれる各単語の必要個数を保持し、window は現在のウィンドウ内の単語数を保持します。これにより、重複する単語も正しく扱えます。 右ポインターで新しい単語を追加したと...

問題リンク 乗算、除算、剰余演算子を使わずに、2つの整数を割り算する問題です。商は 0 に向かって切り捨てます。問題の制約により、除数は 0 ではありません。 両方の値の絶対値を long として求めます。絶対値を計算する前に long にキャストすることが重要です。Integer.MIN_VALUE の正の絶対値は int に収まりませんが、long なら表現できます。 次に、商のビ...

[問題リンク] https://leetcode.com/problems/implement-strstr/ 接頭辞関数（「接頭辞であり、同時に接尾辞でもある最長の proper prefix」を記録するため、LPS 配列とも呼ばれます）は、needle の各位置で終わる部分文字列について、接尾辞でもある最長の proper prefix の長さを記録します。Proper prefi...

問題 方針 numsを左から右へ走査し、次に残す値を書き込む位置を示すインデックスを保持します。現在の値がvalと異なる場合はnums[write]へコピーし、writeを進めます。valと等しい値は読み飛ばします。 各要素を処理する前、先頭のwrite個の位置には、これまでに確認した値のうちvalと異なるものだけが元の順序のまま正確に格納されています。writeは現在の走査位置を超え...

問題 解法 入力はソート済みなので、同じ値は隣り合っています。読み取りインデックスで配列を左から右へ走査し、書き込みインデックスで新しい重複のない値を置く次の位置を管理します。現在の値が最後に書き込んだ値と異なる場合、その値を書き込み位置にコピーしてから書き込みインデックスを進めます。 各読み取り時点で、接頭辞 nums[0..write) には、処理済みの入力に現れた重複のない値...

問題 方針 リストをグループごとに処理します。各グループの先頭から k - 1 個のリンクをたどり、k 番目のノードを探します。残りのノードが k 個未満なら、その末尾部分は元の順序を保つ必要があるため処理を終了します。グループを作れる場合は、グループの次のノードを groupNext に保存し、グループ内のリンクを groupNext に向けて反転します。反転の開始時に前ノードを ...

[問題リンク] https://leetcode.com/problems/swap-nodes-in-pairs/ 隣り合う2つのノードをペアごとに入れ替えます。値を書き換えるのではなく next 参照をつなぎ直すため、元のリストのノードをそのまま再利用します。 ダミーノードを置くことで、先頭のペアにも後続のペアと同じように直前のノードを用意できます。before は、すでに最終的...

問題 方針 空でない各入力リストの現在の先頭ノードを最小ヒープに入れます。各ステップで、ヒープにはまだノードが残っている各リストから、未マージ部分の先頭ノードがちょうど一つずつ入っています。したがって、ヒープの最小ノードは全リストに残っているノードの中で最も小さく、結果に追加できます。そのノードを取り出したら、結果に接続する前に次のノードをヒープへ追加します。先に次のノードを保存して...

問題 方針 ダミーヘッドを使うと、結果リストを簡潔に構築できます。tail ポインターは、最後に追加したノードを指します。両方の入力リストが空でない間、現在のノードのうち値が小さい方を結果に接続し、そのノードが属する入力リストだけを進めます。この処理中、結果リストは常にソート済みで、入力から処理したノードが順番に含まれます。一方のリストが終わったら、もう一方のリストの残りの部分を接続...

問題 動的計画法 この問題で使うパターン演算子は 2 つだけです。. は任意の 1 文字に一致し、* は直前の原子を 0 回以上繰り返したものに一致します。そのため、* は直前の原子と組み合わせて処理し、単独で使ったりパターンのより前の部分に適用したりすることはありません。問題ではすべてのパターンが有効であると保証されるため、各 * の直前には原子があります。 dp[i][j] を、s...

問題 方針 文字列を左から右へ走査し、まだ対応する閉じ括弧がない開き括弧をスタックに積みます。各文字を処理する直前、スタックにはこれまでに見た開き括弧のうち、まだ対応付けられていないものだけが元の順序で残っています。そのため、閉じ括弧が現れたら、直前に現れた開き括弧と対応していなければなりません。スタックが空の場合、または括弧の種類が一致しない場合、文字列は無効です。走査後にスタックが...

問題 バックトラッキング 入力には 2 から 9 までの数字が与えられます。それぞれの数字は電話のキーパッド上の文字に直接対応します。入力が空の場合、作れる組み合わせはないため空のリストを返します。 再帰では数字を1桁ずつ処理します。インデックス i の呼び出しに入った時点で、StringBuilder には先頭から i 個の数字に対して選んだ文字が、それぞれ1文字ずつ順番に格納さ...

問題リンク この問題では、互いに到達可能な異なる2頂点からなる、順序を区別しないペアの数を求めます。2頂点が互いに到達可能であることと、同じ強連結成分（SCC）に属することは同値です。SCC内では、どの頂点からも他のすべての頂点へ有向路が存在します。 サイズが s の各SCCでは、s * (s - 1) / 2 個のペアすべてが条件を満たします。反復版のコサラジュ法を使います。1回目の深...

強連結成分 有向グラフにおける強連結成分（SCC）とは、すべての頂点が互いに到達可能である頂点の極大集合です。互いに到達可能であるとは、双方向に到達できることを意味します。同じ SCC に属する任意の 2 頂点 u と v について、u から v への有向パスと v から u への有向パスの両方が存在します。一方向にしかパスがない場合、両頂点は同じ成分には属しません。 タージャンのアルゴ...

[問題リンク] https://leetcode.com/problems/remove-nth-node-from-end-of-list/ 単方向連結リストの先頭 head が与えられたら、後ろから n 番目のノードを削除し、新しい先頭を返します。n は有効な値であることが保証されています。値をコピーするのではなく、既存ノードのリンクをつなぎ直します。 head の前にダミーノー...

公式 複素数を極形式 [z=r(\cos\theta+i\sin\theta)] で表します。ここで $r\ge 0$ は複素数の絶対値、$\theta$ はラジアンで測った偏角です。整数 $n$ に対して、ド・モアブルの公式は次のようになります。 [z^n=r^n\bigl(\cos(n\theta)+i\sin(n\theta)\bigr)] です。 $n<0$ の場合...

問題 解法 配列を左から右へ一度だけ走査します。nums[i] を処理する前、マップにはそれより前に確認した値とそのインデックスだけが格納されています。現在の値に対する補数 target - nums[i] をマップから検索します。見つかった場合、保存されていたインデックスと i が答えになります。見つからなければ、現在の値とインデックスを保存し、後続の要素で使えるようにします。 マッ...

問題 解法 中順走査では、各ノードを左・ノード・右の順に訪問します。明示的なスタックには、左部分木の処理がまだ完了していないノードを保存します。ルートから始めて、左へ進めるところまで進みながら各ノードをスタックに積みます。次に、次のノードを取り出して値を結果に追加し、その右の子へ移動します。現在のノードとスタックが両方空になったら走査を終了します。ルートが null の場合も空のリス...

[問題リンク] https://leetcode.com/problems/single-element-in-a-sorted-array/ ソート済み配列では、単一要素を除くすべての値がちょうど2回ずつ現れます。単一要素より前では各ペアは偶数インデックスから始まり、単一要素より後ではペアの並びがずれるため、各ペアは奇数インデックスから始まります。 各反復で mid をペアの先頭で...

問題へのリンク XOR は、x と y の同じ位置のビットが異なるとき、その位置を 1 にします。そのため x ^ y は異なるビット位置をすべて示し、Integer.bitCount はその 1 の個数、つまりハミング距離を数えます。 Java の整数幅は常に 32 ビットなので、時間計算量と追加領域の計算量はいずれも $O(1)$ です。 class Solution { ...

BOJ 11659: 区間和を求める 4 配列の累積和配列を作る。prefix[0] = 0とし、prefix[i + 1] = prefix[i] + value[i]で定義する。入力の位置は1始まりで、両端を含む区間[a, b]の合計はprefix[b] - prefix[a - 1]となる。この式で累積和配列のインデックスを使うことで、入力位置とJavaの0始まり配列インデックスの違...

問題 解法 入力配列は空でないことが保証されています。配列を一度走査し、現在のインデックスで終わる部分配列の最大和 (ending) と、これまでに見つかった全体の最大和 (best) を追跡します。各要素では、直前の部分配列を延長するか、現在の要素から新たに開始します。 ending = max(nums[i], ending + nums[i]) ending を更新した後、...

問題へのリンク 左から右への走査 標準的なローマ数字では、ある記号の直後により大きい値の記号が続く場合にだけ、その値を引き算します。たとえば IV は -1 + 5 = 4 です。減算表記に含まれない記号は通常どおり加算します。各記号と直後の記号を比較すれば、この規則をそのまま適用できます。ループ不変条件は、各反復の終了時に、それまでに処理したすべての記号の符号付き寄与分が sum ...

問題 解法 リストはソート済みなので、同じ値は必ず隣り合っています。ポインターを1つ使い、現在まで残した最後のノードを指します。次のノードの値が現在のノードと同じなら次のノードを飛ばし、異なるならポインターを次へ進めます。各ステップで、headからポインターまでには、処理済みの異なる値ごとにノードが1つだけ、ソート順で保たれます。最後に残るノードは元のリストの末尾なので、その nex...

問題へのリンク 方針 最初の文字列を左から右へ走査します。各位置で、最初の文字列の文字と、ほかのすべての文字列の同じ位置にある文字を比較します。最初に不一致が見つかった位置で共通接頭辞は終わるため、最初の文字列のその位置より前の部分を返します。 比較する前に、ほかの各文字列がその位置の文字を持つ長さかどうかを確認します。文字列がそれより短ければ、共通接頭辞はその文字列の長さで終わり...

問題 解法 負の整数は符号 - が左側にしかないため、回文にはなりません。また、0 以外で末尾が 0 の整数も回文ではありません。反転すると先頭が 0 になりますが、整数では先頭の 0 は表現されないためです。 数値を文字列に変換したり、すべての桁を反転したりする代わりに、後半の桁だけを反転します。ループの各反復で x から末尾の桁を取り除き、それを reversedHalf の末尾に...

問題 解説 入力から数字を1桁ずつ取り出し、反転後の値に追加します。Javaの整数除算は0方向へ 切り捨てられ、% の結果は被除数の符号を引き継ぎます。そのため正負どちらの場合も x % 10 は符号付きの最後の桁になり、繰り返し割るとその桁が取り除かれます。したがって 0や末尾に0がある場合も、特別な処理は不要です。 累積値に10を掛ける前に、整数の境界を10で割った値と比較します。...

問題 解説 文字列を1文字ずつ走査し、現在の行のビルダーに文字を追加します。行インデックスは 下または上へ1つずつ進み、最初または最後の行に到達したら進行方向を反転します。 すべての文字を配置した後、行ビルダーを上から順に連結すると変換後の文字列になります。 行が1つだけの場合、または行数が文字数以上の場合は斜めの移動がないため、入力を そのまま返します。 この方法ではジグザグの走査を...

問題 解説 すべての回文は、1文字を中心とする奇数長の回文か、隣り合う2文字の間を中心とする 偶数長の回文のどちらかです。各インデックスについて両方の中心から外側へ広げ、 左右の文字が一致する限り調べます。これにより、それぞれの中心を持つ回文を すべて確認できます。 最長の答えは半開区間 [bestStart, bestEnd) として保持します。より長い回文を 見つけた場合にだけ区間...

問題 二分探索による分割 2つの配列はどちらもソート済みなので、マージせずにそれぞれを左半分と右半分に分けられます。左半分には要素数の合計の半分（切り上げ）の要素を含め、左側のすべての値が右側のすべての値以下になるようにします。 短い方の配列 nums1 で分割位置を二分探索します。nums1 の i 個の要素を左半分に置くなら、nums2 からは j = (m + n + 1) ...

問題: Longest Substring Without Repeating Characters スライディングウィンドウ 文字列のs[left..right]をウィンドウとして保ち、その中の文字を集合に格納します。アクティブなウィンドウに同じUTF-16 charが重複して含まれないことが不変条件です。right位置の文字がすでに集合にある場合は、その重複文字がなくなるまで左端の文...

問題リンク 整数配列 nums と整数 target が与えられます。異なる3要素の和のうち、target に最も近い値を返します。最も近い和が複数ある場合は、いずれを返してもかまいません。 配列を昇順にソートし、各要素を順に3つ組の最初の要素として固定します。残りの範囲の両端に2つのポインターを置いて和を探します。和が target より小さければ左ポインターを右へ動かして和を大きくし...

問題 解説 配列をソートし、各インデックス i を順に固定して、残りの範囲を二つの ポインター left = i + 1、right = nums.length - 1 で探索します。配列が ソート済みなので、ポインターは一方向にだけ動かせます。3つの値の合計が0より 小さい場合、現在の left と、より小さい右側の値との合計もさらに小さくなるため、 left を増やしても解を見落...

問題へのリンク 貪欲な額面選択 ローマ数字は、大きい位の記号から小さい位の記号へ順に表します。減算表記は6種類あり、IVとIXはそれぞれ4と9、XLとXCは40と90、CDとCMは400と900を表します。残りの値以下で最大の額面を選んで記号を結果に追加し、その額面を残りの値から引きます。残りがなくなるまでこれを繰り返します。表では減算表記もそれぞれ1つの額面として扱うため、この貪欲...

問題: Container With Most Water 2ポインター l < rとなる2つの添字を選ぶと、容器に入る水の高さは2本の線のうち低い方で決まります。幅はr - l、高さはmin(height[l], height[r])なので、面積は次の式です。 [(r-l)\times\min(\text{height}[l],\text{height}[r]).] 配列...

解法 木は連結かつ閉路のない無向グラフです。未訪問の頂点ごとに幅優先探索を開始し、その連結成分全体を訪問します。頂点はキューに追加する時点で訪問済みにするため、同じ頂点が重複してキューに入りません。辺をたどって隣接頂点を確認する際、すでに訪問済みで現在の頂点の親ではない頂点があれば、閉路が存在します。無向グラフでは親へ戻る辺だけを除外します。閉路のない連結成分だけを木として数え、孤立頂点も...