コンテストに参加した教訓をまとめていきます。最近はARCに参加し、ABCへのrated参加は見送り中です。

トップページへ 前のABC 参加記へ ARC 参加記へ

コンテスト52回目は ARC 185 である。このARCで稼いだレーティングがABC 2回で無くなった。

コンテスト53回目である。A,B,C,D 4完の大敗である。

コードはこちら

問題文をそのまま実装する。下手に工夫すると解けない。

コードはこちら

A,C,D問題を解き、E問題を諦めてからB問題を解いたので、パフォーマンスが大きく下がった。先にB問題を解けば、大敗も少しはましだったかもしれない。

正しく場合分けをしようとしてWAした。 $NQ \leq 10000$ なので全探索というかシミュレーションでよかった。B問題だということをすっかり忘れていた。

正しく場合分けすると こう 実装する。

• 左手を0, 右手を1として、いま操作する手を $A$ 、いま操作しない手を $B = 1-A$ とする
• 時計回りにみて、 いま操作する手 $A$ を、手を動かす先 $T$ 、操作しない手 $B$ の順番に並んでいるかどうか確かめる。これは以下のどちらかである
  • 原点をまたがない。 $A < B \land A < T < B$
  • 原点をまたぐ。 $A > B \land ((A < T) \lor (T < B))$
• $A,T,B$ が時計回りに並んでいるなら $A$ を時計回りに $(N + T - A) mod N$ 移動する。そうでなければ反時計回りに $A$ を時計回りに $(N + A - T) mod N$ 移動する。
• 移動した手の座標を $T$ で更新する

公式解説2に従い、状況を整理すると こう なる。

• 左手を0, 右手を1として、いま操作する手を $A$ 、いま操作しない手を $B = 1-A$ とする
• $A$ の座標が0になるような相対座標として、座標 $T^{'} = T$ と手 $B^{'} = B$ の座標を定める
• $(0 < ) T < B$ なら $A,T,B$ が時計回りに並んでいるので $T^{'}$ 移動する。そうでなければ反時計回りに $A$ を時計回りに $N - T^{'}$ 移動する。
• 移動した手の座標を $T$ で更新する

コードはこちら

考察が甘かったが、提出したら通ってしまった。

