ABC lessons learned1

AtCoder Beginner Contest lessons learned (ABC 150まで)

ABC 6,8問体制(126..最新)のD問題をだいたい解いたので、そこから得た教訓をまとめていきます。

トップページへ

ABC 125まで

AISing Programming Contest 2019 C

コードはこちら

intを使わない。

問題自体は、連結するマスを連結成分に分解するだけである。色の異なるマス同士を連結してできるグラフでは、任意の黒マスから任意の白マスに到達可能である。よって連結成分の黒マスの数 x 白マスの数が求める個数で、これを連結成分ごとに数えればいい。連結成分といえばunion-find木である。

解の大きさが明示されていないが、どうも 32-bit 整数に収まらないようである。よって 64-bit 整数で計算する。ACLのunion-find木は成分を int で扱っており、したがって long long int から int への narrowing cast が発生するが気にしない。答えがオーバフローしてWAするのは非常に分かりにくいバグなので、初めから回避する方が簡単である。

ABC 037-D

コードはこちら

EDPC G問題の復習である。

ABC 060-B

コードはこちら

$g = GCD(A,B)$ を解像度とみなす。これは $Ax = By + gz$ なる $x,y,z$ を選ぶことができることを意味する。なぜなら $(A/g)x = (B/g)y + z$ に出てくるのはすべて整数だからだ。なので $C = gz$ なる $z$ を見つけられればよいが、これは $C$ が $g$ の正の倍数であることと等しい。

ABC 065-D

コードはこちら

精選100-67で青diff。頂点同士ではなく、頂点とX,Yに平行な直線を結ぶ。

$X$ 座標が同一なの頂点は道を作るコストが0なので、すべてunion-find木の連結成分でつなげる。 $Y$ 座標が同一なの頂点も然り。

ある頂点 $V_i$ から見てコストが最も安いが0でない頂点は、 $X$ が最も前後に近い( $X^{-}, X^{+}$ 頂点、 $Y^{-}, Y^{+}$ が最も前後に近い頂点、の高々4頂点である。これらの道のコストはそれぞれ $X - X^{-}, X^{+} - X, Y - Y^{-}, Y^{+} -Y$ であり、道の先にある頂点はそれぞれ $x = X^{-}, x = X^{+}, y = Y^{-}, y = Y^{+}$ を満たす任意の頂点である。 $V_i$ とこれらの頂点を結ぶ辺を追加する。

辺をコストの小さい順に並べ替える。あとはunion-find木でクラスカル法を実行し、コストが低い順に連結していない辺を連結する。

ABC 074-D

コードはこちら

精選100-63。

入力にワーシャルフロイド法を実行して結果が変わったら -1 である。

ある辺 $d(x,y)$ が最短距離であるなら、任意の経由地 $i$ に対して $d(x,y) < d(x,i) + d(i,y)$ を満たすので、道 $(x,y)$ は存在したと言える。そうでないなら道 $(x,y)$ は存在しなかったと言える。これもワーシャルフロイド法の一部である。

ABC 098-D

コードはこちら

XORとは桁繰上りのない和である。

と知っていれば題意を満たす $A_l ... A_r$ は、各ビットついて、立っているビットの数は全部0または1個に限ると解る。立っているビットの数は $A_i$ について二進数表記したものを(2で繰り返し割ればいい)、 $i$ について累積和を取る。

2で割る回数は決め打ちでよい(入力から20回だし、32回としても問題ない)。 $A_i$ ごとに割る回数を変えるとバグの元である。

ABC 103-C

コードはこちら

ある数を $a_i$ で割った余りの最大値は $a_i-1$ である。そのような $m$ を構成可能である(後で最大公倍数-1だと知った)。 $a$ が互いに素でなかったらとか倍数だったらとか考えたが、特に関係無かった。

ABC 106-D

コードはこちら

累積和の累積和を取る。

• 最初にL始まりR終わる列車の二次元配列を作る。このときRで終わるのではなく、RおよびRより西で終わる列車を数える。これは累積和で求まる。
• 次にLで始めるのではなく、LおよびLより東で始まる列車を数える。これは上記に累積和を、Lついて累積和と取ることで求まる。
• あとは各クエリに答える。

ABC 113-C

コードはこちら

問題文を素直に実装する。

のだが、焦ると何をすべきか分からなくなる。順を追って考えよう。

• 入力を入力順に保存する(これを忘れがち)。県 x $10^9$ + 年 x $10^6$ でよいが、出力に引きずられて県 x $10^6$ にするとWAする。
• 市を県ごとに分類する
• それぞれの県の市を、年の昇順で並び替えて1から順位をつける。値を県 x $10^6$ + 順位 x $10^6$ とする。
• キーと値とを結び付け、入力されたキーの順に値を出力する

整数の0埋めはイディオムなので覚える。

os << std::setfill('0') << std::setw(12) << ids[key] << "\n";

ABC 116-C

コードはこちら

いもす法のココロだが、いもす法ではない。

手を動かすと解るが、水やりすると左端に上りエッジが一段、右端に下りエッジが一段できることが分かる。よって $h_0=h_{N+1}=0$ として、 $h_1..h_{N+1}$ について $h_0..h_N$ から変化の絶対値を足して2で割ると答えが求まる。

図にすれば少し分かりやすい。以下の4パターン(左右対称を省略)で、上記の条件を満たすことが分かる。

 +++++  +++++  +++++  +++++

 --     ---     ---   -----
-+++++  +++++  +++++  +++++

ABC 117-B

コードはこちら

落ち着いて問題文を最後まで読む。焦らない。

ABC 117-C

コードはこちら

悩んでないで手を動かす。

$X$ は昇順に並べ替えたとして、以下を試してみよう。

• コマが1個なら、左端において、右端まで一通りなめる
• コマが2個なら、左右の端において、それぞれ中央に向かう。このとき二つのコマが出会う必要はないと解る。では最終状態でどれだけ離せるかというと $X_i, X{i+1}$ の最長距離である。
• コマが3個なら、左右の端と、先の $X_i$ または $X{i+1}$ におく、両端から中央へ、中央から端に向かう。三つのコマが出会う必要はなく、最終状態でどれだけ離せるかというと、先の $X_i, X{i+1}$ と二番目の最長距離 $X_j, X{j+1}$ である。
• 以下同様に $N$ コマあるなら $N-1$ 番目に大きい $X_k, X{k+1}$ を離せる。特に $N \geq M$ なら、すべてのコマをすべての $X$ に配置するので初期配置から移動しなくてよい

これを実装する。

ABC 119-C

コードはこちら

効率が悪いが組み合わせを網羅。

$N$ 本の竹を、合成してAにする素材( $S_1$ )、合成してBにする素材( $S_2$ )、合成してCにする素材( $S_3$ )、使わない( $S_0$ )の4通りに分類する。この順列組み合わせを網羅し、合成コストの最小値が答えである。

合成コストは、 $abs(\sum S_1 - A) + abs(\sum S_2 - B) + abs(\sum S_3 - C) + 10 \times (|S_1| + |S_2| + |S_3| - 3)$ である。

竹の組み合わせ ($S_0,S_1,S_2,S_3$) をどうやって網羅するかが課題である。 $A,B,C$ に少なくとも一本の竹を割り当てるとして、組み合わせに重複を認めるなら、 0...0123 を始点として std::next_permutation を回し、 0 を 0123 に置き換えればよい。このとき重複ありの組み合わせは $4^{N-3} \times {{n} \choose {3}} < 4^8 = 65536$ なので十分速い。念のためメモ化している。

ABC 120-D

コードはこちら

クエリを先読みして逆から考える。

Union-find木は要素を増やすことはできるが除くのが難しい。なので、不便さが最大という最終状態から、橋を掛けたら不便さが減っていく、と逆操作を行う。A-Bに橋を架けることで不便さはAの連結成分 x Bの連結成分だけ減る。辺のない頂点の連結成分は1個なので特別扱いは要らない。

ABC 125-C

コードはこちら

左右から累積最大公約数を取ると、ある数を除いた最大公約数を求められる。セグメント木にも載るが、 $GCD(N,0) = N$ なので単位元は $0$ である。自力ではTLEし、公式解説を見て実装した。

ABC 126-140

ABC 126-D

コードはこちら

• 入力が木なので、幅優先探索(BFS)を使えば頂点数の線形時間で解ける。根である頂点からBFSすれば、各頂点を根に近い順に訪問できる。ダイクストラ法は $log(N)$ 倍だけ時間が掛かるので使わない。
• 木の頂点をキューに載せるとき、訪問元の色を追加情報に載せる。 (辺の重さ+訪問元の色) の偶奇(and 1)を、訪問先の色にする。
• 根はどの頂点でもいい。わざわざ葉=次数が1の頂点を探す必要はない。

ABC 126-E

コードはこちら

難しく考えすぎないことも重要である。

$X+Y$ が偶数か奇数かは $Z$ で分かるが、そのこと自体は実は重要ではない。

$A_{X_i}$ が分かれば $A_{Y_i}$ が分かるという依存関係があれば十分である。そのような依存関係がある $A_i$ について、一つが分かれば残りはすべて解る。よって求める答えは $A_i$ の連結成分の数である。

ABC 126-F

コードはこちら

2時間8分掛かった。

$K=1$ なら、同じ数を隣同士にして出力すれば答えである。

$K \geq 2^M$ または $M=1 \land K=1$ なら解なしである。

$P = 2^M - 1$ とする。 $K = P$ なら、中心に $[0, P, 0]$ を置いて、その左右に残りの数を左右対称に置き、末尾に $P$ を置く。より正確には、 $1,...,P-1,0,P,0,P-1,...1,P$ である。二つの $[0..P-1]$ の間についてXORを求めると対称性から $P$ である。二つの $P$ の間についてXORを求めると $1 \oplus 2 \oplus ... \oplus P = 0$ より、 $1 \oplus 2 \oplus ... \oplus P-1 = P$ である。

それ以外の場合は工夫がいる。 $Q = P \oplus K$ として、 $[P, Q, 0], S, [K], \bar{S}, [0, Q, P, K]$ と置く。 ここで $S$ は $[0..P] \setminus {0,P,Q,K}$ 、 $\bar{S}$ は $S$ の左右反転である。 $S$ を除くと $[P, Q, 0, K, 0, Q, P, K]$ であり、二つの $0,P,Q$ の間についてXORを求めると $K$ であり、 $K$ 間のXORは $Q \oplus P = K$ である。ここで両0の間に $S, \bar{S}$ を差し込むと答えになる。

公式解説を読むと、上記の $K = P$ の場合が、それ以外にも当てはまると説明がある。しまった、気が付かなかった。

ABC 127-D

コードはこちら

• すべての操作終了後の結果だけ解答すればよいので、操作ごとに状態を更新をする必要はない。いわゆるクエリ先読みと同じ。
• カードを削除したり置き換えたりするコストが高そうなので、これらの操作を無くしたい
• $A_i < C_j$ なら、 $C_j$ が選ばれて $A_i$​ は選ばれない。ここから「N枚のカードに書かれた整数の合計の最大値」を「降順に上位N枚選んだカードに書かれた整数の合計の最大値」と読み替える。そうすれば $C_j$ に隠された $A_i$ は無視できる。これでカードを削除せずに済む。
• ただしBが大きいので、CをB枚Aに追加する操作をM回やると、TLEかMLEするかもしれない。よって $C_j$ の降順にN枚以上までAに追加する。Cを余分にAに追加してもどのみち小さいカードは選ばれないので、ざっくり実装して構わない。
• CをB枚というのは、きちんとしたコードなら構造体とメンバと比較演算子を定義すべきである。しかし比較演算子を定義する時間がもったいない早解きなら、 std::tuple を使うと辞書順の比較演算子がついてくる。

ABC 127-E

コードはこちら

全く手掛かりがつかめず諦めたのだが、解答があっさりしていてびっくりした。

駒を一つ固定してDPしたら解けなかった。駒を二つ固定するのが正解である。駒を二つ固定したとき、以下の操作が答えである。

• 駒を二つ固定したときの、行の差の絶対値 $0 \leq dy < N$ 、列の差の絶対値 $0 \leq dx < N$ を固定する。
• このような駒二つの距離は $dy + dx$ である。
• 矩形 $(0,0)-(dy-1,dx-1)$ をの左上と右下に駒を置く方法は、行方向に $N-dy$ 、列方向に $M-dx$ 通りで、それぞれ独立なのでこれらの積である。
• $dy > 0 \land dx > 0$ なら上下反転があるので二倍する
• 上記をまとめると、 $(dy+dx)(N-dy)(M-dx)(1+(dy > 0 \land dx > 0))$ である

駒を二つ固定すると、残りの駒の置き方は ${N+M-2} \choose {K-2}$ 通りある。これらそれぞれが一回ずつ寄与するので、上記の和に掛けると答えである。

ABC 128-C

コードはこちら

$N$ が小さいので $2^N$ の総当たりでいける。

ABC 128-D

コードはこちら

std::back_inserter の使いどころ。

$N$ と $K$ が小さいので総当たりで解ける。つまり

• 何回操作するか $n_{iter} \leq K$
• 何個取り出すか $n_{pop} \leq min(n, n_{iter})$
• 左から何個取り出すか $left \leq n_{pop}$
• 右から何個取り出すか $n_{pop} - left$

について、筒から宝石を実際に取り出せばいい。 std::copy と std::back_inserter を使うと簡潔に書ける。価値が負の宝石を最大 $n_{iter} - n_{pop}$ 個詰め戻せばいいので、詰めずに残った宝石の価値の合計を求める。

ABC 128-E

コードはこちら

当時は遅延セグメント木で青diffだったのだろう。

道路の工事時間は原点に読み替えて、位置 $X_i$ を $[S_i-X_i, T_i-X_i)$ まで工事すると考える。登場するすべての時刻 $S_i-X_i, T_i-X_i-1, T_i-X_i, D_j$ を座標圧縮して $tbl[S_i] = k \in {0..}$ と読み替えるようにする。

座標圧縮した時刻を遅延セグメント木に載せる。キーは座標圧縮した時刻である。値はある時刻において、最も左にある工事の位置 $X_i$ の最小値(なければというか初期値は $\infty$ )である。これを工事 $i=1..N$ について遅延セグメントに $apply([S_i-X_i, T_i-X_i), X_i)$ すると、ある時刻の工事の位置を更新できる。

工事をすべて遅延セグメント木に載せたら、 $Q$ 人について遅延セグメント木の $prod(D_j,D_j+1)$ の値が最も左にある工事の位置、つまり行き止まりになる位置なので答えである。ただし $\infty$ のときは行き止まりにならないので -1 と答える。

ABC 129-D

コードはこちら

• 4,000,000マスなので、一マス $O(log(max(H,W)))$ の探索コストならTLEしない
• あるマスの光線が障害物に当たるかどうかは、 std::upper_bound で分かる
• 障害物に当たらずグリッドを突き抜けてしまうと、イテレータを begin() , end() と比較するのがめんどくさい。なので番兵としてグリッドの外周を障害物で囲っておく。番兵を使うことを覚えておきたい。

ABC 129-E

コードはこちら

301-Dに似ているけどややこしい。

上の桁から順に組み合わせの数を累積すればいい。話がややこしいのは、ある桁が0ならその下位の桁については総当たりした組み合わせを増やし、ある桁が1ならその値に決め打ちして隣の桁をみることである。Lが2進数で $n$ 桁あるとき

• 最上位桁を0と置けば、残りの桁は0または1である。(0,0), (0,1), (1,1)の組み合わせが $3^{n-1}$ 通りある
• 最上位桁は必ず1である。 $L=1x...$ について $x=1$ なら
  • 最上位桁は (0,1), (1,0)の組み合わせが $2$ 通りある
  • $x=0$ とおいたとき、 $...$ については $3^{n-2}$ 通りある
  • $11$ については隣の桁を見る
• $L$ の最上位の隣の桁が0つまり $10...$ なら、0については (0,0)の1通りに限るので組み合わせは増えず、隣の桁を見る

一般的に $i$ 桁目 $1 < i \leq n$ については、 $1..{i-1}$ 桁目に1が $m$ 個あれば $2^m * 3^{n-i}$ 通りになる。最後に $1..n$ 桁目に 1が $k$ 個あるとき $2^k$ を加える。これまた忘れやすい。

ABC 130-D

コードはこちら

• まず累積和 cumsum を取る、と勘づく
• $cumsum(a_2 ... a_i)$ = $cumsum(a_1 ... a_i) - a_1$ なので、部分列の開始点をずらしていけば部分列の cumsum を更新できる。なので部分列の総当たりは避けられる。
• 実際には cumsum を更新する代わりに、部分和を取る区間より左も含めた cumsum + k 以上になる a の位置を探す。累積和は部分列を長くすれば増えるので二分探索か尺取り法が使える。まず二分探索で書く。

Num answer {0};
for(decltype(n) i{0}; i<n; ++i) {
    const Num d = k + cumsum.at(i);
    auto it = std::lower_bound(cumsum.begin() + i, cumsum.end(), d);
    const auto count = cumsum.end() - it;
    answer += count;
}

尺取り法を使えば、kの探索回数を $O(N*log(N))$ から合計 $O(N)$ にできる。

Num answer {0};
Num right {1};
for(Num left{1}; left<=n; ++left) {
    while((right <= n) && ((cumsum.at(left-1) + k) > cumsum.at(right))) {
        ++right;
    }
    answer += n + 1 - right;
}

ABC 130-E

コードはこちら

LISっぽいのだが、なかなかLISが身につかない。

$S$ について、要素の値がどこに出現するかの集合、つまり $i \in tbl[a] if A_i = a$ を作る。

便宜上、空整数列 $|S_0|$ が一通りあるとする。 $T_i$ と $S_i : i \in tbl[T_i]$ の要素を整数列として結びつけることができる。このとき $i$ を結び付けることで整数列を1個伸ばすことができ、どこから伸ばせるかというと $0 \leq j < i$ なる $S_j$ で終わる整数列である。よってこれらの組み合わせの数の和が、 $T_i$ で終わる整数列の組み合わせである。

これを $i=1..M$ まで繰り返す。セグメント木を使い、 $i=0..N$ が $S_i$ で終わる整数列が取る組み合わせの数として、上記の通り更新する。 $i$ が終わるときに一括更新し、 $i$ の処理中に更新しない(そうしないと数えすぎになる)。

ABC 131-D

コードはこちら

鉄則本の「6.4 一手先を考える」問題 A39とほぼ同じである。ここまでに仕事を始めないと間に合わない締め切り (b-a) を現在時刻が超過しないかどうか調べて、超過したら即 "No" と出力する。

仕事を表現する構造体は、締め切り、終点、掛かる時間から成る。ソートするのに必要なのは終点だけなので、構造体ではなく std::tuple で作れば比較演算子は実装しなくてもついてくる。

ABC 131-E

コードはこちら

最大値を考えるらしい。

中心に頂点1を置き、残り $N-1$ 頂点に対して星型に頂点を張れば、最短距離が2であるような頂点対は $(N-1)(N-2)/2$ 個ある。これを1個ずつ減らせばよい。と解説に書いてあり、実際に頂点 $2..N$ を一つずつ結んでいけば1個ずつ減らせる。星型を思いついてなぜ解けなかったのかよく分からない。二部グラフ問題に落とし込もうとして時間を使い過ぎたか。

ABC 131-F

コードはこちら

連結成分とは気づいたが、それ以上どうしていいか分からなかった。

同一X座標上にある頂点の集合を $S$ とする。 $(x,y) \in S$ にある $y$ と、他の頂点 $(x, y^{'}) \in S$ があるとき、Y座標 $y^{'}$ にある他の頂点 $(x^{'}, y^{'})$ を組み合わせて頂点 $(x^{'}, y)$ を作れる。ということをどう表現するかである。公式解説通り、頂点をunion-find木で連結して、連結成分のX座標とY座標を数える。数え方は頂点ではなく座標をループしないとTLEする。

ABC 132-D

コードはこちら

けんちょん氏の解説にある通り、重複組み合わせに関する理解が問われる。

階乗を求めるコードは頻出なのであらかじめ用意してテストしておく。GMP (GNU Multi-Precision Library)を使えば、任意精度整数を使って組み合わせを求められるし mod 1000000007 も求まるので検算に使える。Rなら gmp パッケージから利用できる。

ABC 132-E

コードはこちら

単にBFSして、各頂点までの最短距離を求める。ただし移動回数が3の倍数以外なら最短距離を更新しない。移動回数が3の倍数で最短距離を更新できない移動についてはその後に移動しないので、いつか探索する頂点は無くなる。

ABC 133-D

コードはこちら

変数の和が二つあるとき、それらから特定の変数を除くには、差を取ればキャンセルできることを思いつく。統計学では difference in differences (DID) という手法がある。

• 山 $i$ に降った雨の量を $a_i*2$ とする。雨量は偶数なのでこう表現できる。山 $i$ に降った雨の量は $a_i+a_{i+1}$ である。
• $B_2 = A_2 - A_1$, $B_3 = A_3 - B_2$, ... と置く。下記より $B_n = a_1 + a_1$ である。ここから $a_1=B_n / 2$ が求まる。
• あとは $A_{2..n}$ から芋づる式に $a_2..a_n$ が求まる。この値を2倍して出力する。

A1=a1+a2, A2=a2+a3, A3=a3+a4, A4=a4+a5, A5=a5+a1
    B2=A2-A1=a3-a1,
              B3=A3-B2=a4+a1,
                        B4=A4-B3=a5-a1,
                                   B5=A5-B4=a1+a1

ABC 133-E

コードはこちら

素直に頂点を塗る。

131-Eの苦戦とは打って変わって、こちらは素直に彩色すればいい。木の頂点間の距離が2以下というのは、頂点 $q$ に親頂点 $p$ があるなら、親頂点 $p$ と $p$ の子頂点 ( $q$ の兄弟頂点)を指す。

• 木の根は $K$ 色で塗る。頂点番号をインデックスとして、何色で塗れるか保存する。
• 木の根に子が $i$ 頂点個あれば、子を $K-i..K-1$ 色で塗る
• 木の根に子の子が $j$ 個あれば、子の子を $K-j-1..K-2$ 色で塗る。以下DFSで葉まで繰り返す。
• 各頂点を何色で塗れるかをmodintで乗算する

途中で塗る絵の具が無くなったら頂点を0通りの色で塗るので、結果的に答えは0通りになる。だから塗る色がなくなったときの処理は明示的に実装しなくてよい。

ABC 134-D

コードはこちら

エラトステネスの篩は、素数 $p$ を使って $p$ の倍数は素数でないと印をつけていく。

ここではその逆で、素数とは限らない $i$ の倍数について既に印がついてるなら、 $i$ に印をつけるかどうかで、 $i$ の倍数についた印が偶数個か奇数個か(パリティ)を指定通りにできる。いいボールの入れ方が無い、という状況を思いつかない。

ABC 134-E

コードはこちら

なんとgreedyだった。

解説を読んだところ、増加列を複数管理しておいて、増加列につなげられる(増加列の最大値より大きい)ならその増加列に積んで、そうでないなら増加列を1個増やす。積むべき増加列は最大値が最も小さいものを選ぶ、というgreedyで解ける。増加列そのものを管理する必要はなく、最大値の値だけ std::multiset<Num> で管理すればよい。

LISとかstackとか色々考えたけど駄目だった。

ABC 135-D

コードはこちら

Mod 13 と mod 1000000007 を区別する。

$(10^{N+1} * d) mod 13 = ((10^{N} mod 13) * 10 * d) mod 13$ である。つまり10の桁数乗の部分を mod 13で作る。 $d$ の部分は文字列で指定されていればその値、それ以外は $d=0..9$ を総当たりする。これである桁以下の値が確定した時点で、 mod 13 つまり13で割った余りが $0..12$ それぞれについて何通りあるかを調べる。

何通りあるかは atcoder::modint1000000007 で数える。初期値は、余り0が1通り、他は0通りである。

ABC 136-D

コードはこちら。if文だらけで長いので、もう少しすっきり書けそうである。

結論から言えば、連続するマスを分割すればよい。

十分長い移動回数になれば、 LR または RL を往復してそこから外に出ないことが分かる。 $10^{100}$ つまり移動回数が偶数回のときに左右どちらに居るかを求めればいい。

• LR または RL になる出発点は、前者は左に連続する L と右に連続する R 、後者は左に連続する R と右に連続する L である。
• 上記の分水嶺は RL である。よって RL を見つけたらこのRとLの間でマスをグループ分けする。
• 後はグループごとに、 LR または RL に到達するまでの回数の偶奇を求める。

別解としてはダブリングがあるらしい。

ABC 136-E

コードはこちら

操作後の $A$ を割り切りる数は $\sum A$ の約数しかないので、それらの約数 $F$ を全部試す。

$A$ を増減してすべての要素を $F$ の倍数にし、かつ要素の増減の和が0になるようにする。まず $A$ の各要素を減らすと想定して $A mod F$ を昇順に並べ $R$ とする。 $R$ の順序はそのままに、減らすのではなく増やすと想定すれば $S$ になるが、 $S_j = F - R_j$ である。

ある $p$ があって、 $U = \sum_{j=1}^{p} R_j = \sum_{j=p+1}^{n} S_j$ になれば、増減が打ち消し合う。このとき $U \leq K$ なら題意を満たす。そのような $F$ の最大値が答えである。 $R,S$ それぞれ累積和を求めると速く求まる。

ABC 137-D

コードはこちら

締め切りから考える。

動的計画法ではなく貪欲法だということは何となくわかるのだが、初日から $M$ 日に向かうと間違える。締め切りから逆算して、 $M$ 日までに報酬を得られるアルバイトの候補を増やしていく。優先度キューで報酬を管理する。

• $M..0$ 日についてループする
• ある $i$ 日について、報酬を得られるまでちょうど $M-i$ 日掛かるアルバイトを優先度キューに追加し、
• その時点で最も報酬の高いアルバイトを請けたら、同じアルバイトは受けられないので優先度キューから削除する

ABC 137-E

コードはこちら

Bellman-Ford法だった。

頂点1と頂点Nの両方から到達可能な頂点だけでグラフを構成し、辺のスコアを $C_i - P$ として、最長経路を求める。

基本的にはBellman-Ford法で、頂点の値を $N$ 回更新したらスコアが正のループがあるとみなす。これが分からず、明示的にループ検出を実装したら 5 WAs になった。

ABC 138-D

コードはこちら

126-D とほぼ同じである。違うのは辺の重みを伝搬するのではなく、親の頂点のカウンターを子にBFSで伝搬することである。

ABC 138-E

コードはこちら

こちらもgreedyだった。

134-Eの苦戦に比べると、こちらはあっさりしている。まず t にあって s にない文字があったら題意を満たさないので-1を返す。

あとは t を先頭から順番に見ていけばいい。 s の何文字目を指すか(カーソル)、 s を何個つなげたか(周回数)を管理すればよい。

• 初期化時点では、カーソルは-1, 周回数は0とする
• まず t の先頭文字 c が、 s の何文字目か(先頭を0番とする)探す。 s を毎回スキャンするとTLEするので、 c の出る位置をあらかじめ調べて、 std::upper_bound で調べる。c は必ず見つかるのでカーソルをそこに置く。
• 同様に t の二文字目 d を探す。 d の出現位置がカーソル以降なら .end() が返るので、周回数を1足してカーソルを-1に戻してスキャンする。というより、 d の出る位置は調べてあるのだからその最小値である。

以後同様に t の最後の文字までみていけば周回数とカーソルが分かるので答えが求まる。

ABC 139-D

コードはこちら

整数を整数Nで割ったときの余りは最大N-1である。ならば数列を回転させれば、一つを除いて割った余りを最大にできる。

$1..N$ の和は $(n+1)n/2$ 、 $1..(N-1)$ の和は $(n-1)n/2$ であることは暗記してすぐ書けるようにする。

ABC 139-E

コードはこちら

トポロジカルソート

試合 $(A,B)$ の後に試合 $(A,C)$ が来るという関係は、 頂点 $(A,B)$ から $(A,C)$ への有効グラフで表現できる。頂点番号は $A * N + B$ とすればよい。これをトポロジカルソートする。サイクルがあればトポロジカルソートに失敗する(結果の頂点数が足りない)ので -1 を出力する。

トポロジカルソートに成功した場合は、ソース済グラフの直径を求めればいい。これはトポロジカルソート済の頂点順にDFSして、 子の頂点の深さ = max(子の頂点の深さ, 親の頂点の深さ + 1) で更新する。すべての頂点の深さの最大値が答えである(深さ0から始めた時は最大値に1足す)。

ABC 140-D

コードはこちら。

解説を読むまで、何をどうしてよいか分からなかった問題である。入力例4を解けなかった。

RRRLRLRLL
RRRRRLRLL
RRRRRRRLL

解き方は連続するLかRを反転させれば、反転させた部分の左右の端の人が幸福になる、というものである。もう少し詳しく書くと、 L..LR..RL の連続するRを反転させると、最右のRと最右のLの人が反転して幸福になる。ただしここで最右のLがない、つまり連続するLと連続するRは合わせて2つしかないときは、最右のRだけが幸福になる。LとRを入れ替えても同様である。一回反転させれば2人幸福になり、連続するLと連続するRの組が2つ減る(ただし最低1)。

得られた教訓と言えば、どこを反転させると最適解なのか分からないが特徴量は分かるということである。入力例を手作業で解けなくても、盤面を記述する特徴量(偶奇とかもその一種)を見つけると、解ける問題がある。

• 一回反転させると連続するLと連続するRの組という特徴量が2減る(最低1)
• 幸福な人の数 = 人数 - 特徴量

ABC 140-E

コードはこちら

ものすごく久しぶりに、解説ACできない問題に出会った。

直感的な理解は解説を読まずに分かったのだが、考察が進まず実装方法が全く分からなかった。セグメント木でACできず、 他の方のコード を読み解いてようやく理解した。

$P_i$ が答えに寄与する組み合わせの数を考える。 $P_{L1} < P_{L0} < P_i < P_{R0} < P_{R1}$ のとき、添え字で言うと $(L1, L0]$ が一番、 $[i, R0)$ が二番なので組み合わせの数は $(L0 - L1)(R0 - i)$ である。左右反転して、 $(R1 - R0)(i - L0)$ も組み合わせとして数える。両組み合わせを足して $P_i$ を掛けると、 $P_i$ の寄与が求まる。 $i=1..N$ について合計すると答えである。

$L1, L0, R0, R1$ が存在するとは限らないので、どう扱うか考える。 $P_j < P_{L0} < P_i < P_{L0}$ なる $j$ が存在しなければ、 $(0, L0]$ が一番、 $[i, R0)$ が二番である。 $P_j < P_i < P_{L0}$ なる $j$ が存在しなければ、 $(0, i]$ が二番、 $(P_i, R0]$ が一番である。ここで左右反転するのがややこしい。以上より、センチネルとして左端 $0$, 右端 $N+1$ があると考えてよい。

実装が大変である。値 $P_i$ を降順に並べる。 $P_i$ の位置 $i$ を集合 $S$ に加える。集合の前後とその前後の要素はイテレータを1個ずらすと分かるので、 $P_i$ より大きくて場所が近い要素 $R1, R0, L0, L1$ が分かる。 $R1, R0, L0, L1$ が存在するとは限らないが、センチネル $0,0,N-1,N-1$ をあらかじめ加えておく。センチネルが値につき1個でなく2個というのが重要である(これが無いとイテレータの終端判定が大変になる)。

ABC 141-150

ABC 141-D

コードはこちら

優先度キュー std::priority_queue の使いどころである。優先度キュー std::priority_queue はデフォルトで値が最も大きい値を取り出すので、最も小さい値を取り出すときは比較演算を反転する。

std::priority_queue<Num, std::vector<Num>, std::greater<Num>> q;

割引券を0枚以上使った後で、最も値段の高い品物に割引券を使うと、最も割引き額が多い。つまり貪欲法で解けばよく、割引後の値段を優先度キューで表現すればよい。

ABC 141-E

コードはこちら

蟻本を知っていれば、もっとエレガントに解けるらしい。

のだが蟻本を読んでないのでローリングハッシュで解く。L=1..N文字からなる部分文字列について、1..(N+1-L)文字目から始めたものにローリングハッシュが一致するものがあるなら、答えはLである。ローリングハッシュを素数1個で解くとハッシュ衝突が多発してWAするので素数2個にしておくのがよいが、そうするとTLEするのでstd::mapをstd::unordered_mapに変えるとぎりぎりTLEしなくなる。

ABC 142-D

コードはこちら

素因数分解も頻出である。コードスニペットとして用意してテストしておく。

解法としては、AとBを素因数分解して、AとBに共通の素因数の数である。理由は以下の通りだが、ここまで思いつくに時間が掛かってしまった。

• AとBに共通ではないAまたはBの素因数は公約数にはなれない
• AとBに共通の素因数から同一の素数を含めて複数選んで掛け合わせると、他の約数と素でなくなる

ABC 142-E

コードはこちら

Bit DP

動的計画法の縦軸に鍵、横軸に宝箱が開いたかどうかのビットパターンを $2^N$ 個置く。鍵で宝箱が開くかどうかもビットパターンで管理する。これをDPで解く。

初期値は鍵を全く使わず、箱が全く開いてないときのコスト $DP[0][0]$ が0。箱が一つでも開いているときのコスト $DP[1..][0]$ は無限大とする。

鍵 $i$ を使って宝箱が開くビットパタン $b_i$ があったとき、鍵 $i$ 未満を使って宝箱が開くビットパタン $p$ について宝箱 $q = b_i \lor p$ の宝箱が開いた状態になる。鍵 $i$ を使って宝箱 $q$ が開いたときのコスト $DP[i][q]$ は、

• 鍵 $i$ をコスト $a_i$ で使い $DP[i-1][p] + a_i$
• 鍵 $i$ は使わず $DP[i][q]$

のうち小さい方である。これをすべての $p$ について解いて $DP[i][0..2^N-1]$ の最小値を求め、すべての鍵について解くと、 $DP[any][2^N-1]$ の最小値が答えである。 $DP[M][2^N-1]$ を答えるとWAする。

ABC 142-F

コードはこちら

這うようにしてAC。

解 $G^{'}$ は、サイクルを一つだけ持ち、サイクル以外の辺を持たないグラフである。これはすぐ分かったのだが、TLE, 2 WAs, 1 WAがなかなか取れなかった。

まず頂点2の解はすべての辺を調べれば分かる。逆方向の枝があればそれが解である。

それ以外はDFSで探索する。DFSで頂点を一つずつ追加し、解の候補に追加した頂点をたどるならループである。最短のループを切り出して解の条件を満たすかどうか調べ(これが無いと1 WA)、解なら出力する。

最短のループを切り出すのがまさに答えであったと、公式解説を読んで分かった。上記の方法以外に思いつかなかったが、実はBFSで 求まる 。

ABC 143-D

コードはこちら

変数の順序を固定すると、重複なく数え上げできる。 $N$ の大きさから、 $O(N^2 * log(N))$ はいけるだろう。

一般性を失わずに $a \leq b \leq c$ と置く。三角不等式 $c < a + b$ を満たすなら、残りの三角不等式の残り二つも満たす。

• $a \leq b < b + c$ から $a < b + c$
• $b \leq c < a + c$ から $b < a + c$

$a$ と $b$ を固定して $c$ が何個あるか数える。 std::vector の要素を指すイテレータが先頭から何番目にあるか(距離 $d$ )は、 std::vector::begin() との差として定数時間で求まる。 std::distance() を使ってもよい。

const auto d = std::max(0LL, static_cast<Num>(
  std::lower_bound(nums.begin(), nums.end(), s) - nums.begin())
    - second - 1);

ABC 143-E

コードはこちら

ワーシャルフロイド法だと思って時間を溶かした。制約を深読みし過ぎである。

正解はダイクストラ法である。 $N$ 箇所の町それぞれから他の町への最短距離 $N^2$ 組を求めて、クエリに答える。このとき、直接つながる二つの町の距離が $L$ より長い時はその道は使えないので、なかったことにする。

出発する町 $S$ から他の町 $U$ を経て、 $U$ の隣町 $V$ までの距離 $D$ (燃料消費)は、ダイクストラ法で以下の通り更新する。

• $D_S = 0$
• $D_V = D_U + dist(U, V) if \lceil D_U / L \rceil = \lceil (D_U + dist(U, V)) / L \rceil$ 。これは町 $U$ で給油せずに $V$ に到達できる場合である。
• $D_V = L\lceil D_U / L \rceil + dist(U, V) if \lceil D_U / L \rceil < \lceil (D_U + dist(U, V)) / L \rceil$ 。これは町 $U$ で給油しないと $V$ に到達できない場合である。

と思ったら解説を読んで、無給油でたどり着ける町同士をコスト1のグラフにして、ワーシャルフロイド法で 解ける と分かった。これは思いつかない。

ABC 144-D

コードはこちら

実数解を求める問題は、解析解を求めるより、二分探索による絞り込みが有効な場合が多い。

角度を上げる=より多く傾ける程、容器の中身がこぼれるのは明らかなので、単調関数として二分探索できる。水面が底辺と側面のどちらにあるかを場合分けすればよい。

円周率の定義 M_PI は、もしかしたら下記のマクロとインクルード文が要るかもしれない。

#define _USE_MATH_DEFINES
#include <cmath>

ABC 144-E

コードはこちら

二分探索である。

何を探索するかが重要なのだが、ここではチーム全体の成績とする。まず自明に言えることとして、最もコストの高い人を最も食べやすいものに割り当てるのが最適である。よってコストの降順、食べにくさの昇順にソートする。ソート後のコストと食べにくさのマッチングを $A_i$, $F_i$ としておく。

次にチーム全体の成績 $s$ で二分探索する。このとき成績が $A_i * F_i$ が $s$ ちょうどにならないのだが、実は気にしなくていい。成績 $s$ を決め打ちして食べにくさ $F_i$ のとき、求められるコストは $x = \lfloor s/y \rfloor$ である。よってメンバ $i$ を修行する回数は $max(0, A_i - x)$ である。これをすべての $i$ について足すと修行する回数になる。

修行する回数が $K$ より大きければ成績が高望みだったので成績の範囲を上半分(値が大きい方)を選び、そうでなければ下半分を選ぶ。答えは二分探索が収束したときの区間の右側 (修行する回数が $K$ 以下)である。

ABC 145-D

コードはこちら

二次元DPするには $X$ と $Y$ が大きすぎる。なので不変量に注目する。それと到達可能条件に注意が要る。

• ナイトが移動した前も後も、x座標+y座標は3の倍数である。
• なので $X+Y$ が3の倍数でないマスには到達不能である。
• Xにできるだけ少なく移動するなら毎回+1移動する。このときYは毎回+2移動する。なので $Y > X * 2$ なら $X$ に達しても $Y$ に達しない。同じく $X > Y * 2$ ならYに達してもXに達しない。どちらも ( $X$, $Y$ ) に到達不能である。 これに注意しないとWAする。
• 上記を除いた ( $X$, $Y$ ) には到達可能である。

$min(X,Y)$ に移動する方法は、1移動するか2移動するかの順列の組み合わせである。

• 移動する回数は $n = (X+Y) / 3$
• 毎回1移動するので、2移動する回数は追加分 $k = min(X,Y) - (X+Y) / 3$
• よって移動する方法は ${}_n \mathrm{C}_k$

ABC 145-E

コードはこちら

ループの内外が重要である。

最適な答えが求まっていて食べる皿の集合が固定なら、限られた時間では食べるのに掛かる時間が短い皿から食べるのが最適である。よって食べるのに掛かる時間が短い順に、時刻 $0..N$ までに得られる美味しさの最大値を動的計画法で求める。

このときループの内外が重要である。外ループを皿 $1..N$ に、内ループを時刻 $0..T$ にする。これを逆にするつまり外ループを時刻、内ループを皿にすると、食べた皿を覚える手間が増えるだけでなく一問WAする。

ABC 146-D

コードはこちら

126-D, 138-D と同様に、木の頂点をBFSでたどるときに何を載せるかである。今回は辺の色を載せる。

• 無向グラフの辺を std::vector<std::vector<Num>> に載せるのはいつも通り
• 辺を塗るために、辺の始終点から辺の番号への連想配列を作る。キーは from + to * (n+1) にする。
• 頂点の次数(つながっている辺の数)を記録する。最大の次数が必要なの色数である。
• 次数が最大の頂点からBFSする。親頂点とつながっている辺(根を除く)以外の色を、子頂点との辺に塗る。

ABC 146-E

コードはこちら

落ち着いて境界値を探る。

$K$ で割った余りが要素の数と等しいことから、部分列の長さは最大 $W=min(N,K-1)$ である。ここで1引くのを忘れてなかなか正解できなかった。

要素 $S$ の和を $K$ で割った余りが要素の数と等しいこと $(\sum S) mod K = |S|$ を言い換えると $(\sum (S-1)) mod K = 0$ である。よって $A_i$ は入力から1引いた数として、 $A$ の累積和を求めて、部分列 $S$ の和 $mod K$ が0になる区間を求める。

最初に $1..W$ について、左からの累積和を $mod K$ が $r$ となる数が何通りあるか $T[r]$ を数える。左端 $i=1..N$ について以下を繰り返す。累積和を取っていない要素の右端を $R = W+1$

• $U = \sum_{1}^{i} A_i$ とする。累積和なのであらかじめ求めておく。
• $(\sum_{L}^{L+W} A_i) mod K = 0$ の組み合わせの数は $T[U]$ である。これを答えに足す。
• $T[U]$ を1減らして、以後 $[A_1,...A_i]$ を数えないようにする
• $R \leq N$ なら $V = \sum_{1}^{R+1} A_i$ として、 $T[V mod K]$ を1足す。その後 $R$ を1増やす。

これらの和が答えである。

ABC 146-F

コードはこちら

DPを諦めることも重要。

DPで $O(N^2)$ は無理そうなので、貪欲法を考える。ルーレットの目は大きいほどよい。なぜなら単に大きすぎる目を出しても、その次の目を小さくすれば済むからである。なのでゲームオーバーマス以外で、距離 $1..M$ の最も遠くの目に飛べばよい。

出目の列が辞書順で最小である、という条件を満たすにはゴールからできるだけ大きな目で飛んで、スタート近くを小さな目で飛べばいい。後ろから考える。

ABC 147-C

コードはこちら

$N$ が小さいので $2^N$ の総当たりでいける。

証言に矛盾が無いときの、正直者の最大値を答える。

ABC 147-D

コードはこちら

Nim数の発想は、2進数で桁が異なるものを独立に扱うことであった。

$A_{1..N}$ について、ビット $pos$ が立っているかどうか調べる。

• $A_i$ のビット $pos$ が立っているかどうかを、二次元配列 $board[i][pos]$ に入れる
• $A_{1..N}$ のビット $pos$ が立っている個数の合計を、一次元配列 ${nbits}[pos]$ に入れる

こうすれば $i=1..N$ について、

• $A_i$ のビット $pos$ が0なら、 $A_{i+1..N}$ のビット $pos$ が、1である個数
• $A_i$ のビット $pos$ が1なら、 $A_{i+1..N}$ のビット $pos$ が、0である個数
• 2進数で桁に対応する係数 $2^{pos}$

の個数と係数を掛けたものを足すと答えが求まる。 $board[i][pos]$ は $i$ を更新するごとに減らす。

二次元配列としては様々な実装があり、添え字検査が必要なら boost::multi_array がよい。要素を一括設定できる。

ABC 147-E

コードはこちら

$A,B$ の制約が小さい。

$D_{i,j} = A_{i,j} - B_{i,j}$ の差だけに意味があるので、差を累積する。差が取りうる値は $(H+W-2) \times max(A,B)$ なので、 $S = 2^{14} = 16384$ 種類あれば十分である。差は正にも負にもなるので、差が無い時に $C = 2^{13}$ なるように下駄を履かせる。

後は左から右、上から下に向かって動的計画法で、ある差を取りうるかどうか調べる。上と左にセンチネル座標0があると仮定すると場合分けが楽になる。

• 初期値は $DP[][0..W][0..S-1] = false$ 、ただし差0について $DP[0][1][C] = true$ とする。
• 外ループ $y=1..H$ 、内ループ $x=1..W$ について、 $DP[y][x][i \pm D_{y,x}] = DP[y][x-1][i] \lor DP[y-1][x][i]$ である。ただし $i \pm D_{y,x}$ は範囲外なら無視し、 $DP[y]$ の部分は今更新している行と前の行だけ持って、それ以前の行は忘れてよい。

$DP[H][W][i] = true$ を満たす $i$ について、 $|i - Center|$ の最小値が答えである。

ABC 148-D

コードはこちら

先頭から見て最初に見つけた1を残し、次に見つけた2を残し... を繰り返す貪欲法で解ける。なぜなら最左の1を残した方が、それより後に出る1を残すより、次の2を残せる余地が高まるからだ。

ABC 148-E

コードはこちら

10の倍数=2の倍数かつ5の倍数

奇数系列は2の倍数を含まないので答えは0である。

偶数系列は5の倍数かどうかだけ調べる。10未満なら答えは0、10以上なら素因数5の数より素因数2の数が多いので素因数5の数を求める。これは $N/2$ にルジャンドルの定理を適用すれば求まる。 N % 2 と N & 1 はどちらかに統一して混ぜない(どのみちこの除算のコストを気にしても仕方ない)。

ABC 148-F

コードはこちら

証明が長い。詳しくこちらの記事を参照。

LCA (Lowest Common Ancestor) を使う必要はないが、294-Gで使うので用意しておくとよい。

ABC 149-D

コードはこちら

一次元DP(動的計画法)を、複数のスロットを用意して更新する。鉄則本の力試し問題 C09: Taro's Vacation と同様である。

ここでは直前にグー、チョキ、パーを出した時の得点を用意する。グー、チョキ、パーそれぞれについて、K回前とは異なる手は2通りあるので、どちらか得点が高い方を選んで、今回の手で得た得点を足す。前述のC09で、前日に勉強したら今日は勉強しない、と同じことをしている。

実装上は以下の点に注意する。

• i回目のジャンケンで、i<Kなら前の手は無いので何を出してもいい
• i mod K回目が同じK通りについて動的計画法を解いて、K通りの得点を足す。なぜならi mod K回目が異なるジャンケンは、出す手が互いに影響しないからである。

ABC 150-D

コードはこちら

整数を因数分解するときは、因数分解が可能である(整数の積で表現できる)ことだけでなく、因数分解の式が条件を満たすことを確認する。 $a=b*d$ を $a/d=b$ に変形できるのは $d \ne 0$ が条件という話である。

最小公倍数(LCM)は推移則 $lcm(a,b,c) = lcm(a,lcm(b,c))$ が成り立つ。C++には std::lcm と std::gcd が用意されているので自作する必要はない。

ここまでくれば $X$ は $lcm(a_{1..k})$ の最小公倍数の、奇数倍であると分かる。Xが何個あるからは、 $\lfloor a_{i}/lcm(a_{1..k}) \rfloor$ である。ここで $X$ が $a_{1..n}$ の奇数倍であることを 確認し忘れるとWAする。