左からおもちゃが連続して箱に収まる最大値 $L$ 、つまり $\forall i \in [1,L], A_i \leq B_i$ を満たす最大の $L$ を求める。同様に右から連続しておもちゃが箱に収まる最大値 $R$ 、つまり $min(\forall i \in [N-R+1,N], A_i \leq B_i$ を満たす最大の $R$ を求める。一個もおもちゃが収まらないときは0とする。

$L + R < (N-1)$ なら、おもちゃ $[L+1,N-R]$ を収めるには追加の箱が1個では足りないので、答えは -1 である。そうでなければ箱に収まらないおもちゃのうち最も大きいものに追加の箱をあてがうので、答えは $B_{N-R}$ である。

ここまでは順調に見えたが。

コードはこちら

SCC (Strongly Connected Component) ライブラリに通したら答えが合わない。よく考えたらSCCはループを含むが単一ループだけから構成する訳ではない(複数のループを行き来できる)のだから、通る訳がなかった。

仕方がないのでDFSしたらTLEした。最短距離をDFSするとTLEすると後で読んだが、痛い教訓だった。公式解説はBFSだが、どうして私はDFSで書いてTLEしたのか分からない。素直にダイクストラ法すればよい。遷移先が頂点0なら、頂点0までの最短距離を更新してその探索はそれ深堀りしない。BFSで実装すると こう なるが、ダイクストラ法と実行時間はあまり変わらない。

コードはこちら

最初に間違った解法を示す。以下Greedyだと入力例が通るがWAの山が返る。つまりサイズ $K$ の集合 $S$ に対して要素 $i = (A_i,B_i)$ を付け加えて

• $A$ が最大の要素を取り除く
• $B$ が最大の要素を取り除く
• 要素 $i$ を取り除く、つまりそもそも付け加えなかったことにする

としたら正解ではなかった。 $A,B$ を昇順にソートしてもだめだった。

正しい解法を示す。 $(A_i, B_i)$ を $A$ の昇順 ($A$ が同じなら $B$ の昇順)に並び替え、一つずつ $S$ に追加する。こうすると $max(\sum A_j) : j \in S$ が最後に追加した $A_i$ になる。その後、上から $K$ 番目に大きい $B$ を除く。こうすると $\sum B_j : j \in S$ を逐次更新することで $A_i \times \sum B_j : j \in S$ も更新できる。 $S$ を $(A_i, B_i)$ と、それ以外の $K-1$ 要素からなる集合にすると分かりやすい。

この 実装 では、最後に追加した $A_i$ をすぐ除いたときは $max(\sum A_j) : j \in S$ が過大になる。しかしそのときはその前の操作が答えなので問題ない。コンテストの後にこの解法を思いついたが時すでに遅し。

B問題が解けずD問題がTLEのままE問題を解き始め、2完で終わる訳には行かないので途中で諦めてD,B問題に移った。残り14分で攻略できなかったのも痛かった。考察力が足りないというより、どの問題をどういう順番でどれだけ時間を掛けるか、進行がぐだぐだである。今回は前回と異なり、E問題を見限ってD,B問題に行ったが決断が遅すぎた。

一年ぶりにrated参加しなかった。A,B,C 3完の大敗である。いつになったら戻れるのか。

コードはこちら

$S$ を昇順にソートして、 ABC かどうか調べる。

コードはこちら

コマを置くたびに、置いたコマとその上下左右を塗りつぶす。

コードはこちら

コマを置くたびに、置いたコマと周辺8コマを std::set<std::pair<Num,Num>> に追加する。重複を数えない。

コードはこちら

何時間掛かったか分からないが解けた。コンテストには全然間に合わない。

$1 \leq left \leq M$ について、対になる右端 $right$ を一つずつ数える。注目すべきは、区間 $[L,R]$ であって、 $left \leq L$ の区間のうち、最も小さい(左側にある) $R$ である。これを $right$ とおく。 $L < left$ な区間は無視して構わない。

• このような $right$ が存在するなら、区間 $[left, left..right-1]$ は他の区間を完全には含まない。この .. は両端を含む。
• このような $right$ が存在しないなら、区間 $[left, left..M]$ は他の区間を完全には含まない。

このような $right$ を求めるにはセグメント木を使う。セグメント木の添え字を区間の $L$ とする。セグメント木の値 $tree(L)$ を、左端が $L$ なすべての区間の最小 $R$ (そのような区間が無ければ $M$ )とする。こうすれば上記の $right = tree(L)$ とできる。

なぜこんなに時間が掛かったのかさっぱりわからない。

公式解説の通り実装すると こう なる。尺取り法っぽく解こうとして失敗した。

コードはこちら

サイクル分解までは分かったが、その先 $2^K$ が全く分からなかった。ダブリングで解くと思ったら、この問題の構造がダブリングそのものだった。

解説を読んでなお、 atcoder::pow_mod を自作しようとして失敗した。自作power実装は こちら 。

翌朝バチャで解いた。100分間で解けたのは　A,B,C,D 4完と今一つの出来である。F問題は自力ACしたが、E問題を捨てて残り時間をF問題に全振りすべきだった。

コードはこちら

同じ数字 $X$ が $C$ 回出たら、操作を $\lfloor C/2 \rfloor$ 回できるので、その合計を求める。

コードはこちら

変数名の付け方が悪くて自分自身が混乱した。

ゴミの種類 $k = t_j$ として、収集周期において今何日目か $r_j = d_j MOD q_k$ とする。 $r_k \geq r_j$ なら同じ周期に回収されるので $r_k - r_j \geq 0$ 日後、そうでなければ次の周期に回収されるので $r_k + q_k - r_j$ 日後である。

コードはこちら

B問題の答えが合わないので先にC問題を解いた。

連想配列 $x,p$ は、値 $x$ が $A_i$ に出現したときの最後の添え字(なければ -1 )とする。この連想配列の中身を答えてから更新する。すぐ解けたので落ち着いてB問題に戻った。

コードはこちら

$HW4^K$ 解法を全探索しようとして思いとどまった。解説を読んで、 $HWK43^K$ 解法だったと知り、わずかな違いでTLEを逃れた。

スタート地点を $HW$ 通り全探索する。スタート地点から経路長=深さが $K$ 周のBFSを行う。キューに載せるのは、現在地 $(r,c)$ と、これまで訪れたマス $visited$ である。マスの番号を $(r-1)W + (c-1)$ として、 $visited$ を std::bitset<128> にすると速く解ける(103 msec)。

$1..K$ の反復で、元のキューにあるマスから1歩進む(マス外と障害物以外に行ける)場所を新たなキューに積み、新旧のキューを std::swap する。深さ $K$ 周の後のキューの長さが答えである。 DFSすれば メモリ使用量は問題ないしBFSより速いが(47 msec, 3680 KB) 、BFSでキューが延びていくのはまずかったかもしれない(それでも103 msec, 5368 KB)。

コードはこちら

$mod M$ をセグメント木に載せて、 $M$ を超える桁あふれをどうにかすることは察したが、それ以上何もできなかった。公式解説にある通りである。この種の問題が解けないのはちょっとまずいが、どう対策するか。

コードはこちら

入力例しか合わなくて困った。単純グラフでないグラフを数えたのが蛇足だったのだが、気づくまで1時間以上掛かった。

ある次数2の頂点 $i$ : 1個以上の次数3の頂点 : 次数2の頂点が頂点 $i$ を含めて $K$ 個、という連結グラフを考える。次数2の頂点同士を結べば題意を満たすので、このグラフについては $K(K-1)/2$ 通りの答えがある。

これを頂点 $i=1..N$ について繰り返す。次数3の頂点は一度訪れたら二度数えないように印をつける。

次数2の頂点同士が連結している場合、それらを結べば次数3の頂点から成るループにはなるが、単純グラフではない。これを理解できなくてご丁寧に数えた結果、入力例以外を全部WAした。基本方針があっているのに入力例以外が全滅することは、ABCでは珍しい気がするが今回はそういうテストケースだった。

翌朝バチャで解いた。100分間で解けたのは　A,B,D 3完とぼろぼろである。C,F問題にかまけて、E問題を選び損ね、C問題に半日かかった。

コードはこちら

Leading 0sがないので文字列にして並び替える。添え字を間違えていきなりWAした。

初めから文字列として読めばいいし、 std::rotate を使えば添え字を間違えにくい。実装は こちら 。

コードはこちら

O が $L$ 連続していれば $\lfloor L/K \rfloor$ 回食べられる。今回は大文字である。

コードはこちら

右側つまり $N$ の大きな側のマスにある石から順に配っていく。位置 $X_i$ にある $A_i$ 個の石を配る。石を配り終わっていない区間を $R=N$ で初期化する。

• 石を配る区間 $[X_i, R)$ を追加する
• それより右側に配る。配るときはできるだけ右側にから先に配る。 $X_i$ にある石を $[Y_i, Y_i+W)$ に配るコストは、 $W (Y_i - X_i) + W(W-1)/2$ である。
• 石を左側には配れないので、配り切れなかった石は捨てる
• $R = X_i$ に更新する

と解ける。石の数が合計しして $N$ なら解けないのだが、これを忘れたために半日溶かした。

公式解説はとてもエレガントである。そして石の数が合計しして $N$ なら解けないのも自明である。石が正確に $N$ 個と解っていれば石の行先は一意なので、もっと単純な実装がありえる。公式解説通りにすると こちら 。

コードはこちら

下駄を履かせる。

クエリが来た時点での時刻を $A$ (初期値0)とする。植物を植えてからの補正付き経過時間を、多重集合 std::multiset<Num> $S$ で管理する。

• クエリ1が来たら、 $M$ に $X = -A$ を追加する。つまりクエリが来た時点の $A$ に、追加した時刻 $X$ を足すと、その植物を植えてからの経過時間が $0$ であることを意味する。
• クエリ2が来たら、 $A$ に $T$ を足す。
• クエリ3が来たら、高さが $H$ 以上の植物を収穫する。 $M$ の要素 $X$ について、現在の高さは $X + A$ であり、植物を植えた時刻を $B$ とすると $A - B$ であることと一致する。

クエリ3は $H - A$ 以上の要素を数えて削除する。直観的には、 $M$ を固定して、時刻を進めることを $A$ を減らすことで表現する。 std::multiset<Num>::lower_bound(h-a) から std::multiset<Num>::end() までイテレータを回して植物を収穫し、収穫した数を答える。

公式解説にある通り、単なるキューでよかった。後で植えた植物が先に植えた植物を追い越すことは無いので、上記の実装はオーバースペックである。キューなら下駄の履かせ方に 悩まない 。

コードはこちら

F問題をLISであっさり解けると思ったのが大間違いで、実はE問題の方が簡単だった。

入力例から察することができるように、答えの1桁目は $S$ の $i$ 桁目を $i$ 回足したもの、つまり $\sum_{i=1}^{N} i S_i$ である。同様に答えの $j$ 桁目は、 $S$ の $i$ 桁目を $max(0,i-(j-1))$ 回足したもの、つまり $\sum_{i=1}^{N-(j-1)} i S_i$ である。 $iS_i$ の部分が共通なので $N$ 回の操作で逐次的に求めることができる。

$\sum_{i=1}^{N} i S_i$ の累積和を逆順にしたものを $C_i : i=1..N$ とする。 $C_i$ の $i$ 桁目が答えの $i$ 桁目である。ただし $C_i$ は10を超えることがあるので、下の桁から繰上げて各桁を10未満にし、もう繰り上げる桁がなくなったら答えである。答えを上の桁から順に出力する。

コードはこちら

右側つまり $N$ の大きな側のビル $i$ からLISを求めると思ったら全然違った。公式解説にある通り、セグメント木とスタックで求める。過去問の教訓がちっとも生きてない。

翌朝バチャで解いた。100分間で解けたのは　A,B,C,D,E 5完と久々の復調、レーティングを上回るパフォが出た。

コードはこちら

数字を文字列として扱うことを覚えた。 123 が文字として出現する回数を数える。

コードはこちら

ランレングス圧縮である。連続する - を数え、 | を見たらそれ以前の連続する - を答えに積む。最初の | についてはそこまで0連続なので無視する。

コードはこちら

再びランレングス圧縮である。連続する 1 の変化点を数える。 $i$ 回目に 1 以外から 1 になる場所を $L_i$ 、 $i$ 回目に 1 から 1 以外なる場所を $R_i$ とする。 $[R_{i-1},R_i)$ を、 $L_i$ が先頭になるように $S$ を std::rotate で回転する。

コードはこちら

$K$ を1引いておき0-based indexingで考える。

$W = |S|$ 単位で考える。 $K mod W$ 文字目を $C = \lfloor K / W \rfloor$ 単位に繰り返した時、大文字小文字が反転するかどうか考える。反転する回数は $C$ を二進数表記したときに立っているビットの数である。なぜなら立っているビットは、 $log_{2}C$ 回の入れ子操作において、反転する箇所に対応するからである。

よって $C$ の立っているビットを std::popcount で求め、 $C$ が偶数なら $K mod W$ 文字目をそのまま出力し、奇数なら大文字小文字を反転して出力する。

コードはこちら

マージテクだと分かったが実装に手こずった。データ構造を最初に定める。座標と色は 0-based indexingにする。

• Union-find木 $T$ は、隣接するマスが同じ色なら連結成分にする
• マスの集合 $G_i$ は、 $T$ の代表元 $i$ に属するマスの番号である。最大値と最小値が分かるよう、 std::set にする。最大値と最小値だけ分かればいいので std::set は実行効率が悪いが、マージテクでもTLEしないので今回はそうした。
• 色の集合 $C_i$ は、 $T$ の代表元 $i$ の色である。
• 色の集合 $S_i$ は、色 $i$ に塗ったマスの数である。色 $i$ に塗ったマスは連続するとは限らないことに注意する。

あとは色を塗ったらマージテクすればよい。

• マスを以前と同じマスで塗った場合は無視する。そうでなければ以下を行う。
• マスの連結成分について、連結成分の代表元を $i$ とし、連結成分の大きさを $W$ とする。以前の色 $S_{C_{i}}$ から $W$ 引き、新しい色を $S_{c}$ に $W$ 足し、 $C_i = c$ にする
• マスの前後について、同じ色 $c$ なら合併する。つまり $T$ で連結し、 $G_i$ を合併する。小さな集合を大きな集合に加えてから空集合と交換する。

$x$ を含む代表元が、クエリが来る前、左側のマスを合併、右側のマスを合併、の時点で異なることがある。このときマージテクの常套手段である std::swap は、空集合と交換した後に自分自身を交換すると、間違って空集合が最終結果になる。これらを間違えて2ペナ出してしまった。

そもそも集合をマージテクするのではなく、最大最小値を マージすれば この種のバグは防げた可能性がある。

コードはこちら

可能手を全探索するしかないと分かったが、バチャ中に実装が終わらず、翌日になっても2 WAsが取れず諦めた。他の方の実装を見てもやはり可能手を全探索するしかないのだが、どこで実装を誤ったのか分からなかった。

このゲーム木は先手と後手が同じ状態にたどり着く可能性を考慮する必要がある。よってゲーム木というよりforestである。例えば初期状態 $[(2),(3),(1)]$ から $[(),(2),(1,3)]$ にたどり着くが、 $[(1),(3),(2)], [(1),(2),(3)]$ 経由だと後手、 $[(),(3),(1,2)]$ 経由だと先手である。

そのため盤面管理は、部分ゲームで勝つかどうかをキャッシュする。部分ゲームの一手先で後手必敗なら、この部分ゲームは先手必勝、そういう状況がなければこの部分ゲームは後手必勝である。手札を入れ替えて一手先を考えれば、今どちらの手番なのか考えなくてよくなる。というより先手と後手が同じ状態にたどり着く可能性があるので手番を考えてはならない。

コンテスト54回目は ARC 187 である。1問も解けずに終わったが、解ける問題がA問題しかなかったので、ABCと違って迷いが無く最後まで気分が落ち着いた。翌朝バチャで解いたABC 380がまあまあだったのは、2時間コンテストに集中する感覚を取り戻したかもしれない。

翌朝バチャで解いた。100分間で解けたのは　A,B,C,D 4完と今回もぼろぼろである。その後E問題を自力ACした。

コードはこちら

問題文の条件を読み違えて早速1ペナした。文字列が奇数長かどうかは調べないと分からない。後は0-based indexingに注意して題意通り調べる。

コードはこちら

A問題と違って、文字列が偶数長かどうか調べた。後は0-based indexingに注意して題意通り調べる。

コードはこちら

最初に / の位置を全部調べる。それぞれの / の位置から 12 を左右に広げられるだけ広げて、最も広い幅が答えである。同じ文字は左右から併せて最大2回しかみないので $O(N)$ である。

コードはこちら

着想はよかったがデバッグで苦しみ、12ペナ72分掛かった。

0-based indexingで考える。隣り合う数字が同じ $A_{2i} = A_{2i+1}$ という状況が何回続くかをランレングス圧縮する。ラン $(L,W)$ は、 $i=0..(W-1)$ について $A_{2(L+i)} = A_{2(L+i)+1}$ が成り立つことを示す。左端を元々の $A$ の偶数番目と奇数番目の両方について考える。奇数番目は std::rotate で1個分左シフトして $N$ を1減らせばよい。答えの初期値を $ans = 0$ とする。

あるラン $(L,W)$ について、答えは $2W$ を超えない。 $i=0..(W-1)$ について、いま注目している数字 $a = A_{2(L+i)}$ が既出なので区間を短くしなければならないかどうかに注目し、尺取り法で求める。

ランをみるとき、区間の左端を $G = -1$ で初期化する。またある数 $a$ が最後に出た位置を $T[a]$ とする(まだ出ていないなら-1)。ある $i$ について $G = max(G, T[a])$ で更新する。この $max$ を忘れてバグの山を築いた。次に答えを $ans = max(ans, i - G)$ で更新する。その後 $T[a] = i$ で更新する。

すべてのランについてのすべての状況の最大値が $2 \times ans$ 答えである。この方法は公式解説1と同じである。

コードはこちら

セグメント木に載せようとして数十分を無駄にした。

最初に / の位置を全部調べる。この位置の集合を $P$ とする。次に、 $T$ の先頭から 1 が出現した回数の累積和を求める。1-based indexingで $i$ 文字目までの累積和を $C1_i$ とする。同様に $T$ の先頭から 2 が出現した回数の累積和 $C2$ を求める。

クエリ $L,R$ について、区間 $[L,R]$ に / がなければ答えは0である。少なくとも一つ以上の / があるとして、最適な / の位置を二分探索する。

$p \in [L,R]$ について、 $p$ より左側にある 1 の数は $B1_p = C1_{p} - C1_{L-1}$ 個である。 $p$ より右側にある 2 の数は $B2_p = C2_{R} - C2_{p}$ 個である。 $B1_p$ は $p$ に対して単調増加、 $B2_p$ は $p$ に対して単調減少なので、 $D_P = B1_p -B2_p$ も単調増加である。よって $D_p$ が負から非負に変わった位置を $j \in P$ とする。より厳密には $P$ に含まれ $L < k < j$ を満たす最大の $k$ があるとき、 $D_{k} < 0 \land D_{j} \geq 0$ を満たす $k$ ともしあれば $j$ とする。

/ の候補 $c$ として、 $min([L,R]), k, j, max([L,R])$ がある。それぞれについて11/22文字列長を $1 + min(P1_c, P2_c)$ で求め、それらの最大値が答えである。 $k,j$ が範囲外にならないように気を付ける。

この方法は公式解説2(別解)と同じである。

コンテスト55回目は ARC 188 である。B問題を26分17秒で解いて黄パフォ、青diffをACしたのは初めてだった。ABCよりARCの方が明らかに高いパフォである。

翌朝バチャで解いた。100分間で解けたのは　A,B,C,D 4完と今回も今一つである。F問題を捨ててE問題を解いたら100分に収まらず(その後自力ACした)、捨てたF問題の方がはるかに簡単だった(その後自力ACした)。相変わらず確率DPも試合運びも下手である。

コードはこちら

. が $A$ 個、 @ が $B$ 個あることを数えて、 $A + B - D$ が答えである。

コードはこちら

$S$ を右から順にみて、最大 $D$ 個の @ を . に置き換える。

コードはこちら

美食度 $A$ の人の最小の添え字 $i$ をセグメント木 $T[A] = i$ に載せる(該当者がいなければ $T[A] = \infty$ 。おいしさ $B$ の寿司を食べるのは $T[0,B]$ の最小値( $\infty$ なら -1 )の人である。同じ美食度の人が複数いたら最小の添え字 $i$ の人が総取りすることを自然と表現できる。

公式解説通りに実装すると このように なる。

コードはこちら

全列挙を求められているので、DFSで求める。制約は以下の通りである。DFSすれば自然と辞書順になる。

• 問題文通り $A_{i-1} \leq A_i$
• 問題文に加えて $1 \leq A_{i-1} + 10 \leq A_{i} + 10(N-i) \leq M$

コードはこちら

基本方針はすぐ立ったが、計算量を削減するのに手間取って100分に収まらなかった。

1パックを開けた時に、レアカードが $0..N$ 枚増える確率を $P[0..N]$ とする。このとき0枚増えると計算が大変なので、1枚以上増える確率を $S = 1 - P[0]$ と定める。

レアカードが $i$ 枚ある状態になる確率を $DP[i=0..(N-1)]$ とする。初期値は $DP[] = 0$, $DP[0] = 1$ である。DPの途中で求まる累積期待値を $E$ とする。 $from=0..(X-1)$ についてDPの漸化式で更新する。

• $NextDP = DP$ とする
• $E$ に $S \times DP[from]$ を足す。つまり $from < X$ なら結果はどうあれ $S$ パック引くので、 $DP[from]$ になる確率を掛けてから足す。
• $added = 1..N$ とする。レアカードは $to = from + added$ 枚になる。 $to \geq X$ ならレアカードがそろったので何もしない。そうでなければ $NextDP[to]$ に $DP[from] \times P[added] \times S$ を足す。つまり遷移前の状態にいる確率 $DP[from]$ に遷移する確率 $P[added] \times S$ を掛ける。0枚引く遷移を削除したので $S$ を掛ける必要がある。
• $DP$ を $NextDP$ で置き換える

上記の反復は $O(NX)$ 回であり、反復が終わったときの $E$ が答えである。

コードはこちら

E問題に熱中するあまり、F問題の方が簡単なのをすっかり見過ごした。問題選びの失敗は何度目だろう(バチャで他人の正解者数を見ていなかったのもあるが)。

問題文をみてすぐに、遅延セグメント木 $T$ に載せればいいと分かる。列 $c$ に置かれた最上(番号が小さい)のバーの行番号を $T[c]$ とする。そのようなバーがなければ $H+1$ とする。

区間 $[C, C+L)$ を占めるバーは、既に置いてあるバーについて区間 $[C, C+L)$ の最も上にある(番号が小さい)行を $r$ としたとき(なければ $H+1$ )、 $r-1$ に置く。これは $T.prod([C,C+L])$ で求まる。

ここまで分かれば、すべてのバーを $R$ の降順にソートして、バーを上記の通り置き、遅延セグメント木を $T.apply([C,C+L], r-1)$ で更新する。

コンテスト56回目は ARC Div. 2 189 である。1問も解けずに終わった。あと一歩で正解だったが、その一歩が遠い。

バチャではなく、各問題をdiffを知った上で解いた。

コードはこちら

最後に給水した時刻と初期値を $L = 0$ 、最後に給水したときの水量を $S = 0$ とする。

$i$ 回目の給水時に、水量は $A = max(0, S - (T_i - L))$ である。ここに給水して、 $L = T_i$, $S = A + V_i$ になる。 $N$ 回の給水が終わった後の $S$ が答えである。

コードはこちら

$O(H^3W^3)$ の総当たりで求める。

コードはこちら

問題を解く前にBFSという言葉がちらっと見えてしまったが、どう考えても加湿器を始点として全方位BFSするしかなさそうである。

BFSの順番を誤るとTLEする。ある床について、ある加湿器からの距離が短い=残り到達可能距離が長いときは、それより短い加湿器は無視してよい。この優先順を自然に達成するには、残り到達可能距離 $D..0$ の順番にBFSする。

• それぞれ加湿器のあるマスをキューの初期メンバにする
• キューから加湿器または床 $F$ を取り出す。このとき残り到達可能距離を $L$ とする。 $C$ の上下左右それぞれの加湿器または床 $T$ について、 $T$ の残り到達可能距離が $L-1$ より短ければキューに $T$ を入れる。そうでなければ他の加湿器がカバーしているのでキューに入れない(入れるとTLEする)。
• この探索は、ある加湿器または床について上下左右から見る4回しか行わないので、計算量はマスの数 $O(HW)$ である

実装上のテクニックとして、ある床の残り到達可能距離を std::optional<Num> にする。値として、加湿器は $D$ 、壁は $\infty$ 、床の初期値は値無しで上記の反復で値を書き込む。値が書き込まれて値が $\infty$ ではない非負なマスの数が答えである(壁は無限大)。

コードはこちら

C++の力でごり押しした。

最初にエラトステネスの篩で、 $2..2000000$ の約数を求める。もしかしたら事前に求める方が早いかもしれない。

答えは平方数しかないので、 $i=2..2000000$ について $i^2 \geq N$ になる $i^2$ が答えの候補である。 $i$ が平方数なら、 $1とi$ を含む $i$ の約数が5個なら $i^2$ はちょうど9個の約数を持つ。 $i$ が平方数でなければ、 $1とi$ 以外の約数を掛けて $i$ を超えなければ $i^2$ の約数である。 $i$ の約数が5個を超えたら早めに打ち切るとぎりぎりTLEしない。

素因数の数から約数の数を求めるのをすっかり忘れていた。

コードはこちら

最小重みとくれば、MSTをクラスカル法で作る。そこにマージテクを使う。

マージするのは、頂点の連結成分 $u$ の代表元に、 $A$ に属する頂点の数(重複あり)、 $B$ に属する頂点の数(重複あり)を持たせる。これは $i$ を代表元とする各連結成分について $f(A,B)$ が未定な頂点の数であり、 $CA_i$ は $A$ が未定、 $CB_i$ は $B$ が未定とする。初期値はそれぞれの頂点が独立な連結成分なので、 $A_1, ..., A_k$ の数である( $v = A_i$ なら、 $CA_v$ に1加える)。

クラスカル法通り、重みの小さい辺から大きな辺の順でグラフ $(u,v,w)$ を連結する。

• $u,v$ がすでに連結されていれば何もしない
• $u$ の代表元を $U$ とし、 $v$ の代表元 $V$ とする。 $U$ を含む連結成分について、 $f(A,B)$ が未定な $A,B$ を減らせるだけ減らす。つまり $S = max(min(CA_U, CB_V), min(CA_V, CB_U))$ 減らす。
• 細かく言うと、 $min(CA_U, CB_V) \geq min(CA_V, CB_U)$ なら $S = min(CA_U, CB_V)$ であり、 $CA_U, CB_V$ の一方は必ず0になり、他方は0以上になる。 $min(CA_U, CB_V) < min(CA_V, CB_U)$ も同様。
• 答えに $wS$ を足す。
• $u,v$ を連結し、連結後の代表元を $T$ とする。 $CA_T = CA_U + CA_V$ , $B_T = CB_U + CB_V$ とする。この部分がマージテクである。

コードはこちら

DPを二段持つ。

色 $C$ を固定し、同じ色の商品だけをDPで更新することを考える。 $DP[T][B]$ を、購入金額の合計が $0 \leq T \leq X$ で、同じ色の商品を購入前なら $B=0$ 、購入済なら $B=1$ のときの最大効用とする。初期値は $DP[][] = 0$ である。

色 $C$ の商品について、 $DP$ の遷移先を $Next = DP$ で初期化し、商品ごとに $from=0..X$ について $Next[to \leq X][1] = max(Next[to][1], DP[from][0] + U_i + K, DP[from][1] + U_i)$ で遷移する。1商品遷移し終わったら $Next$ を $DP$ にする。

同じ色の商品について一通り遷移したら、 $DP[from][0] = max(DP[from][0..1])$ とする。つまり次の色の商品を未購入の状態にリセットする。

答えは $DP[][]$ の最大値である。

翌朝バチャで解いた。100分間で解けたのは　A,B,C,D,E 5完だが遅すぎる。F問題は解けなかった。

コードはこちら

for(auto&& c : s) の使いどころである。

コードはこちら

問題文の通り、レーティングを更新するかしないか判断しつつ実装する。私にはDiv. 1が遠い。

コードはこちら

31人と読んだ瞬間 $2^5-1$ 通りを全列挙すると分かったが、題意を理解するのに時間が掛かった。

$1..31$ を二進数で解釈して、ビット 0..4 が立っていたら A..E を正解したという文字列 $S$ と得点 $T$ を計算する。後は $(-S, T)$ の昇順に $T$ を出力する。

D問題のほうがE問題より簡単かもしれないと思った。しかしE問題の名前を見て、ARC 189-Dを4日掛かって解けなかったことを思い出して、ムキになってE問題から解いた。

コードはこちら

周回問題は二周するという典型がある。つまり最初に $A_{1..2N} = A_1, ..., A_N, A_1, ..., A_N$ と並べて、累積和 $C_{i=0..2N} = \sum_{j=1}^{i} A_j$ を取る。

一周したときの和 $W = \sum_1^N A_i$ は1回以上何回でも加算できる。よって $S$ を $S mod W$ に置き換える。 $S=0$ ならきっちり周回すれば作れる値なので Yes である。ここを間違えて1ペナした。

$S > 0$ については、 $A_{1..N}$ を起点に値を作れるかどうか調べる。 $A_1$ が起点なら累積和 $C$ そのものなので、 $C$ の中に $S$ があれば Yes である。 $A_i$ が起点なら、 $C$ の中に $C_{i-1} + S$ があれば Yes である。そのようなものが見つからなければ No である。

コードはこちら

何を思ったか優先度キューに載せて2ペナを出してしまった。同じマスを何度もキューに載せたらそうなる。

始点から吸収したスライムをUnion-find木で連結成分にまとめる。現在のスライムの大きさを $C = S_{p,q}$ で初期化する。マスの $(y,x)$ スライムを吸収するごとに $C$ に $S_{y,x}$ を加えて、Union-find木で $(p,q)$ と $(y,x)$ をマージする。

計算量を減らすように吸収するマス群 $S$ を管理する。 $(p,q)$ の連結成分 $U$ の上下左右のうち、まだ吸収していないマスだけを持てばよい。 $S$ を std::set<Num,Num,Num> 型にして、マス $(S_{y,x}, y, x)$ を持つ。重複なしの順序集合にする必要があり、優先度キューにすると同じマスを何度もキューに載せてしまう。

最初は $(p,q)$ の上下左右を $S$ に載せる。

1. 候補つまりある時点の $U$ の上下左右について、 $S$ の弱いスライムから順に吸収する。吸収したスライムを $V$ とする。
2. スライムを吸収したら、 $U$ と $C$ を更新する
3. これ以上吸収できなくなったら、 $V$ の上下左右のマスを候補に加える。ただしすでに吸収したマスは加えない。
4. 上記1,2,3を繰り返して、これ以上吸収できなくなったら終わる。

吸収できるスライムは、 $C / X$ 未満だが、整数演算の境界に気を付ける。乗算だとオーバーフローするので、除算で求めた。

• $C$ が $X$ の倍数なら $C / X - 1$ 以下
• $C$ が $X$ の倍数でなければ $\lfloor C / X \rfloor$ 以下

コードはこちら

Trailing zeros ($A$ を $2^k$ で割り切れて $2^{K+1}$ で割り切れないときの $K$) が等しい数をひとまとめにする、ということは分かった。Trailing zerosが異なる数を足すとこの $K$ は小さい方になるが、Trailing zerosが等しい物を足したときの $K$ を求める方法を上手く考えられなかった。

公式解説2のコードを写経しながら書いた。 std::unordered_map<Num,Num> を std::map<Num,Num> にするとTLEする。

バチャではなく、一問ずつ解いた。

コードはこちら

何を思ったか $A,B,C$ をグループ分けする方法を総当たりしようとした。A問題がそこまで重いはずはなく、 $A \leq B \leq C$ にソートして、 $A = B = C$ または $A + B = C$ なら Yes 、そうでなければ No である。

コードはこちら

問題文通り実装する。 $X,Y$ が直感と逆なので入れ替える。周囲は壁なのでセンチネルを作らなくてよい。

コードはこちら

調和級数とは分かったがとても苦労した。

高さが異なるビルたちはそれぞれ独立に考えてよい。ある高さのビルの位置の集合をを $S$ とする。ビルの間隔 $W = 1..(N-1)$ を決め打ちして求める。

$x \in S$ について尺取り法で求める。

• $S$ のうち、まだ見ていていないビル $U$ で最も左にある(位置が小さい)ものを $x$ とする。 $U$ の初期値は $S$ である。
• $x, x+W, x+2W, ..., x+iW,$ とみていき、そのように連鎖するビルが $S$ にある限り、答えを $i+1$ を増やしていく。同時に、すでに見たビルを $U$ から除いて、以後は見ないようにする。
• 上記の連鎖が途切れたら、最初に戻って、まだ見ていていないビルを見る。これをすべてのビルを見るまで繰り返す。

あるビルが連鎖の一部なら、左から来た連鎖で数えられているはずなので、上記の通りでよい。

公式解説を見たら、 $W$ の剰余で場合分けすればよかった。確かにそれは思いついたが、どうして上手く実装できなかったのだろう。

コードはこちら

C問題よりずっと簡単だった。

まだ訪れていない家の座標を、 $X$ を固定した $Y$ の集合、 $Y$ を固定した $X$ の集合と二重に持つ。 std::map<Num,Set> で管理する。 $X$ を変えずに $Y$ 軸方向に移動するときは、始終点の間(両端を含む)にある家を集合から削除し、何軒削除したか数える。

コードはこちら

問題の意図をなかなか理解できなかった。

ユ木の定義から、ユ木は直径が2または4であることがわかる。 $T$ の直径が2なら必ず $x=1$ のユ木である。星形ともいう。これを見落として 3 WAsが返ってきた。以下直径を4にすることを考える。

直径が4と決まっているので、ある頂点 $v$ を木の根を決め打ちする。 $v$ の隣接頂点群 $S$ があり、 $u \in S$ の次数をそろえればユ木になる。これをすべての頂点 $v$ について試し、最小値が答えである。 $v$ が葉(次数1)なら無視する( $T$ の直径が2のときはすでに求めた)。

$S$ に次数が $D_i$ の頂点が $K_i$ 個あるとする。 $D_i = 1$ の頂点は必ず取り除かなければならない( $y > 0$ より、そうしないとユ木にならない)。すべての $D_i$ について、 $S$ の次数を $D_i$ にすることを試す(それ以外の選択肢は中途半端で使えない)。

• $S$ の次数 $D_i$ 未満の頂点 $u$ とその先の頂点を全部削除する
• $S$ の次数 $D_i$ 以上の頂点 $u$ について、 $D_i$ を超える分の辺を削除する

このとき残る頂点の数は、根の分が1個、根に隣接する頂点が $C = \sum_{j=i} K_i$ 個、葉が $C \times D_i$ 個なので、 $1 + C(1 + D_i)$ 個である。よって取り除く頂点数は、 $N - 1 - C(1 + D_i)$ 個である。すべての頂点の、すべての $D_i > 0$ について求めると答えである。この方法は、結果的に直径が2になる場合を含む。

探索回数は辺の数なので、計算量は $(D_i,K_i)$ の連想配列を作るのがボトルネックで $O(Nlog(N))$ である。

公式解説は全探索だった。確かに削除後の木の頂点数は、 $1 + x + xy$ なのでこの性質を使えないかと思ったが、それ以上考察が進まなかった。

二分探索だと思ったらそうではなかった。

翌朝バチャで解いた。90分29秒で A,B,C,D を解いた。遅すぎる。

コードはこちら

2枚あるカードが2種、または、1枚あるカードが1種かつ3枚あるカードが1種、なら Yes 、そうでなければ No である。

コードはこちら

文字列 $S$ の長さを $N$ とする。ボタンを押す回数は $N$ 以下である。 0 で続く長さ $L$ のランがあるたびに、 $\lfloor L/2 \rfloor$ 回だけ、ボタンを押す回数が減る。

コードはこちら

$S,T$ の文字列の長さ $|S|, |T|$ が等しいとき、異なる文字が高々1か所なら Yes である。

$S,T$ の文字列の長さが2以上異なるときは No である。

$|S| + 1 = |T|$ とする(そうでなければ $S,T$ を入れ替える)。 $S,T$ を先頭から見て、連続して一致する文字数が $L$ 個とする。 $S,T$ を末尾から見て、連続して一致する文字数が $R$ 個とする。 $L + R \leq |S|$ なら $S,T$ の違いは一か所なので Yes 、そうでなければ No である。

コードはこちら

基本方針はすぐわかったが、実装をまとめるのに1時間以上掛かった。

マス $(r,c)$ が B であるとは、行 $r$ について、黒いマスの左端を $c$ より小さくできないということである。問題文の $i$ について、 $i$ の最小値が $c$ といえる。

マス $(r,c)$ が W であるとは、行 $r$ について、黒いマスの左端を $c-1$ より大きくできないということである。問題文の $i$ について、 $i$ の最大値が $c-1$ といえる。

上記を基に、行 $r$ における $i$ の最小値がもしあるなら $minR_r$ 、最大値がもしあるなら $maxR_r$ とする。

最初に同一行に矛盾がないことを確認する。ある行 $r$ について、 $minR_r > maxR_r$ なら行 $r$ を塗る方法がないので答えは No である。以下同一行は塗れるとする。

行番号を昇順に調べる。最初は列 $(cmin, cmax) = (-\infty, \infty)$ を塗れるとする。行 $r$ について $minR_r$ があり、 $cmax < minR_r$ なら行がギザギザしていて、 $cmax + 1$ 列を二分で塗り分けられないので答えは No である。そうでなければ $cmax$ を $min(cmax, minR_r)$ で更新し、上の行よりも同じか左の列を黒く塗る。こうして最後の行まで塗れるかどうか確かめる。

念のため列に対しても同様のことをする。最後まで塗れたら Yes である。

コードはこちら

2 TLEsまできたがそれ以上わからず諦めた。

$K$ 個の数値として、先頭から0個以上飛ばして $P_1$ 個目を選び、0個以上飛ばして $P_2$ 個目を選び、を繰り返すと $N \choose K$ 個取れる。探索しながら累積XORすればよい。はずなのだが、DFSでやってもBFSでやってもTLEが取れない。

公式解説にある通り、 $2K > N$ なら $K$ を $N - K$ に読み替えるとTLEしない。このときは選ばなかった $N-K$ 個の $A$ のXORを導出するのに、 $N$ 個全部の $A$ のXORと、 選んだ $K$ 個の $A$ のXORをXORして導出する。

編集距離を長さ $|S|K$ のスライディングウィンドウで求めればいい。はずなのだが、7 WAsが取れない。

翌朝バチャで解いた。100分間で解けたのは　A,B,C 3完である。パフォを度外視して、とにかくC問題を解けるまで取り組んだらD問題が間に合わなかった。

コードはこちら

問題文通り実装する。

コードはこちら

問題文通り実装する。

コードはこちら

典型的な桁DPである。これが解けないのはまずいと思い、D問題以降を無視して解けるまで時間を掛けた。

$i$ 以下のヘビ数は $i$ に対して広義単調増加である。よって $i$ 以下のヘビ数を $C_i$ として、 $C_R - C_{L-1}$ が答えである。

$C_i$ の求め方を考える。 $i$ が10進数で $W$ 桁のとき、 $1..(W-1)$ 桁ですべての数値が 9 であるような数 $N$ に対してヘビ数を求める。次にちょうど $W$ 桁の数について、 $100...0$ 以上 $i$ 以下の数についてヘビ数を求める。これらの合計が答えである。

以下 $C_i$ についてちょうど $W$ 桁の場合の求め方を示す( $W$ 桁未満も同様に求まる)。 $C_i$ の最上位桁を $D$ とする。最上位桁が $T = 1..D$ の場合について求める。

$T < D$ であれば、 $[T0..0, T9...9]$ のすべての値が候補になる。よってヘビ数は $D^{W-1}$ 個ある。 $T = D$ であれば桁DPらしく解く。上から $j = 2..W$ 桁目について、 $j$ 桁目の数値を $p$ として以下の通り繰り返す。

• $j < W$ かつ、 $p \geq D$ なら、以後の桁はすべて $0..(D-1)$ にしても $C_i$ を超えない。よってヘビ数の合計に $D^{W-j+1}$ を足してループを打ち切る。
• $j < W$ かつ、 $p < D$ なら、以後の桁はすべて $0..(p-1)$ にしても $C_i$ を超えない。よってヘビ数の合計に $D^{W-j}$ を足す。 $j$ 桁目を $D-1$ にした場合は $C_i$ を超えるかどうかは後の桁を見ないとわからないので、 $j + 1$ 桁目を見る。
• $j = W$ なら、 $min(D, p+1)$ を足す

9 を並べるところの考慮が難しく、いつまで経っても入力例1が通らなかった。

コードはこちら

C問題に時間を掛けすぎて間に合わなかった。というよりコンテストなら先にD問題を解くのが普通である。

よくある方向別DPである。

$DP[y][x][d=0..4]$ を、マス $[y][x]$ に方向 $d$ からたどり着いたときの最小移動回数とする。初期値は $\infty$ とする。方向は上下左右を0123、スタートマスつまり静止状態を4とする。

あとは優先度キューに距離、マスの位置、移動方向の組 $(Dist,Y,X,Dir)$ を載せて、キューが空になるまでBFSする。最初にスタートマス $(0,SY,SX,4)$ を載せる。隣のマス $nextY,nextX$ に移動方向 $nextDir$ で行ける条件は、マスの外に出ない、隣が障害物マスではない、縦横の移動が連続しないことなので、これらの条件をすべて満たし、かつ $DP[nextY][nextX][nextDir] > Dist + 1$ なら移動する。 $DP[nextY][nextX][nextDir] = Dist + 1$ として $(Dist+1,nextY,nextX,nextDir)$ をキューに載せる。

$min(DP[GY][GX][])$ が答えである。ただし $\infty$ なら -1 と出力する。

この方法は公式解説にある、言い換えを用いない方法である。

コードはこちら

タイムラインからなんとなくヒントが見えた可能性があるが、下記の方針とは全く異なるので自力AC扱いにする。

ARCのようなアドホック問題である。最初に少ない桁、 $N$ が5桁以下 $N < 10^5$ を総当たりで求める。 $N < 10^6$ でも十分早い。 $N$ が小さいときはそのまま答えにしてよい。 $N$ によっては解無し -1 になることがある。

ここで興味深いのは、 $a$ と $a+1$ の桁が異なる数として、 $(9,10), (999,1000)$ が見つかる。この直感から、 $a$ が9または27の倍数のとき $a+1$ を10の倍数にすればACできそうである。

数 $i$ について、 $i$ の桁がある条件なら $i$ は $d$ の倍数である、という条件を定める。これ以外に $i$ が $d$ の倍数という状況もあるが、答えを一つ挙げるためには取り立てて考える必要はない。

• $i$ の桁和が3の倍数なら、 $i$ は3の倍数である
• $i$ のすべての桁が3の倍数で、桁和が27なら、 $i$ は27の倍数である。これは各桁を3で割って、桁和が9なら9の倍数であることからわかる。
• $i$ が偶数なら、 $i$ は2の倍数である
• $i$ の最下位桁が0なら、 $i$ は10の倍数である

$N$ の最上位桁について、 9..1 の順に場合分けして答えを求める。 $2N$ の最上位桁は $N$ の最上位桁だけで決まり、下の桁は影響しないことに注目する。もう少し正確に言うと、 $N$ より $2N$ のほうが桁数が大きいときは $2N$ の上位2桁、 $N$ と $2N$ が同じ桁数のときは $2N$ の上位1桁は、 $N$ の最上位桁1桁の倍になる。 0...0の部分は1桁以上とする。こうしたくて、 $N$ が5桁以下の数を、下記の規則から除外した。

• 9 : 桁数を一つ増やして、 10..010 が答えである。こうすると 10..010 は2の倍数、 10..011 は3の倍数なので題意を満たす。9の倍数でも27の倍数でもないが、下記を考えていると思いつく。
• 5..8 : 桁数は同じで、 90..099 が答えである。 90..099 は27の倍数、 9..100 は10の倍数なので題意を満たす。
• 4 : 60..0399 が答えである。 60..0399 は27の倍数、 60..0400 は10の倍数なので題意を満たす。
• 3 : 27の倍数を作るため、場合分けが要る
  • a = 30..0699 が候補の一つである。 $N \leq a$ なら $a$ を出力する。 $a$ は27の倍数、 $a+1$ は10の倍数なので題意を満たす。
  • $N > a$ なら b = 60..0399 が答えである。 $N < b < 2N$ かつ $a$ は27の倍数、 $a+1$ は10の倍数なので題意を満たす。
• 2 : 360..099 が答えである。 360..099 は27の倍数、 360..100 は10の倍数なので題意を満たす。
• 1 : 場合分けが要る
  • a = 10..010 が候補の一つである。 $N \leq a$ なら $a$ を出力する。 $N$ の最上位が9で、桁を繰り上げないときに相当する。
  • $N > a$ なら b = 20..0 が答えである。 $N < b < 2N$ かつ 20..0 は2の倍数、 20..1 は3の倍数なので題意を満たす。

アドホックな求め方であるが、これでACする。公式解説1と公式解説2を足して2で割ったような解法である。27の倍数判定法は知らなかった。

より簡単な解法として、桁和が8の8の倍数を、桁和が9の9の倍数にする方法を読んで知った。1000が8の倍数であることに注意する。 $N$ が6桁以下の場合は全探索し(5桁だと1 WAする)、それ以外は以下の通り。実装は こちら 。

• 7..9 : 桁数を一つ増やして、 107 の後に0を続ける
• 2..6 : 桁数は同じでそれぞれ、 305, 404, 503, 602, 701 の後に0を続ける
• 1 : 1070..0 より多ければ 206 の後に0を続ける。そうでなければ 1070..0 にする。

計算量が下がらない。

$x_i \leq x_{A_i}$ の大小関係に対応して、 $i$ から $A_i$ に有向グラフを張る。なもりグラフなので自己ループを含めれるとこのグラフには必ずサイクルがある。サイクル $C$ に含まれる頂点 $v \in C$ について、 $x_v$ はすべて同じ値でなければならない。サイクルに入る木構造のグラフについては、葉からサイクルに向かって非減少ならどんな $x$ でもよい。

有向グラフを逆向きにして、サイクルからサイクル外に向かって、 $x$ を $1..M$ に決め打ちしながらDFSする。サイクルは同じ値を取ることに注意する。DFSで頂点をたどるたびに、値を同じか減少かつ1以上にすればよい。このような値の割り当て方法を数える。

この方法は正しい値を返すがTLEする。メモ化再帰してもTLEは直らない。公式解説には累積和を使って計算量を下げると書いてあるが、まだ理解していない。

バチャではなく、一問ずつ解いた。

コードはこちら

問題文通り実装する。

コードはこちら

問題文通り実装する。

コードはこちら

問題を誤読して、鏡餅は1段以上無限段だと思った。

実際にはそうではなく2段しかない。0-based indexingとして、 $A_i$ に関して、 $A_j > \lfloor A_i/2 \rfloor$ なる最小の $j$ を求めて足せばよい。このような $j$ は尺取り法で求まるので計算量は $O(N)$ である。

コードはこちら

遅延セグメント木なら数分で 解ける ので、ratedなら遅延セグメント木を使うべきである。

いもす法で解ける。宇宙人 $i$ について、もらう石は高々 $i-1$ 個、配る石は高々 $N-i$ 個である。石をもらうときに、配る側の石が尽きていたらもらえないので、このことを正確に把握すれば答えが求まる。

石を配る順番は $1..N$ と固定なので、いもす法に載せる。 $[L,R]$ 番目の人に石を配れるとき、いもす法として $D[R]$ に1加えて、 $D[L+1]$ から1引く。これは $i$ 番目の人が石を $C_i = \sum_{j=1}^{i} D[j]$ 個もらえることを意味する。

あとは $i=1..N$ を逐次的に求める。 $C_0=0$ として $C_i$ を $C_{i-1} + D[i]$ で更新し、 $S_i = A_i + C_i$ は宇宙人 $i$ がちょうど成人したときつまりこれ以上石をもらえないときの石の数である。配れる石の数は $T_i = min(S_i, N-i)$ である。よって答えは石を配った後の残り $B_i = S_i - T_i$ である。

コードはこちら

どうしても解けなかった。緑diffの一割は今でも解けない。

$A_i$ に対して $i=1..N$ の $A_i$ より小さな餅を組み合わせるgreedyは反例がある。 $(1,2,10,11)$ の答えは2だが、1を返してしまう。よって大きな餅から順に相手を探す。実は同様のことが、大きな餅を組み合わせても起こる。以下公式解説2に従う。

$H = \lfloor N/2 \rfloor$ として、大きな餅から順に $i=N..(N-H+1)$ について $A_i$ の相手を探す。 $A_i$ の相手は、 $A_j : j=1..H$ のうち、まだ他の餅と組み合わせていないもので、 $A_j \leq \lfloor A_i / 2 \rfloor$ を満たし、まだ組み合わせていない餅の $j$ である。このような $j$ があれば $(A_j,A_i)$ を組み合わせ、そうでなければ無視する。これを繰り返すと最大の $K$ を得られる組み合わせを作れる。C問題と同様に尺取り法で解けるし、 $O(NlogN)$ の集合操作でもTLEしない。

餅の組み合わせを $i=N..(N-H+1)$ ではなく $i=N..1$ にしたらWAが大量に返ってきた。公式解説2をみるまで分からなかった。どうしてWAなのかわからなかったが、餅の集合をを上限2分割しないと貪欲にマッチングできないと知った。

コンテスト57回目は ARC 190 である。1問も解けずに終わった。Div. 1とはいえ、水diffを解けないのはいただけない。

バチャではなく、一問ずつ解いた。

コードはこちら

問題文通り実装する。

コードはこちら

問題文の制約から、unsigned 64-bit整数でオーバーフローしないので、 $N$ を1から順に試す。

コードはこちら

ヘビの長さを累積和で持ち、列から抜けたヘビの長さ(これも累積和)を引けば求まる。

コードはこちら

直感的にはわかるが、丁寧な実装がいる。

小数を扱うのは大変なので、 $R$ を2倍して、正方形は大きさ $2 \times 2$ とする。

円の対称性に注目して、 $X$ 軸、 $Y$ 軸、第一象限だけを考える。 $Y$ 軸上の正方形つまり $X = [-1,1]$ を占める正方形が収まるかどうかは、 $X = 1$ の $Y$ 軸に垂直な直線について、 $X^2 + Y^2 \leq R^2$ が成り立つ $Y$ である。 $Y > 0$ の範囲だけ考えて、 $Y$ の最大値は $U =\lfloor \sqrt{R^2 - X^2} \rfloor$ である。

よってこの範囲に収まる正方形の数は、

• $U < 1$ なら0個。この処理が抜けていてもACするので、このようなことは起きないかもしれない。
• $U \geq 1$ なら、 $Y > 1$ について $C = \lfloor (U-1)/2 \rfloor$ 個と、 $Y < -1$ について同数 $C$ 個と、 $X$ 軸上の1個の、合計 $2C+1$ 個である。

同様に正方形の右端 $X = 3,5,..,R-1$ について、 $X$ を2ずつ増やして同様に求める。 $Y$ 軸に対称な位置も答えなので2倍した値 $4C+2$ を数える(逆に言うと上記の求め方は $Y$ 軸上の正方形なので1倍した)。これらの和が答えである。

コードはこちら

遅延セグメント木の範囲加算だと思ったが解けなかった。レーティングは単調性が成り立つのだが、成り立たないと誤解していた。 $[L,R]$ にひたすら加算すると単調性が成り立たないと思ったが、よくそうではない。 $R$ から $R+1$ になったらレーティングは加算されないが、 $R-1$ から $R$ を経て $R+1$ になればやはりレーティングは加算されないので、最初にレーティングが低い人に後から追い越されることはない。

ここまで分かれば atcoder::lazy_segtree::max_right で、クエリ後のレーティングを求めればよい。 apply はレーティング加算1だが、 prod は区間最大であり、ここがややこしい。 prod を max_right を行うことを考えれば、確かに区間最大でないと困る。公式解説のコードをほぼそのまま写経して解説ACした。

バチャではなく、一問ずつ解いた。

コードはこちら

問題文を誤読して2ペナした。

任意の二要素ではなく、隣り合う二要素を入れ替える。総当たりしてソート済になるか 調べれば よい。

コードはこちら

$A_1 / A_2 = A_i / A_{i+1}$ が $1 \leq i < N$ についてすべて成り立つなら Yes , そうでなければ No である。 $N=2$ は自動的に Yes になる。除算の誤差を発生させないよう、 $A_1 A_{i+1} = A_i A_2$ で判定する。

コードはこちら

黒マスがある最上行 $T$ 、最下行 $B$ 、最左列 $L$ 、最右列 $R$ の中をすべて塗る必要がある。対角線 $(T,L)-(B,R)$ で定義する長方形(両端を含む)の中に . があれば No , なければ Yes である。

コードはこちら

まぐれでACできてしまう。

集合を std::bitset<32> で管理してDFSすると、たいていTLEするのだが1回だけ 2919 ms で間に合ってしまった。

コードはこちら

見るからに食べ物 $1..N$ をコスト $0..X$ で入手できる範囲の何か、というDPである。そこで $min(A_1,A_2,A_3)$ を載せたらWAが大量に返ってきた。気分転換に掃除して換気して頭を洗っている途中で正答を思いついた。

問題文をよくみたら、一つの食べ物からは一種類のビタミンしか摂取できない。だとすれば、ビタミン $v \in 1..3$ をコスト $0..X$ で摂取できる最大量、という $DP_v$ を設計する。 $v$ はそれぞれ独立である。DPの後、ビタミン $v$ を $s$ 摂取するにために払う最低コストは $x$ であるという集合を、要素 $S_v:(s,x)$ の昇順で持つ。 $DP_v[0..X]$ をみて、コストを多く払うが摂取できる量は少ないという逆転があったら無視する。

こうすると答え $t$ を固定して、ビタミン $v=1..3$ の摂取量を $t$ 以上にできるかという問題に帰着する。これは $t$ を $[0,Nmax(A)]$ の範囲で二分探索すればよい。 $t$ を固定して $S_v$ を二分探索すれば、 $t$ を摂取するための最低コスト $D_{i,t}$ もしくは摂取不可能( $D_{i,t} = \infty$ )なことがわかるので、 $\sum_{i=1..3} D_{i,t} \leq X$ なら $t$ は答えになりうる。そのような $t$ の最大値(0以上)が答えである。

コンテスト57回目は ARC Div. 2 191 である。A,B 2完を103:12の7ペナで、なんとか0完を逃れた。

バチャではなく、一問ずつ解いた。

コードはこちら

NEWS の各文字を SWEN の各文字に対応させる連想配列を作って、 $D$ を一文字ずつ置き換える。

Bashからtrコマンドを呼び出しても解ける。

tr NEWS SWEN

コードはこちら

行と列の始点をそれぞれ $1..(N-M+1)$ に決め打ちして総当たりする。

コードはこちら

差分を更新する。

0-based indexingとして、鳩の位置を $N[i=0..(N-1)] = i$ 、巣にいる鳩の数を $C[i=0..(N-1)] = 1$ 、複数の鳩がいる巣の個数 $A = 0$ で初期化する。クエリ1は以下の通り値を更新し、クエリ2は $A$ を出力する。

• 鳩 $P$ の移動元を $F$ 、移動先を $H$ とする
• 移動前の $C$ を $C_{prev}$ 、移動後の $C$ を $C_{next}$ とする
• $C_{next}[F] = C_{prev}[F] - 1$ 、 $C_{next}[H] = C_{prev}[H] + 1$ である
• $N[P] = H$ とする
• $C_{next}[H] > 1$ を、 $C_{next}[H] > 1$ なら1、そうでなければ0と定義する。他も同様。
• $A$ の差分は、 $(C_{next}[H] > 1) + (C_{next}[F] > 1) - (C_{prev}[H] > 1) - (C_{prev}[F] > 1)$ なので $A$ にこの差分を足す。特に $F = H$ なら差分は0である。

コードはこちら

上にあるブロックが下にあるブロックを追い越すことは無い。よってそれぞれのブロックは独立に、いつ1行目になるか考えればよい。明らかにこれは $Y_i$ であるのだが、0-based indexingがどうか考慮するとややこしい。

ブロックが消える条件は、 $x=1..W$ 列目すべてにブロックをそろえられることである。初期状態において $x$ 列目に $C_x$ 個ブロックがあるなら、ブロックを $H = min(C_{\ast})$ 行消すことができる。 $H = 0$ ならブロックは一つも消えないので、すべてのクエリについて答えは Yes である。以下 $H > 0$ とする。

ブロック $j$ が下から $i$ 番目にあることを $S_j = i$ とする。初期状態において $x$ 列目の下から $i$ 番目のブロック $j$ が $Z_{x,i} = Y_j$ にあるとする。ブロックが $i = 1..H$ 回目に消える時刻 $D_i$ は、 $D_i = max(Z_{\ast,i})$ である。ブロック $j$ は $S_j > H$ なら永久に消えず(便宜上時刻 $\infty$ に消えるとする)、 $S_j \leq H$ なら時刻 $D_{S_j}$ に消える。

クエリに答える。 $T,A$ について、 $T \leq D_{S_A}$ なら Yes 、 $T > D_{S_A}$ なら No である。

コードはこちら

再帰する。

問題文に沿って、部分列 $S$ から $A_1$ を得る操作を $F(S)$ とする。 最初に現状の $F(A)$ を求め、 $F(A)$ を変えた先 $T = 1 - F(A)$ を求める。これは問題文通り、入力を3分割しながら再帰すればよい。

長さが $3^i$ の部分列 $S$ について、問題文の最小変更回数を $G(S)$ とする。

• $i=0$ のときは、 $S=T$ なら $G(S) = 0$ 、そうでなければ $G(S) = 1$ である
• $i > 0$ のときは、 $S$ を長さ $3^{i-1}$ の3つの部分列 $S_1, S_2, S_3$ に分割する。答えは $G(S_1), G(S_2), G(S_3)$ のうち、小さい方から2つの和である。

多数決なので、最小変更回数が最も大きい部分列については一切操作せず無視してよい。なので残りの2つの部分列だけ考慮する。何も操作することなく $T = F(S_1)$ が達成できるなら $G(S_1) = 0$ であり、 $G(S_1), G(S_2), G(S_3)$ を昇順に並べたときに自然と採用する。こうすると $F(S_1), F(S_2), F(S_3)$ が何かで8通りの場合分けをする必要がなくなる。

部分列は左端の添え字と、部分列の長さ $3^i$ で管理してDFSすると、 $A$ をコピーするコストを省ける。メモ化はいらない。

コードはこちら

考えすぎて時間が掛かった。

最初の方針は、解 $T$ を超える数が $K$ 個以上になる方法を考えた。しかしいつまで経っても方針が立たないので、以下の方針に切り替えた。

$A, B, C$ をそれぞれ昇順に並べ、数字の大きなものから組み合わせていく。添え字 $N..1$ の順に使っていく。今注目している $A,B,C$ の添え字を $I_A, I_B, I_C$ とする。

• 優先度キューにタプル $(AB + BC + CA, I_A, I_B, I_C)$ を載せる。いつもと違い、値が大きいほど高優先度つまり最初に取り出す要素にする。
• タプルの最初の値は問題文通り $A[I_A]B[I_B] + B[I_B]C[I_C] + C[I_C]A[I_A]$ を計算することにして以後は明記しない。優先度キューの最初の要素は $(N, N, N)$ を載せる。
• キューから要素を取り出したら、 $(N-1, N, N)$ , $(N, N-1, N)$ $(N, N, N-1)$ を載せる。ただし添え字が1未満になる場合と、キューの長さが $3K$ を超えるときは載せない。

キューから $K$ 番目に取り出した値が答えである。なおキューの長さが $3K$ を超えるときは載せないのを、 $K$ を超えるときにすると 8 WAsが返ってくる。

バチャではなく、一問ずつ解いた。

コードはこちら

$P_{1,2,3} = {1,2,3}$ の順列組み合わせをすべて調べ、少なくとも一つの順列に対して、 $A_{P_1} \times A_{P_2} = A_{P_3}$ が成り立てば Yes である。そうでなければ No である。

コードはこちら

$S = 1..N$ を出現しない数の初期値として、 $A$ の要素を $S$ から取り除く。 $S$ が空のときに、出力の2行目を空行にすることに気を付ける。

コードはこちら

0-based indexingで考える。 $Q$ の逆引きつまりゼッケン $q$ を付けた人が $i$ であるという表を $R[q] = i$ とする。人 $i$ についての答えは $Q[P[R[i]]]$ である。

コードはこちら

問題を誤読して時間が掛かった上、ややこしい実装をしてWAした。

サイコロの組は総当たりしかないので総当たりで調べる。サイコロ $i$ について、出目 $a$ の出現回数が $F_{i,a} > 0$ とする。組にするサイコロ $j (\ne i)$ について、出目 $b$ の出現回数を $F_{j,b}$ とし、 $(\sum_b F_{i,b} F_{j,b}) / K_i K_j$ の最大値が答えである(該当する組がなければ0が答え)。

コードはこちら

方針はすぐ立ったが、実装にすごく時間が掛かった。

サーバーを連結成分に分割する。それぞれの連結成分について木構造のグラフを構築する。そうするとそれぞれの連結成分について、冗長なケーブルが分かるのでそれらを集める。

冗長なケーブルを、他の連結成分とつなぎ変える。連結成分が $K$ 個あるとして、元々の連結成分 $1$ の冗長なケーブルを、まだ連結成分 $1$ とつながっていない連結成分とつなげ、連結成分 $(1,i)$ をマージする。元々の連結成分 $i=2..K$ について、連結成分 $1$ とマージ済ならなにもせず、マージしていなければ連結成分 $i$ の冗長なケーブルを、まだ連結成分 $1$ とつながっていない連結成分 $j$ つなげ、連結成分 $(i,j)$ をマージする。

これを繰り返すとすべてのサーバーが単一の連結成分になる。

コードはこちら

E問題は時間が掛かったのに、F問題はあっさり終わった。

順序付き集合で $N$ 番目の要素を取得できる実装 Policy-Based Data Structures があれば簡単だとすぐわかる。あとはクエリ先読みというかクエリ逆再生を組み合わせる。

答えを $A$ とし、クエリ $N..1$ 番目の順に処理する。 $A$ に数字を置ける場所 $S$ を $S=1..N$ で初期化する。

$N$ 番目のクエリは明らかに $A[P_N] = N$ である。 $S$ から $P_N$ を除外する。同様に $i$ 番目のクエリは、 $A[S[P_i]] = i$ であり、 $S$ から $P_i$ を除外する。ここで $S[j]$ は $S$ の小さい方から $j$ 番目の要素である。ここで Policy-Based Data Structures が役に立つ。

想定解法は数字を置ける場所を Fenwick-treeに載せて二分探索だった。確かにそれでも解けるが、 Policy-Based Data Structures の方が実装は簡潔になる。

セグメント木実装はこちら 。初期値はすべてのノードを1にし、値の置き場所が決まったところから0にしていく。

コードはこちら

解法にまるで見当がつかなかったが、高度典型と呼ばれるものかもしれない。ARC 185-Cを今でも理解できていない。

コンテスト58回目は ARC Div. 2 192 である。74:55 2ペナでA問題だけACして、なんとか0完を逃れたがレーティングは上がった。ABCは解くのが遅すぎてレーティングがどんどん下がるが、ARCは2連続水パフォである。

バチャではなく、一問ずつ解いた。

コードはこちら

入力は4通りなので全列挙すればいい。

敢えて2進数で解く。 fine ならビットを立て、 sick ならビットを立てない。高橋君はビット1 ($2^1$) に対応し、青木君はビット0 ($2^0$) に対応すると、このように構成した数+1が答えである。

コードはこちら

A の開始位置と間隔を全探索すると $O(N^2)$ で求まる。

コードはこちら

問題文通り実装する。すでに見た辺の集合を $S$ とする。辺の要素 $(u, v)$ は $u < v$ とする。取り除く辺の数を $A$ とする。

それぞれの辺 $(U, V)$ について以下の通り処理する。 $N$ は関係ないので0-based indexingにする必要はない。

• $U = V$ なら $A$ に1足して、 $S$ を変えない
• $U > V$ なら $U,V$ を入れ替えて $U < V$ にする。そのあと以下の処理を行う。
  • $(U,V)$ が $S$ に含まれていたら $A$ に1足す
  • $(U,V)$ を $S$ に追加する

コードはこちら

方針はすぐ立ったが、実装に非常に時間が掛かった。ARC 192-Cのような泥沼である。

$p = 1..N$ を決め打ちして、 $p$ の左右から 1 を集める。すべての $p$ についての操作回数の最小値が答えである。

$p$ を含まず $p$ より左にある 1 が $L$ 個あるとする。これを $[P-L,P-1]$ に移動する操作回数を求める。同様に、 $p$ を含み $p$ より右にある 1 が $R$ 個あるとする。これを $[P,P+R-1]$ に移動する操作回数を求める。下記の通り累積和を事前に求めておくことで、 $i$ 1回当たり $O(1)$ 、合計 $O(N)$ で求めることができる。

$S$ に含まれる 1 の数を $K > 0$ とする。 $R = K - L$ である。 1 がある位置の累積和 $C[i] = \sum_{j=1}^{i} j \times S_j$ を求める。そうすると $[P-L,P-1]$ に移動する操作回数は、 $(P-L+P-1)L/2 - C[P-1]$ である。 $[P,P+R-1]$ に移動する操作回数は、 $(P+P+R-1)R/2 - (C[N] - C[P-1])$ である。

連続する 1 の端の場所を決め打ちすると実装がとてもややこしい。この実装方針を間違えたことで長時間掛かった。

1ノルムの和を最小化するには中央値を使うことをすっかり忘れていた。中央値を使うと こうなる 。

コードはこちら

C++の力でねじ伏せた。

$A_1, ..., A_N$ それぞれの約数を求める。ある約数 $F$ が $K$ 個以上あり、 $A_i$ の約数が $F$ を含むなら、そのような $F$ の最大値が $i$ の答えである。同じ数について、約数を1回だけ求める。

本当は調和級数で解くらしいが、上記も一応は想定解法の一つである。 $1..10^6$ の約数を列挙するなら調和級数の方が 速い 。

コードはこちら

D問題と同様、なんとなく方針は立ったが、実装に非常に時間が掛かった。

前処理として $A,X$ を座標圧縮して、これらを最大 $N+Q$ 要素にしておく。

LISの求め方はいつも通りセグメント木を使う。 $A$ を先頭から $1..N$ とみていったときに、 ある長さのLIS $L$ があったとして、 $L$ を達成するために必要な最小の $A$ は広義単調現象である。明らかに、 $A$ の選択肢が増えるほど $A$ は小さいものを選べるからである。

よって $A_i$ のLIS $L$ を求めたら、 $R$ の値が $[A_i, \infty)$ のときに達成できるLISは $L$ 以上であると更新する。これは遅延セグメント木の区間maxを使う。

この処理がTLEしないよう、クエリを先読みして、右端が $R_j$ となるクエリ $P[R_j]$ の要素を $(X_j, j)$ とする。 $r = 1..N$ として、右端が $r$ のとき、 $A_{1..r}$ だけで、 $R$ の値が $[A_i, \infty)$ のときに達成できるLISを前記の方法で求める。ここで $r=R_j$ なクエリに答える。遅延セグメント木 $prod(X_i, \infty)$ の値がクエリ $j$ の答えである。

$r$ を網羅したらクエリの答えもすべて求まっているので出力する。

公式解説はDPの求め方が逆で、LISの長さを決め打ちした時の $A$ の最小値である。

バチャではなく、一問ずつ解いた。

コードはこちら

$S$ の各文字について、 2 なら出力する。最後に改行を出力する。

コードはこちら

$(|S_i|, S_i)$ の昇順に並べ替えて、先頭から $S$ を出力する。

コードはこちら

ARCらしい問題である。

連続する W の直後の A を AC... に置き換える。より厳密には、 $K > 0$ 個の W の直後に A があれば、1個の A と $K$ 個の C に置き換える。

$S$ の先頭から以下のように処理する。 $L$ から連続する W が $K$ 個あるとする。初期値は $L = K = 0$ である。 $S$ の各文字について先頭から見ていき、 $S$ の $i$ 文字目を下記の通り処理する。

• A なら上記の処理を行う。 $K = 0$ なら何もせず、 $K > 0$ なら上記の通り $S$ を置き換える。その後に $K = 0$ とする。
• W なら $K$ を伸ばす。 $K = 0$ なら $L = i$ と設定し $K = 1$ とする。 $K > 0$ なら $K$ を1増やす。
• それ以外の文字なら $L = K = 0$ にする

Rubyなら 短く 書ける。

puts gets.gsub(/(W+A)/) {'A'+'C'*($1.size()-1)}

コードはこちら

いつもの括弧列、つまり () だけの括弧列を考える。文字列 $S$ がこのような括弧列である条件は、 ( を 1 , ) を -1 としたときの累積和を文字列の先頭から求めると分かる。累積和 $C_i = \sum_1^{i} S_i : 1 \leq i \leq |S|$ について、任意の $i$ について $C_i \geq 0$ かつ $C_{|S|} = 0$ が成り立つことと、括弧列であることは同値である。

問題文にある三種の括弧列を考える。 (), [], <> すべてについて、上記の括弧列の条件を満たす必要がある。満たさないものがあれば答えは No である。そのうえで、閉じ記号 )]> は最後の開き記号 ([< に対応している必要がある。これをスタックで求める。

• 開き記号を見つけたらスタックに積む
• 閉じ記号を見つけたら、スタックの最上段に対応する開き記号があるかどうか調べる。あるならスタックの最上段を取り除く。なければ答えは No である。

文字列をすべて処理出来たら答えは Yes である。実はスタック操作だけで解けるらしい。

コードはこちら

ワーシャルフロイド法てきに解く。 $a$ から $b$ へのパス(両端を含む)を構成する回文の最短長を $L[a,b]$ とする。このような回文を構成できなければ $L[a,b] = \infty$ である。

初期状態は、 $a$ から $b$ への直行路(自己ループを含む)があれば $L[a,b] = 1$ 、無ければ $L[a,b] = \infty$ とする。頂点 $c,d$ をパスの両端に加えて、パス $(c,a,b,d)$ について $L[c,d]$ を求める。ラベル $(c,a) = (b,d)$ なすべての組み合わせについて、

• $a = b$ ならパス $(c,a,d)$ の回文長は2(同じラベルが連続する)
• $a \ne b$ ならパス $(c,a,b,d)$ の回文長は $max(L[c,d], L[a,b] + 2)$ (回文の両端に同じラベルを付ける)

と更新する。これを $2N$ 回更新すると答えが求まる。自己ループは必ず0、回文長 $\infty$ を -1 と読み替えて出力する。 $N$ 回だと 2 WAsする。

ワーシャルフロイド法で調べる頂点の組は、回文長が短くなったものに限る。この高速化対応をしないと、After ContestをTLEする。

コードはこちら

概要を思いついて、木の直径を持ち出してからが長かった。

アルカンの炭素原子部分つまり次数4の頂点は、次数4以上の頂点の連鎖である。よって次数4以上の頂点をunion-find木でつなげたものが、少なくとも解の候補になる。次数4以上の連結頂点集合が一つもなければ答えは -1 である。以下、次数4以上の連結頂点集合ごとに答えを求めて、その最大値が問題の答えである。

ある次数4以上の連結頂点集合を $S$ とする。 $|S| = 1$ ならメタンで答えは5である。 $|S| > 1$ なら以下の操作を考える。

• 次数4未満の頂点については水素原子をつなげて次数4にする
• 次数4の頂点は何もしない
• 次数が4を超えるの頂点は答えが最大になるように、隣の炭素原子を上手く選び、残りを刈って捨てる

$S$ は木なので、すべての葉から全探索すれば答えが求まるがそうするとTLEする。探索範囲を狭めるために、 $S$ の直径を求めて、直径を構成する二つの葉 $(u,v)$ を起点とする。なぜなら直径を構成するパスは必ず含めて損しないからだ。なお $(u,v)$ の一方を探索し忘れると2 WAsする。

$u$ から下記のようにDFSして、上記の操作を繰り返し、最も多い木の頂点数が答えである。

• DFSの親(もしあれば)を除く隣の頂点群=各子頂点について、DFSで最も多い木の頂点数を求める。
• 子の頂点数のうち、多い物から順番に採用する。DFSの親があれば3頂点分、なければ4頂点分取る
• 採用した頂点が足りないときは、残りを水素原子で1個ずつ埋める
• 今いる頂点自身を1個分足す

バチャではなく、一問ずつ解いた。

コードはこちら

std::is_sorted をそのまま使うと、広義単調増加なので間違える。一工夫すると 使える 。

std::is_sorted(ns.begin(), ns.end(), std::less_equal<Num>{});

コードはこちら

基本的にチェビシェフ距離だが、場合分けがややこしい。以下座標を0-based indexingとする

• $N$ が奇数なら中心は1点 $\lfloor N/2 \rfloor$ 、 $N$ が偶数なら中心は4点 $(N/2-1,N/2-1)$ である。
• 端までの距離 $H = \lfloor N/2 \rfloor$ について偶奇を求める。 $N$ が奇数ならが $H$ と偶奇が一致するマスを # で塗る。 $N$ が偶数ならが $H$ と偶奇が一致しないマスを '#' で塗る。

コードはこちら

値 $A$ の出現位置の集合を $V[A]$ とする。 $V[A]$ は昇順にする。 $|V[A]| > 1$ の要素のうち、 $1 + V[A] - V[A-1]$ の最小値が答えである。そのような要素がなければ答えは -1 である。

コードはこちら

変換表を作るのだが、大変時間が掛かった。

クエリ2を実行して、引っ越し前の巣の番号 $x$ から引っ越し後の巣の番号 $y$ に変換するテーブルを $F[x]=y$ と呼ぶ。この逆変換、つまり実際の巣の番号 $y$ から引っ越し前の巣の番号 $x$ に変換するテーブルを $R[y]=x$ と呼ぶ。この区別が ARC 192-C 並みにややこしい。

鳩 $i$ が実際にいる巣の場所を、クエリ2の引っ越し前として保持するテーブルを $P[i]$ とする

• クエリ1は、実際の巣の番号 $b$ を与えられて、引っ越し前 $P[a] = R[b]$ を設定する。
• クエリ2は、実際の巣の番号 $a,b$ を与えられて、引っ越し前 $ra=R[a], rb=R[b]$ を得る。ここで $F[ra]$ と $F[rb]$ 、 $R[a]$ と $R[b]$ を一斉に交換する。
• クエリ3は、 $F[P[a]]$ を答える

公式解説はラベル鳩と書いているが、本質的には上記と同じである。他の方の 解説 を基に、問題を言い換える。

• ラベル鳩を鳩の集団と言い換える
• 鳩がどの集団に属するかを $P[a] = x$ とする
• 鳩の集団がどの巣にいるかを $F[x] = y$ とする
• 巣にどの鳩の集団がいるかを $R[y] = x$ とする
• クエリ1は、巣の番号 $b$ を与えられて、 $R[b]$ で鳩の集合を求め、鳩が属する集合を $P[a] = R[b]$ に変える
• クエリ2は、実際の巣の番号 $a,b$ を与えられて、鳩の集合 $R[a], R[b]$ を交換する。その逆 $F[R[a]], F[R[b]]$ も一斉に交換する。
• クエリ3は、巣の番号 $a$ を与えられて、鳩の集合 $P[a]$ が要る巣 $F[P[a]]$ を答える

コードはこちら

D問題よりはるかに簡単である。

頂点を倍化してダイクストラ法で解く。倍化した頂点の番号を、元の頂点番号に $N$ 足したものとする。元の辺と重み $(u,v,1)$ 、逆の辺と重み $(u+N,v+N,1)$ 、反転したとき行き来の重み $(i,i+N,X)$ , $(i+N,i,X)$ を辺とするグラフを作る。頂点1から頂点 $N$ または頂点 $2N$ までの最短距離が答えである。

コードはこちら

やはりD問題より簡単である。

上の歯は削ることはできても伸ばすことはできないので、ある時点で常に最も短い歯を基準に両隣を合わせるgreedyで解ける。

集合 $S$ の要素 $(U[i],i)$ を、ある時点で歯 $i$ が長さ $U[i]$ とする。初期状態では $S$ にすべての歯 $U_{1..N}$ を入れる。 $S$ を順序付き集合として、最も短い歯を取り出して以下の処理を行う。

• 左隣の歯がある $i > 1$ なら、左隣の歯を削る。まず $S$ から $(U[i],i)$ と $(U[i-1],i)$ を取り除く。
  • $U[i-1] - U[i] \leq X$ ならこれ以上何もしない。
  • そうでなければ $D = U[i-1] - U[i] - X$ とする。答えに $D$ を加算し、 $U[i-1]$ を $D$ 減らし、更新後の $(U[i-1],i)$ を $S$ に加える。
• 右の歯がある $i < N$ なら、右隣の歯を削る。方法は上記と同様である。

こうすると歯の凸凹が無くなる。あとは下の歯を削って上下の歯の高さをそろえる。すべての $i$ について、 $U[i] + D[i] - min(U[i] + D[i])$ を答えに加える。

公式解説は全コストを二分探索している。実装すると こう なる。二分探索の予感はしたが、区間判定が大変そうなので避けた。

バチャではなく、一問ずつ解いた。

コードはこちら

問題文通り、添え字に気を付けて実装する。

コードはこちら

あらかじめ0を100個積んだスタックを用意する。

コードはこちら

$B$ を降順に並べ替え、0より大きな要素の数を $L$ とする。 $L$ を求めるとき、 $L$ を可能な限り少ない値として更新しないとWAする。同様に $W$ を降順に並べ替える。

$W$ から取るボールの数を $C=0..N$ 個と決め打ちする。 $0 \leq C \leq min(N,M)$ である。 $W$ から取ったボールの価値は $\sum_{i=1}^C W_i$ である。 $B$ から取ったボールの価値は $\sum_{i=1}^C B_i$ が一つの候補である。 $L \geq C$ なら $\sum_{i=1}^L B_i$ も答えになりうる。このようにして求めた答えの最大値を出力する。ボールを一つも選ばなければ最低値0が得られる。

コードはこちら

DFSで全探索する。9の階乗は362880通りしかない。

コードはこちら

基本方針は立ったが詰めが甘くて解けなかった。

辺が自己ループ $A = B$ であれば、 $Z = 0$ なら無視し、そうでなければ解無しである。なぜなら自分自身のXORは常に0だからだ。

各ビットを独立に考える。 $Z_i$ のビット $j$ についてのみ考え、 $A_i \oplus B_i = 0$ なら、 $A_i$ のビット $j$ と $B_i$ のビット $j$ は等しい。 $A_i \oplus B_i = 2^j$ なら、 $A_i$ のビット $j$ と $B_i$ のビット $j$ は異なる。このことをグラフで表現する。

ビット $j$ が異なる $A, B$ の組=辺についてグラフを彩色して、赤か黒に塗り分ける。塗り分けることができなければ解無しである。これはBFSで分かる。BFSの途中で、塗ろうとした頂点の色がすでに異なる色で塗られている、ビットが等しい頂点同士が隣り合っていると分かれば、塗ることはできない。

次にビット $j$ に限らずあるビットについて $A, B$ が結ばれている辺について、頂点をたどってまだ縫っていなければ同じ色に塗る。

こうするとビット $j$ について、赤、黒、塗っていないのどれかになる。赤と黒と頂点数が少ない方について $A$ のビットを立て、それ以外は $A$ のビットを立てない。

はずなのだが、WAがたくさん返ってくる。諦めて公式解説を見たら、頂点数が少ない方というのは連結成分ごとに数える必要があった。入力例だけではこのことをうっかり忘れていた。連結成分が二つあり、赤と黒で塗ったものが $(2,3)$, $(3,2)$ であれば、正解は4、誤答は5である。

コードはこちら

E問題よりずっと簡単である。

ある $A_i$ が持ち上がって $M-1$ になったとき、 $A_{i+1..N}$ の値 $M-1$ 以外の数をすべて転倒している。次に $0$ になったとき、 $A_{i+1..N}$ の値 $0$ 以外の数をすべて転倒しなくなる。同時に $A_{1..i-1}$ にある $0$ 以外の数に転倒される。この差分を更新すればよい。

具体的には、初期状態の $A$ における転倒数を求める。これはセグメント木で求まる。次に初期状態で値 $v$ を取る $A$ の位置(添え字)の集合を $P[v]$ とする。答え $k=0..(M-1)$ について、以下のように更新する。

• $k = 0$ の答えは、初期状態の転倒数である
• $P[M-1-k]$ の $C$ 個の要素を先頭から順に $P_{i=1..C}$ とする。転倒しなくなる数は $\sum_{i=1}^C N - P_i - (C - i)$ 、転倒する数は $\sum_{i=1}^C P_i - 1 - (i - 1)$ である。この差分を転倒数に足して更新する。

コンテスト59回目は ARC Div. 2 194 である。0完で記録的大敗を喫した。問題選びを間違えた上に、A問題を解けず、勝利には程遠かった。

バチャではなく、一問ずつ解いた。

コードはこちら

0.5は誤差なく表現できるので、浮動小数として扱って構わない。

コードはこちら

i と o の差ではないことが入力例2で分かって助かる。

入場後の状態を1、出場後の状態を0とする。

• i の前は状態0であるべきで、そうでなければその直前に o を1個追加する。文字を追加したかどうかに関わらず状態1にする。
• o の前は状態1であるべきで、そうでなければその直前に i を1個追加する。文字を追加したかどうかに関わらず状態0にする。
• すべて文字列を走査した後は状態0であるべきで、そうでなければ $S$ の末尾に o を1個追加する。これが入力例1からわかって助かる。

文字を追加する操作は必要なく、何文字追加したかを数えて出力する。

コードはこちら

B問題よりずっと簡単である。

std::map は要素の種類数を返す。重複を含めた要素数ではない。 $A$ 全部が入った要素について、ある数が何個あるかのテーブル $R$ を作る。空のテーブルを $L$ とする。 $i=1..(N-1)$ について、 $L$ に $A_i$ の要素数を1増やし、 $R$ から $A_i$ の要素数を1減らす。要素数0のエントリを削除すると、要素の種類数になる。

コードはこちら

すぐ立式できたが、二分探索の範囲を間違えてペナルティを出した。

変数 $p$ を導入して $x = y + p, x > 0, y > 0, p > 0$ とする。式変形すると $3py(y+p) = N - p^3$ になる。よって $p$ を全探索すればよい。 $N$ の範囲から、 $1 < p \leq 10^6$ で十分で、範囲を広げすぎるとオーバーフローする。

$p$ を固定する。 $3py(y+p) = N - p^3$ より、 $N - p^3$ が $3p$ の倍数で無ければ $p$ は解の候補ではない。解の候補なら、 $y(y+p) \geq (N - p^3) / 3p$ を満たす最小の $y$ を二分探索で求める。 $0 < y \leq 10^9$ を探す必要があり、範囲を間違えてペナルティが返ってきた。範囲を広げすぎるとオーバーフローする。

このような $p > 0$ が存在し、かつ整数 $y > 0$ が存在して $3yp(y+p) = N - p^3$ を満たすなら、そのような $y + p$ と $y$ を出力する。存在しなければ -1 を出力する。 $y = 0$ は解ではないが、親切にも入力例から分かる。

実は二次方程式の解の公式で求まる。実装するのが大変なら二分探索でもいい。

コードはこちら

何時間経っても解けなかった。

葉からの距離をたどって、長さ $K-1$ になるパスが見つかったら消す、という方法は上手くいかなかった。公式解説の方法は確かに上手くいくのだが、 $K$ より大きな木を見つけたら打ち切る場合分けが巧妙で思いつきそうもない。

コードはこちら

E問題は解けないがF問題は解ける。

第一の組については、C問題と同様に全探索する。残り二組については、ある数 $a$ を上手く二つの組に分割できる範囲を求めて、そのような範囲がもっともたくさん重なる場所で分割すればよい。

残り二組について、範囲を以下の遅延セグメント木に載せる。

• 数 $i$ の出現位置が0または1か所なら分割不能である。出現位置が2か所以上なら、位置の最小値を $L$ 、位置の最大値を $R$ とする。このとき、真ん中の組 $A_j$ について、 $L \leq j < R$ とすれば、 $i$ を二組に分けられる。
• これを遅延セグメント木 $T$ に載せる。applyを加算、prodをmaxにする。すべての $i$ について、上記 $[L,R)$ にapplyで1加算する。
• prod $[l, r)$ は、 $l \leq j < r$ のときに、分割した $i$ の最大値を数える。要するにどれだけたくさん分割できるかである。

C問題を拡張しつつ、上記の遅延セグメント木を活用する。

• 組1 $(A_1, ... A_i)$ を $S$ とする。重複した要素を数えない。初期状態は空である。
• 組2,3 $(A_i+1, ... A_N)$ に含まれる数が何個あるかのテーブル $U$ を作る。初期状態は $A$ 全部入りである。
• 数 $i=1..N$ の出現位置の集合を $P[i]$ とする。初期状態は $A$ 全部入りである。
• 遅延セグメント木の初期状態は $A$ 全部入りである。 $P$ を基に作る。

分割点 $i=1..(N-2)$ について以下の順に更新する

• $S$ に $a = A_i$ を加える。
• 遅延セグメント木 $T$ の $a$ についての範囲を、あれば取り除く。 $apply(min(P[i]),max(P[i],-1))$ する。
• $U$ から $a$ を1個取り除く。 $U$ から0個になったエントリを取り除く。
• $P[a]$ から $i$ を取り除く
• 遅延セグメント木 $T$ の $a$ についての範囲を、可能なら加える。 $apply(min(P[i]),max(P[i],1))$ する。
• $S$ の要素数、 $U$ のエントリ数、 $prod(i,N-1)$ の和が、答えの候補である。

このような候補の最大値が答えである。

バチャではなく、一問ずつ解いた。

コードはこちら

• $N$ 文字の - を並べる
• 0-based indexingで、 $\lfloor N/2 \rfloor$ 文字目を = にする
• $N$ が偶数なら、0-based indexingで $N/2 - 1$ 文字目を = にする

コードはこちら

$2^7$ は小さいので、計算量のオーダーを気にしない。

7枚のカードを選ぶ、選ばないを $2^7$ 通り全探索する。

• カードが5枚でなければ無視する
• カードが5枚なら、ある数字 $A$ が $C$ 枚ある連想配列 $T : A[C]$ を作る
• $T$ のエントリ数が2以外なら無視する
• $T$ の値 $C$ が2または3であるエントリ $A$ があればフルハウスである。答えは Yes である。

上記で該当するものがなければ No である。

コードはこちら

ある数字 $A$ を持っている人たち $A[P]$ という連想配列 $T$ を作る。 $T$ のキーを昇順に走査し、 $|P| = 1$ となる $A$ の最大値(なければ -1 )が答えである。

コードはこちら

二次元アクションゲームのスクロールを考える。

計算量を減らすために、煙が移動するのではなく、座標系の原点 $(Y,X)$ が移動すると考える。 $S$ の $t$ 文字目が

• N であるとき、座標系が $Y$ 方向に $-1$ 移動する
• S であるとき、座標系が $Y$ 方向に $1$ 移動する
• E であるとき、座標系が $X$ 方向に $-1$ 移動する
• W であるとき、座標系が $X$ 方向に $1$ 移動する

初期値は $Y = X = 0$ である。時刻が経過するたびに上記の通り座標系が変化し、煙が $(Y,X)$ に発生する。

高橋君の居場所 $(R + X, C + Y)$ に煙があるかどうかは、煙の場所を std::set<Num,Num> で管理して、 $(R + X, C + Y)$ が含まれるかどうか判定する。

コードはこちら

処理を間違えたらWAではなくTLEした。落ち着いて再実装したらACした。

題意から任意の二頂点は到達可能であり、距離を定義できる。 $G$ は木なので、直結していない頂点同士を直結すると必ずループになる。頂点 $(U,V)$ の距離が奇数長なら、 $(U,V)$ を直結してできるループの長さは偶数である。偶数なので、他の頂点間の距離が偶数か奇数かには影響しない。単に結べる頂点が減るだけである。

よってすべての頂点の組 $(U,V) , U \ne V$ について、長さが奇数長で $G$ に含まれない辺の集合 $T$ を求める。

$T$ が奇数個なら先手、偶数個なら後手を選ぶ。あとは $T$ の辺を互いに取り合えば勝つ。自分だけでなく相手が取った辺を $T$ から除き忘れるとTLEする。

二部グラフと言われればそうである。

コードはこちら

ローリングハッシュで解ける。自作ライブラリの使い方を思い出すのに苦労した。

$S$ の接頭辞にある最大長の回文を求める。 $S$ の逆順を $R$ とする。 $S$ の後ろ $i = 1..|S|$ 文字と、 $R$ の先頭 $i = 1..|S|$ 文字が一致するかどうか調べ、一致するものの最大長を $L$ とする。 $S$ の末尾の文字と $R$ の最初の文字は一致するので $L \geq 1$ である。

$L$ はローリングハッシュで求まる。ハッシュ衝突に備えて、キーを2つ以上用意する。 $L$ が求まったら、接頭辞 $P = S[1:|S|-L]$ 、回文 $S[L+1:|S|]$ 、 $P$ を反転したものを順に出力する。

Manacherアルゴリズムを忘れていた。ライブラリ化もしていなかったし。

コンテスト60回目は ARC Div. 2 195 である。1完で茶パフォ、これが今の実力である。

久しぶりにバチャで解いた。D問題が全くわからず時間が掛かった。

コードはこちら

$S[i] \ne T[i] : i = 1..N$ な要素を数える。

コードはこちら

Min rankを求める。

得点が $P$ な人たち $T[P]$ という連想配列を作る。 $P$ の降順に出力し、出力した人数の分だけ順位を増やす。

コードはこちら

350点だが典型だった。

入力したグラフを連結成分の集合 $G$ に分ける。それぞれの連結成分を木にすればよく、辺の数は連結成分の頂点数-1である。よって答えは $M - (N - |G|)$ である。

コードはこちら

最初の50分間は全く題意が分からなかった。ペナルティの山を築いて、問題文通り実装すればいいだけと気が付いた。なぜ 71:34と8ペナも掛かったのだろう。

前処理として、人 $a$ の位置の集合を $P_a$ とする。 $|P_a| = 2$ である。人 $a = 1..N$ について、条件に合う相手 $b$ がいるなら $(a,b)$ という組を作る。この組の数が答えである。

条件に合うかどうかは、問題文通り実装すればよい。エッジケースに注意する。 $a=1..N$ について調べる。

• $a$ 同士は隣接していない。つまり $|P_a[1] - P_a[0]| > 1$ である。
• $P_a[0]$ に隣接する要素について、位置の候補 $S$ は $P_a[0] - 1, P_a[0] + 1$ のうち、1以上 $2N$ 以下の要素である。 $2N$ を $N$ と書くと大量にWAする。
• $P_a[1]$ に隣接する要素について、位置の候補 $T$ は $P_a[1] - 1, P_a[1] + 1$ のうち、1以上 $2N$ 以下の要素である
• $S$ のそれぞれの要素 $s$ と、 $T$ のそれぞれの要素 $t$ の組み合わせ最大4通りについて、条件に合うことを調べる。
  • $b = A_s$ とする。 $b$ 同士が隣接する。つまり $|P_b[1] - P_b[0]| = 1$ なら条件に合わない
  • $c = A_t$ とする。 $c$ 同士が隣接する。つまり $|P_c[b] - P_c[0]| = 1$ なら条件に合わない
  • $s = t$ なら交換しないのと同じなので条件に合わない
  • $b \ne c$ なら条件に合わない
  • それ以外は条件に合うので、組 $(a,b)$ を候補に加える。組を一意にするため、 $a < b$ とする。

組の数が答えである。

バチャではなく、一問ずつ解いた。

コードはこちら

$P = 400$ として、 $P$ が $A$ で割り切れれば $P / A$ 、割り切れなければ -1 である。

コードはこちら

任意精度整数 boost::multiprecision::cpp_int を使って計算する。

コードはこちら

なかなか解けなかったが、 $a$ が正であるという制約を見落としていた。

$b$ は奇数であると仮定して構わない。なぜなら $b = 2c$ のとき、 $2^a \times b^2 = 2^a \times {(2c)}^2 = 2^{a+2} \times c^2$ が成立し、これは $c$ が奇数になるまで繰り返すことができるからだ。

まず $b = 1$ を全探索する。これは $N$ を二進数表記した時の桁数 std::bit_width(N) である。 $a = 0$ を除くので1引く。

$a \geq 1$ を、 $2^a \leq N$ の範囲で全探索する。 $a$ を固定すれば $B$ は $C = \sqrt{\lfloor N / 2^a \rfloor}$ のうち奇数かつ1より大きいものであるから、 $\lfloor (C - 1) / 2 \rfloor$ 個である。

これらの総数が答えである。 $b$ は奇数という制約は、公式解説3と同じである。

コードはこちら

入力例3に助けられた。

01-BFSして魚屋までの距離を求める。同方向の移動距離1,2までのマスについて、到達のマスまたは途中のマスに壁があれば距離1を足し、そうでなければ距離0を足す。例えば、 $(0,0)$ から $(0,2)$ に移動するとき、 $(0,1),(0,2)$ の少なくともどちらか一方が壁なら距離1、そうでなければ距離0を足す。 $(0,0)$ から $(0,1)$ に移動するとき、 $(0,1)$ が壁なら距離1、そうでなければ距離0を足す。

01-BFSなので優先度キューは要らないが、C++の力で $log(N)$ 余計に払った。

コードはこちら

C問題はなかなか解法が見えないのに、E問題はあっさり分かった。

クエリの数からして、前処理にたっぷり時間を掛けるべきと分かる。二つの素数 $P,R$ について、 $A = P^{2i} R^{2i} = (P^{i} R^{i})^2$ が成立するならば、 $P^{i} R^{i} \leq \sqrt{A} \leq 10^6$ を満たす最大の $B = P^{i} R^{i}$ について $B^2$ が答えである。

よって二つの素因数の積 $P^{i} R^{i}$ で表現できる数 $B$ の集合をあらかじめ求めておく。 $1 \leq B \leq 10^6$ だけ調べれば十分である。これは $1 \leq P \leq 10^6$ を満たす素数 $P$ を列挙し、それぞれの $P$ について $B$ を $P$ で試し割りすれば $B$ の素因数を列挙できる。

400 numbersを求めるか、400 numbersの平方数を求めるかという違いを除けば、公式解説通りである。

バチャではなく、一問ずつ解いた。考えがまとまらない。

コードはこちら

$\lfloor S/100 \rfloor = 2$ なら Success 、そうでなければ Failure を出力する。

コードはこちら

状態 $in \in {False, True}$ を考える。初期状態は $False$ である。

• login なら $in$ を $True$ にする。前の状態は関係ない。
• logout なら $in$ を $False$ にする。前の状態は関係ない。
• public なら何もしない。
• private なら、 $in = False$ の時に答えを1増やす。 $in = True$ なら答えは変わらない。いずれにせよ状態を変えない。

コードはこちら

累積和だとすぐ分かったが添え字で悩んだ。

$N = 1$ なら答えは1である。このハードコーディングを間違えた。以下 $|A| > 1$ とする。 $A$ の値ではなく累積和 $C_i = \sum_{j=0}^{i}$ を持つ。

• $C_{-1} = 0$ である
• $0 \leq i < K$ のとき、 $C_i = i + 1$ である
• $i \geq K$ のとき、 $C_i = C_{i-1} + C_{i-1} - C_{i-K-1}$ である

答えは $C_N - C_{N-1}$ である。Modがいつもの素数ではないので、以下の通りにする。

atcoder::modint::set_mod(1000000000);
using ModInt = atcoder::modint;

実は累積和ではなく、スライディングウィンドウで解ける。 $Nlog(N)$ 解法でよければセグメント木が簡便らしい。

コードはこちら

方針はすぐ立ったが考えがまとまらない。

o の前後に . を置けないので、 o の前後を . で埋める。残った ? は o を置きたければ置ける場所であり、それらの値が o または . に一意に決まるならそのように決め、決まらないなら ? のままにする。

上記の通り埋めた後の $S$ に含まれる o が $C$ 個とする。 $C = K$ なら、残りの ? をすべて . に置き換えたものが答えである。以下少なくとも一個以上の ? を o にしなければならない状況を考える。

? をランレングス圧縮する。ラン $i$ が長さ $L_i$ として、 o を最大 $\lceil L_i/2 \rceil$ 個置ける。最大限 o を置くと $D = \sum L_i$ 個置けるが、 $D < K - C$ 個ならどの ? についても、 o に置き換えるか . にするか選択の余地があるので、すべての ? は ? のままである。

$D = K - C$ 個なら最大限 o に置き換える。奇数長のランは o.o.o と、 o で始まり o で終わり o. が交互に続くパターンしかないのでそのように ? を置き換える。偶数長のランは o 始まりと . 始まりの両方になりうるので、 ? のままである。

上記の通り $S$ の ? を置き換えたものが答えである。公式解説1の通りである。

コードはこちら

方針はすぐ立ったが考えがまとまらない。

問題を以下のように読み替える。

1. 頂点 $1..K$ だけからなるグラフ $G_k$ が連結かどうか調べる。連結ではない、つまり頂点1を含む連結成分 $S_k$ のサイズが $K$ 未満なら -1 を出力する。
2. 頂点 $1..K$ だけからなるグラフから、 頂点 $K+1..N$ に直接辺が出ているなら、その頂点集合 $R_k$ を求める。上記で -1 を出力しなければ、 $|R_k|$ を出力する。

$K = 1..N$ について、上記を求める。 $K = 1$ については、 $S_1 = {1}$ 、 $R_1$ は頂点1と直接辺でつながっている頂点 $2..N$ である。

頂点 $K-1$ まで求まっていて、 $K$ について求める。頂点 $K$ と直接つながっている頂点集合を $U$ とする。

• $j \in U$ について、 $j < k$ なら頂点1と 頂点 $j$ を連結する。
• $R_k = R_{k-1} \setminus k$ で初期化する。つまり $R_k$ から $k$ を除く。
• $j \in U$ について、 $j < k$ なら $R_k$ から $j$ を除く
• $j \in U$ について、 $j > k$ なら $R_k$ に $j$ を加える
• 頂点1の連結成分の大きさが $k$ なら(既述の通り頂点 $1..k$ が連結なら) $|R_k|$ を出力する。そうでなければ -1 を出力する。

計算コストは $R$ に辺を出し入れする回数で決まるので $O(Nlog(N))$ である(辺の数が $O(N)$ なので)。

コードはこちら

F問題はいつまで経っても解けないのにG問題は解けた。

答えは $(sx_i, sy_i)$ から $(gx_j, gy_j)$ までの距離のうちどれか一つである。それ以外の距離はわざわざ寄り道しているのでもっと短くできる。 $i,j \in 1..N$ の距離の二乗を整数で求めて $L[i,j]$ とする。これを座標圧縮する、つまり昇順に並べて同じ値は同じ順位にしたものを $D[i,j]$ とする。 $D$ が取りうる値を昇順に並べたものを $V$ とする。

$|V| = 1$ なら $L$ の唯一の値が答えである。そうでなければ $k \in 1..|V|$ で二分探索する。何を二分探索するかというと、 $D[i,j] \leq V[k]$ に限った $i,j$ だけで目標を達成できるかどうかを判定する。

具体的には $(i,j)$ の組を $N$ 個以上作れるかどうか判定すればよく、二部グラフのmax-flowを求めて $N$ かどうか判定する。 $(Soucre,i,j,Sink)$ というグラフを作り、 $(Source,i)$ , $(j,Sink)$ はすべての $i,j \in 1..N$ について容量1の辺を張り、 $(i,j)$ は $D[i,j] \leq V[k]$ なら容量1の辺を張る。 $(Source,Sink)$ の容量が $N$ かどうか判定する。

最後に、二分探索の結果 $k$ を $L$ に逆変換して平方根 $\sqrt{L}$ を求めると答えになる。

バチャではなく、一問ずつ解いた。

コードはこちら

$S$ の先頭から各文字を走査して、英大文字だったら出力する。

コードはこちら

これまでに案内した人数を $P = 0$ で初期化し、これまでに並んだ人の食券番号を先頭から $V$ とする。 $V$ は0-based indexingとする。

• クエリ1は $X$ を $V$ の末尾に追加する
• クエリ2は $V[P]$ を出力し、 $P$ を1増やす。

コードはこちら

初期状態で、 $C[i=1..N]$ は料理 $i$ に含まれる嫌いな食材の集合とする、 $F[j=1..M]$ は食材 $j$ を含まない料理の集合とする。 $B$ をまだ見ていないとき、答えは $C[i=1..N]$ のうち要素が空なものの数である。

$j = B_k$ について以下の操作を行う。

• $a \in F[j]$ について、 $C[a]$ から $j$ を除く
• この操作の前に $C[a]$ が空ではなく、この操作の後で $C[a]$ が空になったら、料理 $a$ を新たに食べられるようになったので答えを1増やす

コードはこちら

線分ではなく直線だった。問題を読み違えて時間が掛かった。

すべての直線の組が交わるとき、答えは $M(M-1)/2$ である。平行な直線は交わらないので、平行な直線の組を求めて答えを引く。

直線の向きは、 $S = (A - 1 + B - 1) mod N$ で一意に決まる。よって直線の向き $S = 0..(N-1)$ について、そのような直線が $L$ 本あるとき、答えから $L(L-1)/2$ を引けばよい。これをすべての $S$ について求める。

公式解説通りである。

コードはこちら

半分全列挙だとは分かったが、TLEに苦しんだ。おそらく想定解法ではないが、数時間かけてごり押した。E問題が解けなくてF問題を解けるのはなぜだろう。

座標を0-based indexingとする。対角線 $|X+Y| = N-1$ にある $N$ マス $(0,N-1)...(N-1,0)$について、取りうる $modM$ の値を全列挙すればよい。一番経路が多い $N-2 \choose (N-2)/2$ が ${18 \choose 9} = 48620$ なので、全経路を探索すれば全列挙が間に合いそうである。というより後で知ったが、二項係数の和 $\sum_{i=0}^N {N \choose i} = 2^i$ である。 $(1+1)^n$ の係数から導出できる。

$mod M$ はいつも通り求める。左上から桁を末尾に増やすときは $10accum + digit$ 、右上から桁を先頭に増やすときは $digit 10^{width} + accum$ で累積する( $width$ は右下からのマンハッタン距離)。このとき経路中で $modM$ 演算を取るとTLEする。高々10進数9桁なので、 $mod M$ を取るのは最後にまとめてで構わない。

ある対角線のマスについて、左上からの累積値が $a \in 0..(M-1)$ を取るとする。 右下からの累積値 $S$ について、 $(a + max(S)) mod M$ は常に候補になる。 $M - a$ 未満で最大の値 $b \in S$ があれば $a + b$ が答えの候補になる。これは二分探索で求まる。センチネルとして $min(S) + M$ を $S$ に加えておくと処理しやすい。

とにかく $mod M$ をできるだけ減らすとTLEを回避できる。だいたい公式解説通りだが、なぜTLEしたのだろう。

バチャではなく、一問ずつ解いた。解くのが遅い。

コードはこちら

添え字を2ずつ増やす。

コードはこちら

? を置き換える方法は必ず $26^4$ 通りなので、 $T$ を置き換えて $S$ にし、 $S$ が $U$ を含むかどうか調べる。

コードはこちら

$PS[X]$ をユーザ $X$ が閲覧できるページ、 $GS[X]$ をユーザ $X$ がすべてのページを閲覧できるかどうかとする。 $PS[X]$ の初期値は空集合、 $GS[X]$ の初期値は $False$ である。

• クエリ1は $PS[X]$ に $Y$ を追加する
• クエリ2は $GS[X]$ を $True$ にする
• クエリ3について $Y \in PS[X] \lor GS[X]$ なら Yes 、そうでなければ No である。

コードはこちら

色々見落としが多い。

$A$ に $a$ が現れる回数を $C[a]$ とする。 $|C|$ を $A$ に現れる数値の重複無し種類とする。

$D = 0$ のときは、答えは $N - |C|$ である。これを忘れるとTLEする。

$D > 0$ のときを考える。 $a$ を等差数列 $a, a+D, a+2D, ...$ に分解する。この分解は $O(N)$ でできる。分解した等差数列 $P$ について、等差数列のそれぞれの成分 $a$ が $A$ に現れる回数 $T = C[a] : a \in P$ を考える。

$\sum T$ が最大になるように $T$ を上手く間引く。これは動的計画法でできる。 $T$ の $i \in |T|$ 番目の要素を間引いた時の $T[1..i]$ の要素数を $DP[i][0]$ , 間引かないときの要素数を $DP[i][1]$ とする。二回連続で間引くことはできても、二回連続で間引かないのは許容されないので、

• $DP[0][0] = 0$, $DP[0][1] = T[1]$
• $DP[i+1][0] = max(DP[i][0], DP[i+1][1])$
• $DP[i+1][1] = DP[i][0] + T[i]$

で更新する。このとき $(\sum T) - max(DP[|T|][])$ が、ある等差数列について求める答えである。これをすべての等差数列について求めた和が最終的な答えである。

コードはこちら

ローリングハッシュでまとめながら集合を管理と分かったが手こずった。

文字列 $T$ の先頭 $k=1..|T|$ 文字についてのローリングハッシュを $H(T,k)$ とする。

• $S_1$ に含まれる文字列 $T$ の $H(T,|T|)$ の集合を $X$ とする。 $S_1$ 丸ごとのハッシュである。
• $S_2$ に含まれる $j \in 1..|S_2|$ 番目の文字列 $T = S_{2,j}$ に注目する。値が $h = H(T,1..|T|)$ となるような文字列の添え字の集合を $Y[h]$ とする。 $S_2$ が持つ接頭辞の候補である。
• $S_2$ の $j$ 番目の文字列が、 $S_1$ のいずれかの要素が接頭辞になるかどうかを $U[j]$ として持つ。接頭辞なら1、接頭辞でなければ0である。 $U$ は0-based indexingとしてセグメント木として持つ。

クエリ $T_i = 2$ が来た時点で、 $|S_2| - \sum U$ が答えである。クエリ $X,Y,U$ を更新する方法を定める。

クエリ $T_i = 1$ をこう処理する。 $h = H(S, |S|)$ として、 $j \in Y[h]$ について、 $U[j] = 1$ とする。その後の $S$ に $h$ を追加し、 $Y[h]$ を空にする。空にし忘れるとTLEする。

クエリ $T_i = 2$ をこう処理する。クエリが来る前の $|S_2|$ を $L$ とする。

• $U[L] = 1$ なら既に $S_1$ の接頭辞なので何もしない
• $U[L] = 0$ かつ $h = H(S, 1..|S|)$ として、いずれかの $h$ が $X$ に含まれるなら $U[L] = 1$ とする。既に $T$ は $S_1$ の接頭辞である。
• $U[L] = 0$ かつ $h = H(S, 1..|S|)$ として、いずれの $h$ も $X$ に含まないなら $h$ それぞれについて $Y[h]$ に $L$ を 追加する。今は $T$ は $S_1$ の接頭辞ではないが、将来は接頭辞にされるかもしれない、という予約である。
• 上記のいずれの場合も、 $L$ に1足す

コードはこちら

$O(N^2)$ が許されるので総当たりする。 $N$ を式にした時の演算子の数は $O(log(N))$ である(同じ数字を10回程度しか足さないので)。

$N = A + B$ と $N = A \times B$ についてメモ化再帰しながら総当たりして、最も文字列長が短いものを返す。 1,11,111,1111 をそのまま文字列にしたものをあらかじめ用意しておく。 $A,B$ の文字列表現をそれぞれを括弧で囲むかどうか判定する。

$A op B$ の $B$ に括弧が要るかどうかは、 $A$ の先頭から以下の通り調べる。 $B$ も同様である。

• () 内は調べない。これは入れ子の深さが0以外かどうかで分かる。 ( で1深く、 ) で1浅くする。
• $op = \times$ で $+$ が出たら、 $B$ に括弧が要る。 $op = +$ は調べなくてよい。

バチャではなく、一問ずつ解いた。E問題がわからない。

コードはこちら

出現した文字を数え、出現するかもしれない文字 a-z それぞれについて出現しなかったものを出力する。

コードはこちら

色を変えてから回転することと、回転してから色を変えることは等価である(回転後の場所の色を変えればいいので)。よって $r = 0..3$ 回転した時の操作回数は、 $S$ を回転後に $S,T$ で色が違うマスが $C_i$ 個として、 $i + C_i$ である。この最小値を求める。

コードはこちら

グラフにサイクルがあるか、と問題を読み違えて時間を溶かした。いったい何をしているのだろう。

辺の数が $N$ で、頂点数 $N$ の唯一の連結成分を持ち、すべての頂点の次数が2なら Yes 、そうでなければ No である。次数を無視すると、結び目があるグラフをサイクルグラフを誤認する。

コードはこちら

STLの柔軟性に助けられた。

std::map は std::vector<int> をキーに持つことができる。これを利用してDPを作る。

$DP[V,C]$ は、動物 $1..M$ を見た回数のベクトル $V[1..M]$ のときに、動物園の最低入場料 $C$ という連想配列とする。ただし $V \in 0..2$ とし、2回以上見たら2回と同じとみなす。初期値は $DP[0] = 0$ 、それ以外は $DP[] = \infty$ とするが、 $DP[] = \infty$ なら $DP$ に載せない。

同じ動物園を二度までは見る(三度見る必要はない)ので、動物園を見る順番を $P[1..2N] = 1..N, 1..N$ とする。 $DP[0,0]$ は動物園を全く見ていなければコスト0という意味である。

動物園 $k=P[i]$ でコスト $C_i$ で動物 $U$ を見る。 $T$ はベクトルで、動物園 $k$ 動物 $j$ を見られるときに $U[j] = 1$ 見られないときは $U[j] = 0$ である。DPの更新式は以下の通りである。

• $S$ は、値が $\infty$ でない $DP$ のすべての要素とする
• $S+T = min(2, S[j] + T[j])$ とする
• $DP[S+T] = min(DP[S+T], DP[S] + C_i)$

答えは、動物を二回見たというキーに対する値 $V = (2,2,...,2) , DP[V]$ である。

$DP$ の要素は高々 $1+2^{2N}$ 個なので、制約から 1048577個である。計算量は $NN4^{N}$ だが間に合ってしまった(60 ms)。

実は動物園を $3^N$ の全探索すればよかった。

コードはこちら

何時間考えてもわからない。MSTを作る問題だと思ったら全く違った。公式解説をほぼそのまま実装して解説ACした。後ろから考える典型である。

MSTを作ればよいのだが、合流する頂点を任意だと思ったので計算量が多すぎた。頂点 $i$ に頂点 $i+1$ 以降をすべて合流させると公式解説と同じ考え方になる。