コンテストに参加した教訓をまとめていきます。

トップページへ ABC 参加記2へ ABC 参加記3へ

ABC 325がコンテスト初参加である。A,B,C,Dはコンテストで解いた。

コードはこちら

問題文通りに素直に実装する。コンテストで最初の提出なので std::cout << s << " san\n"; の san の前に空白を入れるのをうっかり忘れたが、提出する前に気が付いて直した。

読解力が問われる。

コードはこちら

世界標準時(UTC)で $t$ 時なら、現地時間(localtime) は $(t + X_i) \quad mod 24$ である。31時というのは無く9時として扱うのだが、これは常識で補う必要がある。それと1時間の会議を18時ちょうどまでに終えたければ、17時までに開始しなければならない。

あとは総当たりでいい。UTCを $t=0..23$ の整数、拠点 $i=1..N$ について、 $9 \leq (t + X_i) \quad mod 24 < 18$ を満たす拠点について $W_i$ の合計を求める。 $t$ についての、 $W_i$ の合計の最大値が答えである。

コードの繰り返しで時間を掛けてしまった。もっと要領よく実装したい。

コードはこちら

Union-find木に一工夫

連動するセンサーを連結成分とするunion-find木にまとめる。まとめ方は、縦、横、右下、左下方向に連結するマス目である。それぞれ始点をどうするか注意が必要で、縦は最下行、横は最右列、右下は最下行と最右列、左下は最下行と最左列を加えないように注意する。そうしないと範囲外アクセスになってしまう。

というよりセンチネルつまりセンサーがないマスで囲って、4走査方向でコピーアンドペーストしないように実装をまとめる。 このように する。

あとは連結成分を数えればいいのだが、正確にはセンサーがある連結成分である。ACLのDSUは辺が無い頂点をそれ自身だけ含む連結成分として扱うので、センサーがないマス目も連結成分である。よって一つでもセンサーがあるかどうかを、 atcoder::dsu::groups() の連結成分の最初の要素がセンサーかどうか調べて、センサーで連結成分だけを数える。

時間が際どかった。1 WA (ペナルティ)を出してしまったので、修正案を締め切りギリギリに提出してACした。

コードはこちら

時刻を上手く更新する。

シミュレーションすればいいのだが、 $T \leq 10^{18}$ なので $1..max(T)$ を1ずつ更新するとTLEする。なのでもっと高速なシミュレーションを実装する。

大まかな方針を述べる。最初に、商品を印字機に入る時刻の昇順に並び替える。次に、現在時刻以降になった商品はすべて印字可能なので、締め切り $T_i + D_i$ が速い順に優先度キューに入れる。印字機に入れた時刻は優先度キューに入れなくていい。最も小さい値を取りだす優先度キューは std::priority_queue<Num, std::vector<Num>, std::greater<Num>> なのだが(デフォルトは最も大きい値を先頭に持ってくるので)、緊張すると忘れてしまう。

高速にシミュレーションするために、現在時刻を上手く更新することを考える。まず現在時刻 $time$ は0、優先度キューは空、並び替えた商品の添え字 $index$ は0、印字した商品の合計を0で初期化する。

• 優先度キューが空なら、まだ優先度キューに入れていない商品 $i$ の最も早い投入時刻 $T_i$ と現在時刻 $time$ のどちらか遅い方に現在時刻 $time$ を進める。ここで現在時刻 $time$ を1ずつ増やすとTLEする。
• 優先度キューに入れていない商品のうち、投入可能な商品つまり $T_i \leq time$ を満たす商品を取り出して、印字機から出る時刻を優先度キューに載せる。商品を優先度キューに投入したら $index$ を1つ進める。すべての商品を投入した後にオーバーランしないように気を付ける。
• 優先度キューが空になるまで商品を一つずつ取り出す。商品が印字機から出る前つまり $T_i + D_i \leq time$ なら印字可能なので、印字した商品の数を一つ増やす。商品を一個印字したら、現在時刻 $time$ を1増やす。
  • 印字機に投入していない商品があり、その投入時刻が現在時刻と等しいかそれ以前なら、優先度キューの処理を打ち切る。これを扱い損ねるとWAする(後から投入して印字機から出るのが早い商品を見過ごすので)、というかWAしてしまった。
  • そうでなければ優先度キューが空になるまで...という処理を繰り返す

こうして求めた、印字した商品の合計が答えである。

公式解説における、印字機に商品が無いときに現在時刻を進める、という方針と基本的に同じである。上記でWAしないような配慮が難しかった。WAの回避策ではなく、初めからきれいに実装し直すと このように なる。

• シミュレーションの終了条件は、商品を全て印字機に投入し、印字機が空であること
• 投入時刻と同じか投入時刻を過ぎた商品をすべて印字機に投入する
• キューが空でなければ一つ商品を取り出す。締め切りを過ぎてなければ印字し、印字した商品の数を一つ増やし、時刻を1増やす。ここではループを回さないのが重要。
• 印字機が空で、未投入の商品があるなら、未投入の商品の投入時刻まで現在時刻を進める

ループを一回回すと、印字機から商品を取り出す(印字可能かどうかは問わない)か、印字機が空なので時計を進めて商品を投入可能にするか、少なくともどちらかが成立する。よってどの商品も動かないという無限ループにはならず、 $O(N)$ 回のループで終了する。計算量は優先度キューが律速なので全体で $Olog(N)$ である。

E問題以降はコンテスト中には解けなかったので別途解いた。

コードはこちら

ダイクストラ法

ダイクストラ法のスニペットは作ったが、コピペしてすぐ使えるように直した方がいい。問題に適用するまで3分掛かるのはもったいない。

社用車で行く都市は0-based indexingで頂点 $2i$ とし、電車で行く都市は頂点 $2i+1$ とするグラフを作る。都市 $N$ は頂点 $2(N-1)$ と頂点 $2N-1$ の両方がある。出発地の都市に対応する頂点 $0$ と、たどり着かない頂点 $1$ を用意する。こうすると頂点番号を明示的に最短距離表 std::vector<std::vector<Num>> edges(N * 2) の要素に持たせなくて済む。

これを移動時間を辺の重みとするグラフにする。

• 社用車で着いた都市 $i$ から社用車で行く都市 $j$ への距離は $D_{i,j} \times A$
• 社用車で着いた都市 $i$ から電車で行く都市 $j$ への距離は $D_{i,j} \times B + C$
• 電車で着いた都市 $i$ から電車で行く都市 $j$ への距離は $D_{i,j} \times B + C$
• 社用車で着いた都市 $i$ から電車で行く都市 $j$ への距離は $\infty$

頂点 $0$ から他頂点 $i$ までの最短距離 $distance(i)$ をダイクストラ法で求め、 $min(distance(2(N-1)), distance(2N-1))$ が答えである。ただし同じ都市には遷移しない、つまり頂点 $from$ から $to$ に遷移するとき $\lfloor from/2 \rfloor = \lfloor to/2 \rfloor$ に遷移しないように注意する。

公式解説は、都市1から社用車でたどり着ける最短距離と、都市 $N$ から電車でたどり着ける最短距離を求めることで、頂点数を $N$ にしている。しまった、この考え方は鉄則本C14にあったが忘れていた。確かにそう実装する方がダイクストラ法の コード をまとめられてすっきりする。

コンテスト2回目である。A,B,C,Eはコンテストで解いた。Dは時間切れ、F,Gは問題文すら見ていない。

コードはこちら

100階に意味は無い

$-3 \leq (Y-X) \leq 2$ だけに意味がある。境界条件に気をつけて慎重に実装する。

コードはこちら

問題文をよく読む。

「なお、制約の条件下で答えは必ず存在します」ので、326-like number を全部列挙して、 $N$ 以上のものを std::lower_bound で見つける。

公式解説を見たら、一つずつ候補を増やせばよくて全部列挙する必要はなかった。B問題は上手い方法を考えるよりさくっと実装した方が早いのだが(TLEすることはないので)、それでも初手でいい方法を思いつく必要がある。解説通り 実装 すると、確かに簡潔に書ける。

コードはこちら

中途半端はよくない

$x$ として、プレゼントがある座標を選ぶのが最適である。 $x$ としてプレゼントがない座標を選んでも、獲得できるプレゼントは同じか少ないのでいいことは何もない。

あとは $A_i$ を昇順に並べ替えて、 $i=1..N$ について、 $x=A_i$ から $x+M \leq A_j$ 以上の(つまり同じ値を認める)要素 $j$ を探し、距離 $j-i$ が獲れるプレゼントの数である。 $j$ は std::lower_bound でみつけ、みつからなければ end() を返すのでその時も問題なく距離が求まる。計算量は $O(Nlog(N))$ である。

尺取り法を使えば $O(N)$ になる。実装は こちら 。C問題でC++実装なら $O(Nlog(N))$ で押し切って早く提出すればいい(B問題と同じで、コンテストでは慣れた解法を選ぶまでの時間を節約する方がいい)。そうはいっても、やはり尺取り法を速く正確に実装する訓練は必要である。

コードはこちら

DFSではなかった(わけではないが)

コンテスト中はDFSで解こうとしてどんどんコードが長くなって収集が付かなくなり、あえなく時間切れになった。翌朝もっとすっきりした解法を思いついてACした。

ある行に注目すると、文字列のパターンは $6 \times {N \choose 3}$ しかない。 ABC の順列と、 ABC を入れるマス(空きではないマス)の位置の組み合わせである。 $3 \leq N \leq 5$ より、このパターンは高々60通りであり、先頭の文字を固定すると20通りである。

各行の先頭の文字は $R$ で固定するので、各行のパターンを独立としても全マスは $20^5=3200000$ 通りに限られる。これを題意を満たすかどうか全探索して、一つでも題意を満たすものがあればそれ出力し、一つもなければ No を出力する。

• 各列の、空きでないマスの最初の文字は $C$ で与える通り
• 各列に A,B,C はちょうど一回ずつ出現する

この方法は公式解説1と同じである。C++なら途中で探索を打ち切らなくてもTLEしない。公式解説2に基づく実装は こちら

注意深く実装すればDFSでも 解ける 。公式解説より条件がややこしいので実装するにはコンテストの時間が厳しいが、実行時間に問題は無い(4 sec制約で194 msec)。

• マスを左から右に埋めて、右端まで行ったら下の行に移る
• $r$ 行目 $c$ 列目のマス $[r,c]$ を埋める文字群 ABC または空白 . を以下の通り選ぶ
  • 左端から $[r,c-1]$ まで空白 . だけなら、 $R[r]$ をマス $[r,c]$ の候補にする。加えて、空白をここに入れても右端まで $[r,(c+1)..N]$ に残りの文字を入れられるなら空白も候補にする。
  • 左端から $[r,c-1]$ までに空白 . 以外があるなら少なくとも $R[r]$ はもう使っており、まだ使っていない文字群を候補にする。加えて、空白をここに入れても右端までに残りの文字を入れられるなら空白も候補にする。
• すべてのマスが埋まったら、各列が $C$ を満たすか調べる。各行が $R$ を満たすことはそのようにDFSするのだから調べなくてよい。

コードはこちら

制約をよく見る。

問題文からして確率DPにみえる。しかし $N \leq 3 \times 10^{5}$ なので $O(N^2)$ 解法はTLEする。このことに気が付かず20分掛けて $O(N^2)$ 解法を実装してTLEし、時間を溶かしてしまった。先週ワーシャルフロイド法で解こうとして時間を溶かした教訓が活きるどころか悪くなっている(時間が延びた上ペナルティまでもらってしまった)。

まず正答を示す。確率DPといえば一応そうなのだが、あることに気づけば簡単な漸化式で表現できる。それは $y$ が異なる $A_y$ の給料は二度もらうことはできない、ということである。なぜなら $A_y$ を一度もらったら $x=y$ と更新するので、二度と $x=y$ は成立しないからだ。

ということで以下の漸化式を組む。

• 給料 $A_i$ をもらえる確率を $P_i$ とする。便宜上 $P_0=1$ とする
• $i > 0$ について、 $P_i = 1/N \times \sum_{j=0}^{i-1} P_j$ である。

漸化式は一言で言うと引くDPである。

• 前のさいころの目がどうあれ、 $i$ がでる確率は $1/N$ である
• そしてこれまで出たサイコロの目がどういう順番かは、 $j$ の目が出たかどうかで区別すれば網羅できる。なぜなら $j$ が異なる $A_j$ の給料は二度もらうことはできないので、これまで出たサイコロの目は狭義単調増加にしかならないからだ。
• 例えば3の目にたどりつく方法は、 $[0,3],[0,1,3],[0,1,2,3],[0,2,3],$ がすべてだが、結局3の目にたどりつく直線の目にたどりつく確率の和として網羅できる。 $[0,1,2,3],[0,2,3]$ を統合するのに、2の目にどうたどりついたかは関係ない。

漸化式の計算回数は $O(N)$ でここにmod計算が掛かる。これならTLEしない。この方法は公式解説1そのものである。

この漸化式はおそらく閉じた式に変換できるようにみえ、公式解説2がそれに該当するが、式の導出を間違えるくらいなら素直にコードで実装した方がいい。

漸化式が $O(N^2)$ な解法を反省のために載せる。過去問を洞察なしに適用すると、確かに解けるがTLEする。

確率DPで $DP[i=0..N][y=0..N]$ を考える。一次元目はさいころを振った回数 $i$ 、二次元目は $i$ を固定したときに $y=0..N$ である確率である。便宜上 $DP[0][0]=1$ 、他は $DP[][]=0$ とする。

既述の通り $A_y$ は二度もらえないので、 $i=0..(N-1)$ まで反復するとそれ以上もらえる給料は無くなる。このとき $DP[i+1][y] = 1/N \times \sum_{j=0}^{y-1} DP[i][j]$ で更新する。ここに至る洞察が正しければ、漸化式の回数が $O(N)$ 解法まであと一歩である。DPで計算量を削減するには累積和が常套手段であり、最初の解法に結び付く。ここで $O(N)$ の二重ループを見つけて提出を踏み止まるべきだった。

コンテスト3回目である。A,B,C,D,Eはコンテストで解いた。Fの問題文はざっとみて諦め、Gの問題文はみていない。

コードはこちら

全探索その1

$S$ の $1..(N-1)$ 文字目とその右隣をみて、 ab か ba になるものが一つでもあれば Yes 、一つもなければ No である。

コードはこちら

全探索その2

$A=1..$ に対して、 $A^A \leq B$ の範囲で全探索する。念のため __int128 を使って演算オーバーフローを避けている。

実は long long int (最低64-bit)でも通る。

$15^{15} = 437,893,890,380,859,375 < max(B) = 10^{18} = 1,000,000,000,000,000,000$ である。 $16^{16}=18,446,744,073,709,551,616 > 2^{63}-1$ なので符号あり64-bit整数ではオーバーフローするのだが、x64でオーバーフローを無視して計算し続けると、

• $16^{16} = 0 < B$
• $17^{17} = -2,863,221,430,593,058,543 < 0 < B$
• $18^{18} = -497,033,925,936,021,504 < 0 < B$
• $19^{19} = 6,353,754,964,178,307,979 > 10^{18} > B$

であり、結果的には通ってしまう。

コードはこちら

昔作ったのが役立った。

いわゆる数独である。問題通りに実装すればいい。3x3マスの4重ループを上手く実装する。

std::set の方が $1..9$ を $0..8$ にしなくて済むので 簡潔 である。こういう工夫が実装時間の短縮につながる。どうしても count したければ std::bitset<10>::count する 。

コードはこちら

二部グラフ

二部グラフを構成することに帰着する。まず $A_i = B_i$ なら明らかに題意を満たさないので No である。 $A_i \ne B_i$ という前提で以下話を進める。

$A_i,B_i$ を頂点とし、両者を辺で結ぶグラフを考える。このグラフを二部グラフとして彩色してみる。 $i=1..N$ について、まだ色がついていない頂点 $i$ を起点としてBFSする。このとき起点を 0 、辺でつながった相手を 1 、相手の相手を 0 ... と彩色することを考える。

• まだ色がついていない頂点は、隣と異なる色で塗る
• 既に色がついている頂点は、隣と異なる色で塗れるならBFSでたどらない。隣と同じ色なら題意を満たさないので No である。

すべての頂点を彩色出来たら Yes である。

Union-find木を使った 実装 の方が簡潔である。BFSより速く実装できるので解答時間を短くして他の問題に時間を割ける。

コードはこちら

割引価値

DPで解けそうにみえて、境界条件がちょっとよく分からなくなった。-Infを雑に決めたのがいけなかった。

$DP[i][k]$ を、コンテスト $1..i$ から $k$ 個選んだ時の最高レーティングとする。 $k=1$ の場合は直接計算する。このときレーティングは負になりうることに注意する。 $DP[][] = -inf$ でいいと思うがここがよくわからなかった。

• constexpr double Inf = -1000000000000; はWA
• constexpr double Inf = -1e+18f; もWA
• constexpr double Inf = -std::numeric_limits<double>::infinity(); はAC

である。最後の場合、 $i < k$ ならコンテスト $i$ は選べないというガードが無くても AC できる(ただし計算時間が倍になるので、2 sec制限を考慮してガードする方がいい)。

$DP[i+1][k]$ は、コンテスト $i+1$ を選ばなければ $DP[i][k]$ 、コンテスト $i+1$ を選べばある変換式 $f(i,k)$ があって $f(DP[i][k])$ である。なお $(i+1) < k$ ならコンテスト $i+1$ は選べない(ここを抜くと入力例は通るが前述の通りWAする)。両者の最大値を取って $DP[i+1][k]$ を更新し、すべての組み合わせの最大値が答えである。

この $f(i,k)$ を実装するのがこの問題の主な課題である。まず定義より、 $k=1$ なら $Q_i - 1200 / \sqrt{k}$ である。

$f(i,k)=R_k$ が求まっているとき、 $f(i+1,k)=R_{k+1}$ の第一項の分子 $D_{k+1}$ は $D_{k+1} = Q_i + 0.9((R_{k} + 1200 / \sqrt{k}) \times (1-0.9^{k})/0.1)$ である。この考え方は、過去のコンテストについて割引価値を求めるとき、累積和に0.9に掛ければ $\sum$ の中を再計算しなくていいという意味である。ここで等比数列の和の公式、 $\sum_{i=1}^{k} ar^i = a(1-r^k)/(1-r)$ を用いている。よって $R_{k+1}=D_{k+1} / ((1-0.9^{k+1})/0.1) - 1200 / \sqrt{k+1}$ である。

こうしてDPを更新すると、更新回数は $O(N^2)$ になる。意外と計算時間が厳しいので(2sec制限)、ガード無しの877msよりガードありの437msにすべきである。

ここで $1200/sqrt(k)$ と $(1-0.9^{k})/0.1$ をあらかじめ計算すると実行時間を 30 msec まで短くできる。定数オーダーの最適化も気にした方がいい。

コードはこちら

コンテスト中には問題文を読んでもいないが、ADTで見たので解いた。ADTの60分で9完は間に合わなかったがあと6:15だった。

かごにりんごが収まるのではなく、りんごを収めるかごがどの範囲にあるか、と読み替える。つまり時刻 $T_i$ に座標 $X_i$ にりんごが落ちるなら、時間帯 $[T_i, T_i + D)$ に座標 $[X_i, X_i + W)$ にあるかごで拾うことができると考える。座標に下駄を履かせる必要はない。時間帯はキューで管理し、座標は遅延セグメント木を用いた区間更新で管理する。

遅延セグメント木には、ある座標のりんごを拾えるかごの位置の座標数を載せる。

1. りんごが時刻 $T_i$ に $X_i$ に落ちたら、区間 $[X_i, X_i + W)$ に1を足す。そのりんごをキューに追加する。
2. 時刻 $T_i - D$ までに落ちたリンゴについて、区間 $[X_i, X_i + W)$ に-1を足す。そのりんごはキューから除く。
3. 全区間についての値の最大値が、ある時刻に拾えるりんごの最大数である
4. これを全 $T$ について最大値を求める

2と3を逆にしたので答えが合わず60分9完を逃したのは惜しかった。

コンテスト4回目である。A,B,C,D,Eはコンテストで解いた。Fの問題文はTLE解まで行ったが解けなかった。

コードはこちら

条件に合う $S_i$ を足す。

コードはこちら

決め打ち

この種のB問題は決め打ちが定石である。

まず月を決め打ちする。月の下一桁が0なら無視する。そうでなければすべての月日を列挙して、月の下一桁と月、日の各桁が一致ものを数える。

月日を文字列表記する方が早く 実装 できる。

コードはこちら

累積和

$i$ 文字目までに隣り合う文字が何文字あったかを累積和で求める。境界条件に注意する。

コードはこちら

プッシュダウンオートマトン

文字をスタックに積んでいく。スタックトップが ABC (スタックの上から順に CBA )なら、取り除けるだけ取り除く。 std::stack だとスタックの上から2,3文字目を見るのが大変なので、 std::vector の方が実装しやすい。

コードはこちら

総当たり

$K$ で割った余りはDPできなさそうなので、総当たりで行く。グラフを木にするには、ループが発生しない範囲で辺を追加し、すべての頂点を網羅したら木である。これをDFSで求める。木のコストはDFSしながら求まる。 $N \leq 8$ なのでC++なら余り実装に気を遣わなくてもTLEしない(696 ms)。

コードはこちら

重みつきunion-find木

重みつきunion-find木を使えば解ける。使わなくても解けるがそれについては後で述べる。コードはこちらの 記事 を参考にし、命名規則やコーディングスタイルなどを変えてある。やりたいことは公式解説通りである。

• 解の全体構造を、辺 $a_i,b_i$ に距離 $d_i$ があるグラフとみなす。辺の向きは $a_i$ から $b_i$ に距離 $d_i$ 、逆向き $b_i$ から $a_i$ が 距離 $-d_i$ である。距離というより重みと言う方が適切かもしれない。
• $a_i,b_i$ が同じ連結成分になければ、距離 $d_i$ の辺 $a_i,b_i$ で結ぶ。このような $i$ は良い集合である。
• $a_i,b_i$ が同じ連結成分にあれば、頂点 $a_i,b_i$ の距離が $d_i$ なら $i$ は良い集合であり、そうでなければ良い集合ではない

公式解説3に基づくQuick Findを使った実装は こちら である。Quick Findの実装はこちらの 記事 を参考にした。

最初に私が思い浮かべた解法も大体同じなのだが、 $a_i,b_i$ が同じ連結成分にあるときに $O(1)$ で頂点 $a_i,b_i$ の距離を求める方法が分からずTLEした。重みつきunion-find木は一つの解決策だが、実はクエリ先読みを使った別解が公式解説2である。重みつきunion-find木を知らなかったのはまあ仕方ないが、クエリ先読みを思いつかなかったのは発想力が足りない。連結成分にはループが無い、つまり木であることまでは分かったのだけど。実装すると このよう になる。

コンテスト5回目である。A,B,C,Dはコンテストで解いた。Eは80分掛けて解けず、Fはコンテスト終了直後から解き始めて16分で解いた。つまり問題選択を完全に間違えた。

コードはこちら

A問題は最後の文字の後に空白を出力しないよう気を付ける。念のため改行も出力しない。公式解説てきには、 std::endl は出力してもいいらしい。

コードはこちら

降順に並び替えて先頭から順に値を調べ、先頭以外の値が出たらそれが二番目に大きい値である。

コードはこちら

ランレングス圧縮

文字種 a-z ごとの最長ランを求める。それらの和が答えである。

コードはこちら

std::set を上手く使う。 std::set<Num,Num> の要素は候補者に対応し、得票数 $c$ と、候補者番号 $i$ について $[C,-i]$ というペアにする。そうすれば std::set<Num,Num>::rbegin() で取り出せるのは題意の当選者、つまり最多得票で、同得票数なら番号が最も小さい候補者である。

あとは一票ずつ開票して、候補者の std::set<Num,Num> の要素を入れ替えればいい。 $O(Mlog(N))$ で求まる。

公式解説は、最後の当選者を覚えて置いて $O(M)$ で求めている。 こう 実装するし計算量が減るのはうれしいが、個人的には場合分けが少々複雑なので早解きでWAする心配がある。

コンテスト中に80分掛けて解けなかった。

コードはこちら

まずWAを取り切れない解法を述べる。完成系 $S$ から $T$ を剥がしていってすべて # だけからなる文字列を作れるかどうか調べる(この方針自体は公式解説と同じ)。剥がせるというのは、 $T$ の部分文字列を重ねて # に置き換えられるということである。 # 以外の連続する文字列があったとき、左または右から $1..M$ 文字重ねるというのを繰り返す。のだが、どういう訳かWAした。

公式解説は $S$ と $T$ を比較するとき虫食いでいい、つまり T=ABA と S=...A#A... が一致することである。言われてみればその通りだった。虫食いに対処するなら左右からスキャンしたのではだめかもしれない。

コンテスト中に80分掛けて解けなかったが、コンテスト直後に16分掛けて解けた。この問題ではなくE問題を選んだのは、完全に問題選択を間違えた。

コードはこちら

高度なマージテクが要るかと思ったらそうではなかった。題意通りそのまま実装すればACできる。

• $N$ 個の箱に対応する std::set 型の $S_i$ を用意する。箱には $C_i$ だけ入れる。
• クエリごとに $S_a$ の中身を $S_b$ に移す。このとき箱にあるボールの種類 $|S_a|$ は sets[a].size() である。ボールを移す前に、 $|S_a| > |S_b|$ なら std::swap で箱を入れ替えてから移す。その後 $|S_a|$ を空集合と std::swap して空にする。

この実装は536 msで実行できてTLEしない。公式解説も上記の通り std::swap を前提にしている。

コンテスト6回目である。A,B,C,Dはコンテストで解いた。Eは締め切り10分遅れ、F,Gは問題を見ていない。

コードはこちら

素直に $A \leq L$ の要素数を数える。

コードはこちら

題意を理解するのに苦しんだ。

$L \leq A_i \leq R$ なら $X_i = A_i$ にできる。よって答えは $A_i$ なのだが、何を間違えたか $0$ と提出してしまった。 $L \leq A_i$ なら $X_i = L$ , $A_i \leq R$ なら $X_i = R$ である。

公式解説通り、 std::clamp を使うと簡単に 実装 できる。

コードはこちら

この問題も異常に手こずってしまった。

まず非負整数の二乗つまり平方数を $i=0..sqrt(2 \times 10^{12})$ を求める。 $i=0..sqrt(2 \times 10^{12})$ について、 $abs(i^2-d)$ に近い平方数を二分探索する。見つかった平方数 $s$ とその前後について $abs(i^2 - d + s)$ を求め、その最小値が答えである。

何を思ったか $abs(i^2 - d - s)$ とコーディングしてしまい時間を溶かした。絶対値を展開するのに焦った。公式解説をみて思ったのだが、そもそもなぜ私は二分探索をしたのだろう。公式解説通りの $O(N)$ 解法は こちら 。

実は三分探索でも解けるらしい。三分探索ではなく差分を二分探索、つまり目的の式 $f(x,y) = |x^2+y^2-D|$ について $x$ を固定して上で $f(x,y+1,D)-f(x,y,D)$ が非負になる(負から非負に転換する)最小の $y$ を求めればいい。下記に丸ごと コード を載せた方が説明しやすい。 $log(N)$ 倍計算コストが多くなるが、絶対値の扱いで悩むことは無くなる。

void solve(std::istream& is, std::ostream& os) {
    Num d {0};
    is >> d;

    constexpr Num Upper = 1500000;
    Num answer = 1000000000000000000LL;
    for(Num x{0}; x<Upper; ++x) {
        auto func = [&](const Num y) {
            return std::abs(x * x + y * y - d);
        };

        Num left = 0;
        Num right = Upper;
        while((right - left) > 1) {
            Num base = (left + right) / 2;
            if ((func(base+1) - func(base)) < 0) {
                left = base;
            } else {
                right = base;
            }
        }

        answer = std::min(answer, func(right));
    }

    os << answer << "\n";
}

コードはこちら

この問題も異常に手こずってしまった。

各行各列に o が何個あるか数えておく。 o があるマスを全探索し、そのマスの同行に $r$ 個(そのマス自身を含む)、そのマスの同列に $c$ 個(そのマス自身を含む)あったら、組は $(r-1)(c-1)$ 通りある。この和が答えである。重複して組を数えることは無い。

o があるマスを全探索しという条件を忘れ、すべてのマスを全探索して時間を溶かした。

コードはこちら

B,C,D問題で時間を使いすぎて時間切れし、締め切りの10分後に解いた。この問題に45分掛けたのも長すぎるが、とにかく他の問題を早く解けなかったことが原因である。

MEXは $0$ 以上 $N$ 以下にしかならない。よって $N$ より大きな $A$ の要素は無視して構わない。

集合として $A_{1..N}$ の要素 $A[1..N]$ 、非負整数 $0..N$ を何個 $A_{1..N}$ に保持しているか $count[0..N]$ 、非負整数 $0..N$ のうち今使っていない数 $blank[0..N]$ を管理する。それぞれ std::vector , std::vector , std::set で持つ。以下のように初期化する。

• $A[1..N]$ の要素は読み込んだ要素を設定する
• $count[A_i]$ は $0 \leq A_i \leq N$ を見つけるたびに1増やす。ただし $A_i > N$ なら何もしない。
• $blank$ は初期状態で $0..N$ をすべて加え、 $A_i$ を取り除く。ただし $A_i > N$ なら何もしない。

上記の後 $blank$ に無い最小の非負整数を $mex$ とする。その後各クエリを処理する。クエリごとに以下の通り更新する。

• $A_{i_k} = x_k$ なら何も更新しない。以下 $A_{i_k} \ne x_k$ とする。
• $old = A_{i_k}$ とする。クエリの前に $old \leq N$ なら $count[old]$ を1減らす。減らした後0になったら $old$ は使っていないので、 $blank$ に $old$ を加える。その後 $mex = min(mex, old)$ に更新する
• $x_k \leq N$ なら $count[x_k]$ を1増やし、 $blank$ から $x_k$ を除く。すでに除いてあれば何もしない。
• $mex$ を 旧 $mex$ 以上の使っていない数にする。 blank.lower_bound(mex) が指す値で $mex$ を置き換える。
• 置き換えた $mex$ を出力する

よく考えたら $mex$ は $blank$ の最小要素なので変数として保持する必要はない。よってもっとすっきりした 実装 にできる。

• $old = A_{i_k}$ とする。クエリの前に $old \leq N$ なら $count[old]$ を1減らす。減らした後0になったら $old$ は使っていないので、 $blank$ に $old$ を加える。
• $x_k \leq N$ なら $count[x_k]$ を1増やし、 $blank$ から $x_k$ を除く。すでに除いてあれば何もしない。 $old = x_k$ でも問題ない。
• この時点では $mex$ は $blank$ の最小要素 blank.begin() が指す値である

今使っていない数ではなく、今使っている数を管理してコンテスト中はTLEしてしまった。最初からここに気づけば35分で解いて、ぎりぎりコンテストでは提出が間に合った可能性があるのだが、これが時間無制限で解く練習と期限内に解くコンテストの差である。

セグメント木を使うと、要素数と要素が空かどうかを同時に管理できる。参考にしたコードは こちら で、私の実装は こちら である。

コンテスト7回目である。A,B,Cはコンテストで解いた。D,Eは締め切り8,23分遅れ、F,Gは問題を見ていない。

コードはこちら

桁の繰上りを実装する。

コードはこちら

時間を使い過ぎた。 $N \leq 100$ なのだからS,M,Lを0..100パックずつ買っても100万通り総当たりすればいい。

配るDPでも 解ける 。こちらの 記事にある通り、整数計画問題として解ける。SciPyで解くと こちら で、 PuLPで解くと こちら 。

コードはこちら

元の $A_{1..N}$ と、ソート済の $A_{1..N}$ を持ち、 $A_i$ 以上の要素が何個あるかを std::upper_bound で調べる。

コードはこちら

デバッグにしくじって期限に間に合わなかった。二次元累積和を

bool grid[1024][1024];
Num cumsum[1024][1024];

と書くべきところを、

bool grid[1024][1024];
bool cumsum[1024][1024];

と書いてしまったので、いつまでたっても入力例が通らなかった。 grid を cumsum にコピペするときに直し忘れた。コンパイラは bool に += しても警告を出さないし、警告を出す方法も分からない。今後は状態を bool で管理するのを止めた方がよいかもしれない(そうしたからといってMLEするわけでもないので)。

マスの座標表示として、左上ぴったりの座標を含む、右下ぴったりの座標は含まない、とする。 $mod N$ で $(0,0)-(N,N)$ の領域を単位とする。単位に完全に含まれる領域は、 $(N \lceil a/N \rceil, N \lceil b/N \rceil)$ , $(N \lfloor c/N \rfloor, N \lfloor d/N \rfloor)$ であり、領域の幅と高さを $N$ で割ることで単位の数が分かる。単位に含まれる黒マスはあらかじめ数えれば分かる。

単位未満の領域を数える。左上、真上、右上、左、右、左下、下、右下について黒マスの数を求める。 $modN$ の座標 $p$ において、区間は $[0,p)$ か $[p,N)$ かどちらかである。この領域にある黒マスの数を数えればいいのだが、クエリが多数あるので、あらかじめ領域に対して $O(1)$ で黒マスの数を返せるように二次元累積和を求めておかないとTLEする。最初これを忘れてTLEし、二次元累積和を実装したのだが32分掛かっても上記のバグを直すことができずに終わった。

公式解説は $(0,0)-(A,B)$ と $(0,0)-(C,D)$ という二次元累積和と捉えることで、領域分割をより巧妙に行っている。実装は こちら 。より正確には黒マスの数を、原点を左上として右下が4か所の二次元累積和 $(C+1,D+1) - (A,D+1) - (C,B+1) + (A,B)$ で求める。一次元累積和と同様、開区間と閉区間のインデックスに気を付ける。

コードはこちら

コンテスト終了8分後に331-Dのデバッグが完了し、そのまま解いた。15分で解けたので331-Eを先に解いて331-Dを後にすれば得点が増えたので、またもや問題選択を間違えた。この癖が一向に直らない。ただ331-Dの解法は問題文を見てすぐ思いついたので(領域分割が公式解説より拙いのとTLEに気がつかなかったが)、EよりDを先に着手したときは解けるだろうと予想した。正解者数より、最速正解がD:8分、E:2分に注目すればよかったのかもしれない。

$L \leq min(10^5, NM-1)$ の制約が厳しいので、探索を上手く打ち切れば $O(NM)$ にはならずTLEしない。のだが、331-Dを落としたショックから break; を忘れて一回TLEしてしまった。

std::vector<std::pair<Num, Num>> に値段、主菜とID $0..(N-1)$ を組にして入れて、降順にソートする。値段の降順が得られ、IDの順序は気にしなくていい。副菜も同様である。後は主菜の値段が高い順に(外ループ)、副菜の値段が高い順に見て行って(内ループ)食べ合わせが悪くないなら組み合わせて内ループを打ち切る。適切に内ループを打ち切れば探索回数は $O(N+L)$ になり、食べ合わせを連想配列で管理するコストが最初の登録時に $O(Llog(L))$ である。この方法は こちらの公式解説 と同じである。

公式解説1のように優先度キューでも組めるが、インデックス管理が大変である。実装は こちら。セグメント木でも 解ける 。

コードはこちら

実装に落とし込む方法が分からなかったので、公式解説のコードを読んで作り直した。基本的には文字列のローリングハッシュをセグメント木に載せる。これだけではどうしていいか分からないので、具体的な方法を学ぶ。

ローリングハッシュの定義は公式解説通りである。文字のUS-ASCIIコードをそのまま数値とみなし、文字 $C_{1},C_{2},...,C_{M}$ について $\sum_{i=1..M} C_i x^{M-i}$ とする。ここで $x$ は実行時に決める乱数である(素数でなくてもよい)。実際には $mod \quad prime$ で値を取り、ハッシュ衝突を避けるために複数 ($K$ 個)の素数( $prime$ )を用意してそれぞれについてハッシュを生成する(素数ごとに $x$ も異なる)。

セグメント木に載せるのは、文字列を左から読んだ時のローリングハッシュ、文字列を右から読んだ時のローリングハッシュ、文字列長に対応する係数である。係数とは先の $x^i$ 、ただし $i$ は文字列長である。後は公式解説通り実装する。

• $K$ 個の $x$ を実行時に決める
• 一文字をセグメント木のノードにする。ハッシュ値は文字のUS-ASCIIコード 係数は $x$ とする。
• セグメント木のノードの単位元を作る、ハッシュ値は文字の0、係数は $x$ とする。
• セグメント木のノードを結合し、新たなノードとして左からのハッシュ値、右からのハッシュ値、係数の積を返す。

ここまで来たら初期文字列をセグメント木に載せ、クエリごとに文字を更新する。回文かどうかは、左右から読んだハッシュ値が一致するかどうかで分かる。

コンテスト8回目である。A,B,C,Dはコンテストで解いた。E,Fは解けなかった。

コードはこちら

問題文をそのまま式にする。

コードはこちら

これも問題文をそのまま式にする。

コードはこちら

洗濯する日 0 の間で連続する 12 の区間について考え、全区間の中で最も多いロゴ入りのTシャツの購入枚数が答えである。最後には暗黙に 0 があるとすると終端処理が楽である。一区間については以下の通りである。

• 競技プログラミングのイベントに行く $C$ 日分だけ、ロゴ入りのTシャツが要る
• 食事に行くのが $D$ 日として、 $M$ 日以内なら無地のTシャツで済み、それを超えた分はロゴ入りのTシャツを買う。
• つまりロゴ入りのTシャツは合計で $max(0, D-M) + C$ 枚要る

コードはこちら

なんとか解けた。

$H,W \leq 5$ なので行列の入れ替えは総当たりすればいい。この組み合わせが $(5!)^2$ 、グリッドの一致検査が $HW$ 回なので、 $A,B$ が一致するかどうかの検査は最大360000回である。

一致する入れ替えがなければ -1 を返す。一致する入れ替えについて操作回数は転倒数である。よって答えはすべての一致する操作回数について、転倒数の和の最小値である。問題文をよく読むと行、列は隣としか入れ替えられないので転倒数とすぐ気が付くべきだったが、ここで十数分を費やしたものはもったいなかった。

コードはこちら

TLE解しか出せなかった。

分散の定義は公式解説4を参照する。公式解説によると計算量は $O(D \times 3^{N})$ である。解説をよく理解しないと、DPにおける内ループと外ループが $O((2^{N})^2)$ になり、計 $O(D \times 4^{N})$ になってTLEする。そのための数え上げの工夫が公式解説4だが、巧妙すぎて思いつくことができなかった。公式解説4のコードを引用する。

for(int t=s;t;t=(t-1)&s){
   new_dp[s]=min(new_dp[s],dp[s^t]+w2[t]);
}

結論から述べる。 $s$ の立っているビットが $p$ 個とする。 $q=(2^{p-1}-1)..0$ を順に数え、 $q$ の各ビットを $s$ の立っているビットに右から順に(LSBからMSBの方向に)当てはめることと等価である。例えば $s$ が二進数で $011010$ のとき、 $s$ の $0$ を見やすくするために $.$ と書けば、 $[.11.1.],[.11.0.],[.10.1.],[.10.0.],[.01.1.],[.01.0.],[.00.1.]$ である。

Rubyで確認するコードが以下の通りである。

fmt = '%06b'
s = '011010'.to_i(2)

t = s
while t > 0 do
  puts(fmt % t)
  t = (t - 1) & s
end

t = s;
while t > 0 do
  u = ((fmt % s).split('')).zip((fmt % t).split('')).map do |sc, tc|
    if (sc == '0')
      '.'
    else
      tc
    end
  end.join()
  puts('[' + u + ']')
  t = (t - 1) & s
end

• 集合 $s$ から 集合 $t$ を除いた残り $s \oplus t$ を求める。これらはすべてビットパターン(集合に要素 $i=0..(N-1)$ があるときにビット $i$ が $1$、なければ $0$ )である。
• $s \oplus t$ が差分、つまり $t$ で立っているビットは $s$ でも必ず立っている、というところが重要である。なぜなら以下のように更新するからである。
• $t-1$ は、 $t$ の最右(LSBから見て最初に立っている)ビットを $0$ に、それより右を $1$ にする。LSBを0ビット目として3ビット目が立っているとして、 $1000$ を $0111$ にする。
• これを $s$ でマスクする。そうすると
  • $t$ の最右ビット(3ビット目)を0にする( $??0???$ )
  • $t$ の最右より右(0..2ビット目)に $s$ の立っているビットがあればすべて立てる( $??0.1.$ )。 $s$ のビットを復活するともいえる。
• この操作は、 $s$ の立っているビットだけ集めて2進数 $p$ 桁の数があるときに、1を引くことと等価である。10進数の計算において、 $x000, x > 0$ から $1$ 引いたら、 $y999, y=x-1$ になるのと同じである。 $999$ のところが $s$ のビットを復活するという操作である。

こうすれば集合 $s$ から 集合 $t$ を除くために、 $t$ は $s$ の部分集合であることを確かめなくて済む、というより $t$ が $s$ の部分集合ではない例を挙げないのが計算量を減らす原動力になっていると思われる。

コードはこちら

遅延セグメント木を使えば解けると想像はしたが、それだけでは解答できない。

こちらの 実装 を参考にして実装した。何を遅延セグメント木に載せるかが課題である。 atcoder::lazy_segtree でいう木のノード $S$ と写像 $F$ を定義する。

写像 $F$ から定義する。問題文の通り、入力値(明示されない)を確率 $p$ で期待値を $x$ に変更する。この合成を $F \circ G$ を考える。つまり $(G_p, G_x)$ を適用した後に $(F_p, F_x)$ を適用する。これは

• 確率 $F_p$ で $F_x$ にする
• 確率 $(1-F_p)G_p$ で $G_x$ にする
• それ以外は無変更

である。このとき

• 変更する確率は変更しない確率の残りなので $1 - (1 - F_p)(1 - G_p)$
• 変更するときの期待値は $F_p \times F_x + (1-F_p)G_p \times G_x$

である。ここで写像として、

• 変更しない確率 $F^{'}_p = 1 - F_p$
• 変更するときの期待値 $F^{'}_x = F_p \times F_x$

と定義すると $F \circ G$ において、

• 変更しない確率 $({F^{'} \circ G^{'}})_p = F^{'}_p \times G^{'}_p$
• 変更するときの期待値 $({F^{'}\circ G^{'}})_x = F^{'}_x + F^{'}_p \times G^{'}_x$

となってすっきりする。これは他の方の実装を見るまで分からなかった。恒等写像は $F^{'}_p = 1, F^{'}_x = 0$ である。

次に遅延セグメント木のノード $S$ を定義する。これは要素数(幅) $width$ と、期待値 $avg$ からなる。単位元は要素数0, 期待値0である。実装する処理は区間の統合(merge)と、写像による区間更新(update)である。

• Merge: 両区間 $lhs, rhs$ の幅の和が0なら単位元を返す(これを忘れると0除算が発生してREする)。そうでなければ両区間の加重平均を取る。つまり
  • $width = lhs.width + rhs.width$
  • $avg = lhs.width \times lhs.avg + rhs.width \times rhs.avg$
• Update: 区間 $lhs$, 写像 $F^{'}$ を与え、写像が期待値を更新するときとしないときの加重平均を取る。
  • $width$ は $lhs$ のまま
  • $avg = lhs.avg \times F^{'}_p + F^{'}_x$

ここまでくれば、初期値 $A$ とクエリ $(L-1,R,X)$ をセグメント木に載せれば答えが求まる。

コンテスト9回目である。A,B,C,D,Eはコンテストで解いた。Fは問題文をちらっと見て、解き始めようとした頃には残り10分なので諦めたし解説を読んでもまだ理解していない。

コードはこちら

問題文をそのまま文字列にする。

コードはこちら

頂点ABCDEを、頂点番号0,1,2,3,4と読み替える。頂点番号の差の絶対値が $0..4$ なら、距離が $[0,1,2,2,1]$ とする。この距離は同じ長さと違う長さの辺を区別しているだけ、つまりカテゴリ値である。

あとは同じ距離(カテゴリ)の辺なら Yes そうでなければ No を出力する。

コードはこちら

$N$ がとても小さいので、レピュニットを1..18桁分作って総当たりしてソートしても間に合う。よくみたら入力例がそうだった。

コードはこちら

解の方針を立てるのに手こずった。頂点1の直接の子ノード達について、それぞれの頂点数が効いてくるのは分かったが、その後の考察が大変だった。

まず頂点1が葉なら答えは1である。これは頂点1の次数が1であることから分かる。

そうでなければ頂点1の直接の子ノード達について、それぞれの子ノードの先にある頂点数(子ノードを含む)を求める。これをソートして、一番大きいもの以外の和が答えである。なぜなら一番大きい物以外を刈ると頂点1が葉になるからだ。上手くまとめれば頂点1が初めから葉の場合とまとめられるだろう。

頂点1の直接の子ノード達は互いに結びつかないことを利用して、union-find木を使って木の頂点を数えることができる。再帰が要らないので少しコードが短くなる。実装は こちら 。

コードはこちら

333-Dとは逆に、解の方針はすぐ立ったが細部がややこしかった。

ポーションとモンスターについて、すべてのタイプ $x_i$ について独立に問題を考えていい。なのであるタイプ $x$ についてだけ考える。

出来事を最後から最初に向かって再生する。モンスターが居たら、必要なポーション $s$ を1足す。ポーションを見つけたら、必要なポーション $s$ を1引く。ただし必要なポーションは0未満にはしないので、更新式は $s=max(0,s-1)$ である。出来事の最初まできて必要なポーションが0より多ければ、モンスターを撃退できないので、その場で -1 を出力して終了する。

上記の再生時に、ポーションをみつけた時点で必要なポーションが0より多ければ、そのときポーションを拾うという操作を記録する。ポーションを拾わない(必要なポーションが0)ときと、モンスターに遭遇したときは拾わないとしてよい。要するにポーションを拾うのはできるだけ遅くして構わないということである。

最後に出来事を先頭から再生する。モンスターを撃退できることは分かっているので、どのポーションとモンスターかは気にしない。

• ポーションをみつけて拾う出来事ならポーションを1個追加して 1 を出力する(ように配列にpushする)。併せて、ポーションの保持数の最大値を更新する。
• ポーションをみつけて拾わない出来事なら 0 を出力する(ように配列にpushする)
• モンスターに遭遇したらポーションを1個減らす。

問題文にある通り、まずポーションの保持数の最大値を出力し、その後でポーションをみつけて拾うか拾わないか出力する。

コンテスト中の解答は余分なコードが多々あるので、必要なコードだけ残すと このように になる。それでも意外と長い。

コンテスト10回目である。A,B,C,D,Eはコンテストで解いた。Fは問題文をちらっと見て、解き始めようとした頃には残り10分なので諦めた。

コードはこちら

問題文をそのまま実装する。

コードはこちら

5問中一番解答時間が掛かった。初見で20分掛けて入力例を解くことができずいったん諦め、C,D問題を解いた後に解いた。

分かってしまえば解法は簡潔である。この方法は公式解説2と同じである。まず $L,R$ から $A$ を引いて $A$ を原点にする。

$L$ およびそれより東にある最も近いクリスマスツリーは、 $L$ 以上の $M$ で割り切れる最も小さい数である。これを $l$ とする。 $R$ およびそれより西にある最も近いクリスマスツリーは、 $R$ 以下の $M$ で割り切れる最も大きい数である。これを $r$ とする。

$l > r$ なら高橋君と青木君の間にあるクリスマスツリーは0本である。そうでなければ $1 + (r - l) / M$ である。つまり区間 $r-l$ を $M$ 区間に分割し両端を数える。

$L$ 以上の $M$ で割り切れる最も小さい数は以下のように求める。負の数の除算がどうなっているか振る舞いがややこしいので、念のため手作業で場合分けする。 $modM$ を重ねているのは、 $M$ を $0$ にするためである。

• $L \geq 0$ なら、 $L + (M - L mod M) mod M$
• $L < 0$ なら、 $L + abs(L) mod M$

$R$ 以下の $M$ で割り切れる最も大きい数は以下のように求める。

• $R \geq 0$ なら、 $R - abs(R) mod M$
• $R < 0$ なら、 $R - (M - R mod M) mod M$

Rubyなら Integer#ceildiv を使って こう 書ける。

公式解説1は、 $L-1$ および $R$ より西(除算を切り捨てる方向)にある最も近いクリスマスツリーを使っている。実装は こちら。

これも他の方の解法から知ったのだが、原点に移動したあとの $L,R$ に下駄を履かせて非負にする、つまり $\lceil \frac{2 \times 10^{18}}{M} \rceil M - A$ を $L,R$ に足すと、公式解説1の方法がより理解しやすくなる。このように移動した後では原点より東だけ、 $[0,R]$ に含まれるクリスマスツリーから $[0,L)$ に含まれるクリスマスツリーを引いたものが答えであり、 $\lfloor R/M \rfloor - \lfloor (L-1)/M \rfloor$ である。これが一番簡潔な コード である。

コードはこちら

B問題が解けなかった動揺から、D問題よりも先に解いてしまった。解法自体は割とすぐ思いついたが、C問題にしては重そうにみえる。

0-based indexing で 色 $0..(N-1)$ の靴下が $0..2$ 足あることを数える。次に靴下を色の昇順に、その色の靴下の数だけ並べる。例えば色0の靴下が2足、色1の靴下が0足、色2の靴下が2足あるなら $[0,0,2]$ である。

奇妙さの総和を最小にするには、色で昇順にならべた靴下を先頭から2足ずつ組み合わせればよい。なぜなら昇順になっている靴下を入れ替えると、全体の奇妙さは増えることはあっても減ることはないからである。靴下が偶数足ならこれだけで解ける。

公式解説では、無くしていない同じ色の靴下は2足まとめるの最適とあるが、これは使わなくてもよい。同じ色の2足が別れても、奇妙さの総和は変わらないからである。

靴下が奇数足( $M$ 足)なら、どれか靴下 $0..(M-1)$ を一足抜いて残った偶数足( $M-1$ 足)の靴下について同様に求める。ここで計算量を減らさないと計算量が $O(N^2)$ になってTLEする。対策として、色が小さい方から偶数足、色が大きい方から偶数足とった場合の奇妙さについて、累積和を求めておく。

公式解説では累積和を $presum$ と書いているが、これは prefix sum の略である。Rには cumsum という関数があり、これは cumulative sum の略である。

コードはこちら

C,D問題を解けて順位表を見たところで、ようやくB問題に取り組む心構えができた。

$R$ を昇順に並べて累積和を求め、 $X$ 以下となる累積和のインデックスを it = std::lower_bound で求める。 it が $X$ より大きい要素を指しているときは一つ手前にして、先頭からの距離が答えである。

コードはこちら

連結成分の増減を丁寧に数える。

まず赤いマスを数え(総数を $r$ をする)、緑のマスの連結成分を求める。これは union-find木を構成し、連結成分の最初の要素が緑である連結成分の総数 ($g$) を求める。

それぞれの赤いマス $C$ について、緑に塗ると連結成分がどう増減するか数える。赤いマス $C$ の上下左右それぞれのマス $A \in {UDLR}$ について、他の上下左右とつながることができるものが何個あるか数える。

• $A$ が赤く塗られていたら無視する。そうでなく緑なら、
• 他の上下左右マス $B \in {UDLR} \setminus A$ について $A,B$ が同じ連結成分なら $C$ を塗ったからといって $A,B$ が $C$ を介して新たにつながる訳ではないと分かる
• $A$ に対してこのような他の上下左右マス $B$ がなければ、 $C$ を介してつながることができる。つまり $C$ を緑に塗ると $A$ が全体の連結成分から1減る。

そのような $A$ が何個あるか求める ($G$ 個とする)。上記の方法をコンテスト中に実装して、自分で読み返しても分からなかったのだが、もっと簡潔な方法があると知った。上下左右の連結成分の代表元が何種類あるか数えればそれが $G$ の値である。実装は こちら 。

$C$ を緑に塗ると、連結成分は以下の通り増減する。

• $G > 1$ なら $G-1$ 個連結成分が減る ($G$ 個の連結成分を1つにまとめるので)
• $G = 1$ なら $1$ 個連結成分は増減しない ($C$とつながるだけなので)
• $G = 0$ なら $1$ 個連結成分が増える。これは $C$ が単一成分の連結成分になることを意味する。

すべての赤いマスについて、それぞれ緑に塗ったときの、連結成分の総増減 $d$ が求まるので、 $g - d / r$ が答えである。

コンテスト11回目である。A,B,C,Dはコンテストで解いた。EはTLE, Fは問題文を10分以上考えて諦めた。配点からしてE,Fは解けないだろうという予想が当たってしまったが、C問題のペナルティが痛恨である。E問題はあと一歩足りなかった。

コードはこちら

「英小文字と数字からなる文字列Sが入力されます」「Sは2023で終わることが保証されます」は無視してよく、「Sの最後の文字を4に変更し、変更後の文字列を出力してください」だけ実装する。改行を除いた入力文字列の最後の文字を 4 にする。

コードはこちら

外から内に $X,Y,Z$ の順に $1..N$ をループし、 $x + y + z \leq N$ なら出力する。

コードはこちら

上下を読み違えて、1ペナルティ5分 + 再提出に6分掛かった。これを割ければ順位が600位程度は上がったはずで、急ぎ過ぎて出力例1があっていないことを見過ごしてしまった。

龍の尾が切れることは考えず、ひたすら頭が伸びていくと考えてよい。

• 初期状態はベクトル $(N..1,0)$ である。逆順であることに注意。
• 1種類目のクエリで頭が伸びる。伸びた先はベクトルの末尾に加える。 std::vector なら計算量は $O(1)$ である。
• 2種類目のクエリで頭から $p$ 番目の位置を返す。 std::vector なら添え字 std::vector::size()-p で、計算量は $O(1)$ である。

いつものグリッド操作の癖で U 上方向はY座標が減ると勘違いしたが、本問では U 上方向は $y$ 軸正方向である。出力例1をよく確認すればわかったはずだが、なぜか見過ごしたまま提出してしまった。

対策を考える。コンソールに入力と出力が混ざってどれが出力か分からなくなるのは、 grep で色付けすると、どれが出力か分かる。

make && ./335c | grep --color '^.*'

あらかじめ用意した期待値(出力例)と、コマンドの出力が一致するかどうかは、 bash なら以下のように調べる。

diff の -C オプションは、copied contextで出力を十分長く出して、出力が何か確認しつつ期待値 expected.txt との差を表示する。 --strip-trailing-cr オプションは行末のCRを除くことで、WindowsとCygwinで改行コードがCRLFかLFの違いを無視する。

diff -C 100000 --strip-trailing-cr <(make && ./335b) expected.txt

コードはこちら

とぐろを巻けばよい。座標を0-based indexing, 中心座標を $C=\lfloor N/2 \rfloor$ とする。

• 始点を $(C-1,C-1)$ にする。上下左右の移動幅を、 $[C-1,C+1]$ にする。
• 一回下に移動してから、移動先に連番1を振る。その後移動幅いっぱいまで下に移動し、そのたびに連番を振る。
• 移動幅いっぱいまで右に移動し、そのたびに連番を振る
• 移動幅いっぱいまで上に移動し、そのたびに連番を振る
• 移動幅いっぱいまで左に移動し、そのたびに連番を振る
• 0列目なら終了する
• 一列左に移動して連番を振る。移動幅を上下に1ずつ広げ、同様に下、右、上、左に移動幅いっぱいまで進む。以下繰り返し。
• 中心 $(C,C)$ は連番ではなく T を出力すること忘れずに

公式解説は外周から順に内周に向かっている。上記では内周から外周に向かう。

コードはこちら

最大経路問題に慣れる。324-Fの経験が活きなかった。

最小経路問題と同様に始点からBFSするとTLEする。結局TLEを取り切れずにコンテストが終わってしまった。

解法としては、隣接する $A$ が等しい頂点をひとまとめに圧縮する。Union-find木を使って圧縮し、連結成分を代表元に読み替えた新たなグラフを構築する。公式解説では新たなグラフを構築せず、頂点を代表元に読み替えながら処理する。

移動できるのは $A$ の昇順なのでそのように頂点 $1$ から頂点 $N$ までたどり、経路があれば最長経路長、経路がなければ答えは0である。繰り返しなるが、最小経路問題と同様に始点からBFSするとTLEする。 $A$ の昇順に、隣接する頂点に経路長を配るのが正解である。 $A_i < A_j$ なら $i$ から $j$ に配る。

公式解説1はバケットソートらしく解いているが、公式解説2のようにダイクストラ法でも 解ける 。これをコンテスト中にやりたかったのだが、優先度キューに積むものを思いつかなかった。

有向グラフの最長経路はトポロジカルソートして経路長をDPすると求まるので そうしても よい。ただしその場合は、トポロジカルソートの入力を有向グラフにする、つまり $i$ から $j$ に向かうなら $A_i < A_j$ にして、 $j$ から $i$ への枝をグラフに入れない。前記の解法は配るときに $A_i < A_j$ か $A_i > A_j$ か判定してもよいが、トポロジカルソートではそうできない。

コンテスト12回目である。A,B,Cを9分11秒で解き、D問題以降を90分掛けて解けなかった。早解きできたが、D問題を解けなかったのでパフォーマンスが振るわなかった。

コードはこちら

問題文通りに文字を追加する。大文字と小文字を区別する。

コードはこちら

$N$ を2で割り切れる回数である。While文で求まるが、C++20なら以下の通り一行である。

void solve(std::istream& is, std::ostream& os) {
    uint64_t n {0};
    is >> n;
    os << std::countr_zero(n) << "\n";
}

コードはこちら

5進数である。

まず $N=1$ なら答えは0である。これを忘れるとおそらくWAする。

$N>1$ なら $N-1$ を5で割った余りを求めて2倍する。これを逆順に出力する。各桁は ${0,2,4,6,8}$ と一桁なので空白区切り無しで出力すればよい。 $N=1$ のときに空文字列にならないように特別扱いした。

コードはこちら

90分掛けて解けなかった。全く解法の糸口すらつかめなかった。

上記のコードは、公式解説2である。公式解説のようなエレガントな解でなくても $O(Nlog(N))$ でも、何か正解にたどり着く方法はなかったのだろうか。

公式解説1に基づくコードはこちらで、公式解説4に基づくコードはこちら

桁DPを使うこと、桁和を決め打ちすることは分かったのだが、実装中に何をしてよいか分からず手が止まってしまった。 $N$ との大小でDPすることが全く分からなかった。

コンテスト13回目である。久しぶりの5完である。

コードはこちら

問題文通り実装する。変数 $X,Y$ と出力 Takahashi, Aoki がこんがらないように気を付ける。

コードはこちら

おそらく簡単な解法があるが、 $S$ が短いし文字が三種類なので正規表現で書いてしまった。B問題は長考するとどんどん時間が無くなるので、何か短時間で解ける方法を思いつく必要がある。正規表現はときどき計算量が爆発するので怖いし、C++でregexを使うのは久しぶりだったが、思い切って使った。公式解説でも正規表現が挙がっている。

void solve(std::istream& is, std::ostream& os) {
    std::string s;
    is >> s;

    std::regex re(R"(^A*B*C*$)");
    if (std::regex_match(s, re)) {
        os << "Yes\n";
    } else {
        os << "No\n";
    }
}

公式解説をさっと読んでから、文字が広義単調増加(文字のアスキーコードが非減少)だと気が付いた。公式解説2-3と同じで、公式解説は std::is_sorted を使い、 std::is_sorted を知らずに実装すると こちら になる。

コードはこちら

落ち着いて考える。

• 先頭の人は $A_i = -1$ な人 $i$ である、そうでなければ
• 次の人というベクトル $next[N]$ において、 人 $next[A_i] = i$ という連結リスト(linked list)を作る

あとは先頭の人から連結リストをたどればよい。連結リストの挿入コストを $O(1)$ にするために std::vector で持つ。

コードはこちら

TLEしないように気を付ける。

文字列を与えられたら、o を連続 $K$ 個並べられるか、並べられるなら何個 o が足りない( . を o に変える必要があるか)か求める関数を作る。この関数にすべての行とすべての列を入れ、後述の操作回数の最小値を求める。最小値が求まらない、つまりどうやっても $K$ 個並べられないなら、答えは -1 である。

文字列 $S$ の長さを $L=|S|$ とする。0-based indexingで先頭から $i \in [0,L-K]$ まで調べる。 $[i,i+k-1]$ に x があれば $K$ 個並べられないし、なければ並べられる。並べられるときは、 $K$ から区間の o の数を引いたもの(. の数)が、必要な操作回数である。計算量が $O(L^2)$ だとTLEするので一工夫する。

• $S$ 中の x の位置をあらかじめ求めておく。そうすれば $i$ 以降の最初の x は std::lower_bound で $log(L)$ で求まる。
• o の数をあらかじめ累積和にしておく。そうすれば $[i,i+k-1]$ の o の数は $O(1)$ で求まる。

公式解説は x の数も累積和で求めている。一瞬それも思いついたが、上記の方法にしてしまった。公式解説は $O(HW)$ 、上記の方法は $O(HWlog(HW))$ なのでC++の力でゴリ押してしまったが、どちらも実行時間は大差ない。 x の数も累積和で実装すると この ようになる。

コードはこちら

この種の問題は複数回見たことがあるので、解法の目途はすぐ立った。しかし細かい作り込みを間違えて、1 WA + 再提出9分掛かった。本当にもったいない。

そもそも、出力形式を間違えてはいけない。改行と空白をジャッジサーバは区別する(単に改行を空白文字とみなしている訳ではない)。インタラクティブな問題に慣れていないが故の誤りだが、今後は気を付けよう。

解法だが、友人 $i$ をビット $i$ とみなして、腐ったジュースの番号を特定する。ただし0-based indexingであることに注意する。これを間違えてWAした。まとめて1 WAだったのが救い。

• 友人の数は $W=\lceil log2(N) \rceil$ である。これは std::bit_width(N-1) で求まる。これを当初 std::bit_width(N) にしてしまった。 $N=8$ の出力がおかしいので気が付く。
• 友人 $i=[0,W-1]$ をビット $i$ に対応させる。 $[0,N-1]$ のビット $i$ が立っていれば、そのジュースを飲ませる。ジャッジサーバは1-based indexing なので1足して渡す。
• ジュースの本数と番号の間は空白である。改行にするとWAする。
• 受け取った数は2進数なので、逆順に読んで(先頭の文字がLSB、最後の文字がMSB)2進数に変換する。この値に1を足す(解答は1-based indexing)なので
• All 0sを受け取るということは誰もお腹をこわさないということだが、0は0-based indexingの先頭なので、1-based indexingなら1番目ということで辻妻が合う

ペナルティ無しで10分早く解けば青パフォだったらしい。D,E問題の早解きをもっと鍛える必要がある。インタラクティブ問題はデバッグが難しいので実装の正確さが問われる。

コンテスト14回目である。レーティング修正が減って、暫定の字が無くなった。3完しかできなかった。A,B,C問題をコンテスト中に解いて、E問題は21分遅れでACした。D問題はコンテスト中には解法が分からずE問題の解説を書いていたら理解できた。F問題はさっと読んで諦めた。

コードはこちら

std::islower, std::isupper はそれぞれ英小文字、英大文字に該当するなら非0, 該当しないなら0を返す。返り値はbool値でも1でもないので比較には注意を要する。C/C++において0と等号または不等号で比較するのが鉄則で、1と比較するのは推奨されない。

コードはこちら

やりかたは一つではないが、それだけに却って迷いが出る。問題の制約から、以下の方法にした。

• 英小文字 a-z を整数 0..25 に変換する
• 整数 0..25 それぞれの出現回数を数える。長さ26の std::vector に収める。
• 最多出現回数を求める
• $i = 0..25$ を走査して、最多出現回数となる最小の $i$ を出力して終了する。 std::max_element はこの用途に合っているが、ループを手書きして最初の最大要素で打ち切った。

整数に変換しなくても連想配列でもよい。そのときは連想配列 std::map<char,int> に文字が登録されていない場合は0を返すことを利用する。

コードはこちら

$A,B = 0$ の扱いが厄介なので慎重に実装する。

問題の制約から、料理の最大数は $10^6$ 、材料 $N=10$ のとき、 $10^7$ 回のループを回すと分かる。なので作れる料理Aの数 $N_a = 0..$ を決め打ちして、それぞれの $N_a$ で作れる料理Bの数 $N_b$ を求め、 $N_a + N_b$ の最大値を求める。

$N_a$ を決め打ちしたとき、料理Aに材料 $i$ は $A_i \times N_a$ 使う。これは $N_a$ について単調増加なので、 $A_i \times N_a > Q_i$ ならその場で処理を打ち切って構わない。

材料Bから作れる料理の数は $\lfloor (Q_i - A_i \times N_a) / B_i \rfloor$ なので、この最小値が $N_a$ を決め打ちしたときの $N_b$ である。ここで $B_i = 0$ なら料理の数を求めてはならない(0除算エラーになる)。制約から $B_i \geq 1$ なる $i$ が存在するので材料Bから作れる料理の数が不定にはならない。不定値の定義として十分大きな数にしてもいいが、 std::optional の方が可読性がよい。

上記を打ち切るまで繰り返せば、料理Aと料理Bの数の和の最大値が求まる。

コードはこちら

封鎖されると困る橋を選ぶには、封鎖したときのコストが最小の橋を選ぶ。地点は0-based indexingとする。

$A$ 地点から $B$ 地点に最短距離で行くために通る橋の数は $A < B$ として(そうでなければ $A,B$ を逆にする)、 $D=min(B - A, 2N + A - B)$ である。この考察はE問題と同じである。橋を封鎖されると迂回するので、通る橋の数つまりコスト $C$ が $C = (N - D) - D = N - 2D$ 増える。

どの橋を封鎖されると通る橋の数が $C = N - 2D$ 増えるかを求める。そのまま実装すると計算量が $O(N^2)$ になってTLEするので、いもす法を使う。インデックス操作がややこしく、一つ間違えるとWAが多発する。

• $A$ から $B$ に昇順に行くなら( $D = B - A$ なら)、 $A$ で $C$ 増やし、 $B$ で $C$ 減らす
• そうでなければ(降順に行くなら)、 $0$ で $C$ 増やし、 $A$ で $C$ 減らし、 $B$ で $C$ 増やし、 $N$ で $C$ 減らす

これを $X$ のすべての隣り合う経路、つまり $[X_i,X_{i+1}] : i=1..(N-1)$ について求める。ある橋を封鎖したときに迂回が必要かどうかは、すべての隣り合う経路について独立である。そうすればコスト $C$ が最小の橋 $T$ が分かる。コストが最小の橋が複数あるならどれを一つ選んでもよい。

あとはツアーを実際に行って、封鎖した橋 $T$ を通るなら迂回し、そうでないなら直行する。 $A$ 地点から $B$ 地点に最短距離で行くために通る橋の数は $A < B$ として(そうでなければ $A,B$ を逆にする)

• $A$ から $B$ に昇順に行くなら( $D = B - A$ なら)
  • $A \leq T < B$ なら迂回して $N-D$
  • そうでなければ直行して $D$
• $A$ から $B$ に降順に行くなら
  • $T < A \lor B \leq T$ なら迂回して $N-D$
  • そうでなければ直行して $D$

である。この累計が答えである。ほぼ公式解説1と同じである。

遅延セグメント木を使うと こちら の実装を参考に このよう になる。いもす法は橋の番号で線形走査し、セグメント木は橋の二分木を積み上げると言える。遅延セグメント木を使うと計算量が $O(Nlog(N))$ になってしまうが、整数の可算だけという遅延セグメント木に慣れていれば却ってコードが短くなるかもしれない。

コードはこちら

C問題までを22分14秒で解き、D問題は題意を読み解くところからして厄介で、F問題は解けそうにないことから、E問題に賭けた。解答までに要した時間は99分12秒、つまりコンテスト中には解けなかった。

辺が交わることの定義が厄介で、それさえわかれば解けたも同然である。

連続する頂点を右岸と左岸に分離するのが答えである。この右岸と左岸に分離した連続する頂点という組は全 $2N$ 頂点に複数あってもよく、 $2N$ 頂点全部をまるごと右岸と左岸に二分する必要はない。このことに気が付かなかったのがコンテスト中に解けなかった敗因である。その後、辺が交わるときと交わらないときでどういう特徴量が異なるだろう、と試行錯誤しているうちにコンテストが終わってしまった。80分くらい試行錯誤して、以下を思いついた。

右岸頂点の同士が円周上に連続して出現し、左岸頂点の同士が円周上に連続して出現し、右岸と左岸の頂点が円周上で入り混じらなければ辺が交わらないと言える。以下頂点番号は0-based indexingで表記する(入力値から1引く)。

最初の辺を長さでソートする。頂点番号が $A < B$ のとき(そうでなければ $A$, $B$ を入れ替える)、辺の長さは時計回りと反時計回りの短い方 $D=min(B-A, 2N + A-B)$ である。これをタプル $[D,A,B]$ にして std::vector に載せて距離の昇順にソートする。辺が短い順に辺を加える。

辺の交わりをセグメント木で表現する。要素は整数、単位元は0、applyを整数の可算にする。

頂点 $A,B$ を結ぶ辺があり(説明の都合上、まず辺の長さが $D = B - A$ のときだけ考える)、その区間に他の辺が収まっているかどうかをセグメント木で調べられるようにする。辺の長さの昇順に調べるので、今加えようとしている辺 $A,B$ が既に加えた辺と交わらなければ、既に加えた辺の方が短いのだから頂点 $A,B$ の区間は既に加えた辺を覆うはずである。この覆っているか否かをセグメント木の区間可算で表現する。

これはセグメント木の要素 $A$ を $+1$ 、セグメント木の要素 $B$ を $-1$ にする。セグメント木の区間 $[A,B]$ の和を取って、和が0なら $[A,B]$ にある辺(0本かもしれない)は $[A,B]$ から飛び出しておらず頂点 $A,B$ の区間は既に加えた辺を覆うと分かる。逆に和が非0なら $[A,B]$ の中から外へ辺が飛び出している。セグメント木の範囲の境界値について、同じ頂点は二度現れない、つまりいま調べようとしている頂点 $A$, $B$ はセグメント木の要素が必ず0なので、雑に境界値を設定しても問題ない。

ここまで書いて、D問題とE問題が似ていることに気が付く。円周に沿って区間和を取るところがそっくりであり、E問題を解けたことがD問題の解決につながった。E問題の方が境界値の設定が緩い分、ほんの少し簡単なのかもしれない。

セグメント木の区間 $[A,B]$ の和が非0なら Yes を出力してすぐ終了する。そうでなければセグメント木の要素 $A$ を $+1$ 、セグメント木の要素 $B$ を $-1$ にして、他の枝を見る。

辺の長さが $D = B - A$ でないときは反時計回りなので、セグメント木の区間 $[A,2N]$ と $[0,B]$ の和を取る。セグメント木の要素 $A$ を $-1$ 、セグメント木の要素 $B$ を $+1$ する。他は同様である。

すべての枝について調べて交わることがなかったら、 No を出力して終了する。

公式解説1は最初に書いた、連続する頂点を右岸と左岸に分離するという操作を、閉じ括弧の対応として表現している。確かにこの方が理解しやすく、公式解説もセグメント木に言及しているがスタックを使うと $O(N)$ になるのはエレガントである。実装は こちら 。

コンテスト15回目である。A,B,C,D,Eの5完である。Eを解いてからDを解くのも正しい順序である。いつもこうありたいが、実装力に課題が残った。

コードはこちら

A問題からしてなかなか解けなくて焦った。文字列の最後に出る . を標準C++ライブラリで見つけようとして方法が分からず(正解は 下記 )、for文を手書きして解いた。ここで時間を使ってしまったのはもったいない。

void solve(std::istream& is, std::ostream& os) {
    std::string s;
    is >> s;
    os << s.substr(s.rfind('.')+1) << "\n";
}

A,B問題のようにテストケースが1個/回なら、正規表現も 使える 。

コードはこちら

250点B問題はハマると怖いが、アルゴリズムはすぐわかって実装が厄介な問題である。なぜか4方向を std::vector でコンパイルが通らず、仕方ないのでC配列で書いた。どうしてコンパイルが通らなかったのか、今となっては分からない。Initializer-list initialization を書き損ねたのだと思う。

std::vector<std::pair<Num, Num>> dyxs {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};
std::pair<Num, Num> dyxs[4] {{-1, 0}, {0, 1}, {1, 0}, {0, -1}};

コードはこちら

始発時点の乗車人数から累積和の底値が0が割り込まなければいい。始発時点の乗車人数を0と決め打ちして、累積和の最低値 $x=min(cumsum)$ が $x < 0$ なら始発時点の乗車人数をその分下駄を履かせる。つまり始発時点の乗車人数を $max(0, -x)$ にする。

コードはこちら

実装力が問われる。

2人のプレイヤーを障害物と壁に押し付ける手順を厳密に求めると、色々と反例が出そうである。よってある状態から次の状態に遷移できるかどうかグラフを構築し、2人のプレイヤーが同じマスにたどり着くまでの最短手順を求める。たどりつけなければ -1 を出力する。

行と列を入力そのままの(つまりプレイヤーが動ける範囲では)1-based indexingとして、センチネルとして盤外を障害物で囲む。つまり $H+2$ 行 $W+2$ 列とみなす。マスの数は $M = (H+2)(W+2)$ である。

状態は、2人のプレイヤー $P,Q$ それぞれの行と列 $C,R$ の組、 $PC, PR, QC, QR$ できまる。以下の通り定義する

• 2人のプレイヤーが同じ場所に居れば0とする。0行0列のマスには到達しないので0で問題ない
• そうでなければ、 $M(PC \times H + PR) + (QC \times H + QR)$ とする

ある状態から次の状態は、4方向の移動を総当たりする。2人のプレイヤーをある方向に1マス動かそうとしたとき、障害物がなければ隣のマスに移動でき、障害物(盤外含む)があれば隣のマスに移動できない。移動後の結果が、

• 2人のプレイヤーとも移動できなければ状態遷移しない。状態が変わらないともいえる。
• 2人のプレイヤーの少なくとも一方が移動できれば状態遷移する。状態が変わるともいえる。2人のプレイヤーが同じ場所に居れば先に述べた通り。

であり、状態遷移元から状態遷移先に枝を向ける有向グラフを作る。後は初期状態から終端状態(2人のプレイヤーが同じ場所に居る)までの最短距離を求める。

最短距離をダイクストラ法で求めるとTLEする(これで1WA)。なのでBFSで求めるが、距離をlong long intで保持するとMLEする(これでもう1WA)。距離をint16_tで保持すると 2226 ms, 986472 KB とギリギリでACした。メモリ使用量が $2(62^4) = 29552672$ つまり30 Mbyteでない時点で何かがおかしい。状態数は int16_t に収まらないのにACできてしまった。

有向グラフを一度に全部構成するとメモリが足りないが、次の状態遷移だけキューに積んで逐次的に構成すれば 1074 ms, 141640 KB に収まる。実装は こちら 。

コードはこちら

始めてセグメント木でACできた。

$A$ に同じ値 $a = A_i = A_j, i < j$ があったとき、 $A_j$ を選んだ方が長い部分列を作れる。よって $a$ で終わる部分列は添え字が最後のものだけ保持すればよい。

Aの最大値は $maxA = 5 \times 10^{5}$ に固定なので、要素数が $maxA + 1$ のセグメント木で保持する。セグメント木の要素は整数、演算は最大値、単位元を0とする。セグメント木の要素数は $N,D$ とは無関係なので注意する(これが原因で実行時エラーが起きた)。 $A_1,..,A_N$ について以下の通り更新する。

• 先頭の値を $set(A_1, 1)$ つまり $A_1$ だけの部分列があり、長さを1とする
• $A_i, i > 1$ を末尾とする部分列を作るなら、 $L = max(1, A - D)$, $R = min(maxA, A + D)$ として、末尾が $[L,R]$ にある部分列からつなぐことができる。よって $[L, R]$ の最大値 + 1 をセグメント木に $set(A_i)$ する。セグメントの実装によって引数が異なるので注意する(Rが右開区間なら引数は $R+1$ )。

全部の要素についてセグメント木を更新したら、区間 $[1,maxA]$ の最大値が答えである。区間は雑に取って構わない(部分列に含まれない場合は長さ0なので)。区間を正確に取ると こちら 。

コードはこちら

コンテスト後に解法をちらっと見たので実装した。

$A_i \times A_j = A_k$ は $mod P$ においても $(A_i mod P \times A_j mod P) mod P \equiv A_k mod P$ である。前者が成り立つなら後者は必ず成り立ち、後者が成り立てば前者はほぼ成り立つ(衝突して偽陽性が出ることがある)。衝突に備えて複数の素数 $P$ を用意する。

$mod P$ を32-bit、乗算結果を64-bitで持つ。 $2^{32}$ 未満の素数は例えば こちら の値を使う。

あらかじめ $A_k : k=1..N$ について、 $P$ で割った余り $0..(P-1)$ に該当するものが何個あるか求めて置く。この値は std::unordered_map<uint64_t, size_t> で数える。 std::multiset<uint64_t>::count(x) はキー x の要素数に線形の時間が掛かるのでTLEする。

後は $i=1..N$, $j=i..N$ について、 $(A_i mod P \times A_j mod P) mod P$ が $A_k mod P$ である要素を数えて足す。足すときに $i = j$ なら1倍、 $i < j$ なら2倍する ( $(i,j)$ と $(j,i)$ ) 。

実はBoost Multiprecision Libraryでも通る。上記のように探索範囲を $i \leq j$ に限定すれば、1396 msなので2秒制限に 通る 。A..E問題をもっと早く解いていれば、TLE覚悟で提出して通った可能性がある訳で、早解きができたらと思うと惜しい。

コンテスト16回目である。A,B,C,D,Eの5完である。Cで時間を掛け過ぎた。Fは44分掛けたが結局だめで、6完は遠かった。

コードはこちら

制約に「そのような等差数列が存在する入力のみが与えられます」とあるので、 $A$ から $B$ まで ($A,B$ ともに含む)出力する。

$D > 0$ なので、 $D$ が0だったり負だったりする設定よりは楽できる。だから こう してよい。公式解説も同じだが、改行コードを三項演算子にするのを初めて知った。

コードはこちら

std::vector::push_back() と std::vector::at() の使い方を理解していれば解ける。添え字に気を付ける。

コードはこちら

解答時間を掛けすぎである。

最初の実装は手元で2秒以上掛かったのだが、これは最適化無しだから遅いのであって、最適化したら2秒を切ると思ってジャッジに投げたらTLEした。痛恨である。最初に正解を思いつかなくて焦ってしまったのにペナルティまでつけてしまった。

操作するごとに $x$ は $\lfloor x/2 \rfloor$ , $\lceil x/2 \rceil$ になって減るのだから、黒板に書かれた整数が大きい順に処理すればいい。ここで同じ数を繰り返し処理するとTLEする。なので、 $x$ が $counts[x]$ 個あるというメモを作る。

• $x < 2$ ならこれ以上操作できないので何もしない。
• $x \geq 2$ なら、払う金額を $x \times counts[x]$ 追加する(ここがややこしい)。その上で $\lfloor x/2 \rfloor$ , $\lceil x/2 \rceil$ をそれぞれ $counts[x]$ 個増やす。
• $x$ は未処理のものを降順に処理する。

メモ化再帰でもっとすっきり実装できるらしいが、まだ上手く理解できていない(操作前の自分より大きな数がどうだったかには影響を受けないのでDFSで求まるということ)。公式解説1そのもののコードが こちら である。この種の実装力がまだまだ私には足りない。

といって済ます訳にも行かないので証明を考える。 $x$ から $1$ に至るまでの一連の操作で取りうる数が何種類あるか考える。

• $x$ が偶数(LSB=0)なら、1段の操作によって生まれる数は $y = x/2$ が2つである。よって取りうる数は1種類増える。
• $x$ が奇数(LSB=1)なら、1段の操作によって生まれる数は $y = (x-1)/2$ と $y + 1$ である。よって取りうる数は2種類増える。
  • $y$ が偶数(LSB=0)なら $y+1$ は奇数 で、 $y,y+1$ から1段の操作によって生まれる数は $z = y/2$ と $z + 1$ である。よって取りうる数は $x$ から2種類増える。
  • $y$ が奇数(LSB=1)なら $y+1$ は偶数 で、 $y,y+1$ から1段の操作によって生まれる数は $z = (y-1)/2$ と $z + 1$ である。よって取りうる数は $x$ から2種類増える。

以上の考察から、1段の操作によって新たに生まれる数は高々2個であり、 $N$ の桁数のオーダー(つまり $O(log2(N))$ ) に収まる。よってメモ化する対象は $O(log2(N))$ 個であり、 $N$ から $1$ に至る操作も $O(log2(N))$ 回なので、メモ化によって操作を打ち切れば探索回数も $O(log2(N))$ に収まる。私の解法はBFSで、公式解説はDFSで求めている。

コードはこちら

素直にダイクストラ法で解く。

コードはこちら

始めて遅延セグメント木を使ってコンテストで本番ACした。

遅延セグメント木は要素を整数、単位元を0、ノードの統合と作用する関数をともに整数の可算にする。この実装は338-Dと全く同じである。

あとは遅延セグメント木における区間可算を以下の通り定義する。下記で関数は atcoder::lazy_segtree のメンバ関数である( atcoder::lazy_segtree オブジェクトが入った変数の名前は省略する)。

• 初期値は $A_i$ を $set(i, A_i)$ する。
• $i$ 番目の操作は $box = B_i$ 、取り出したボールの数を $balls = get(B_i)$ とする。
• 箱 $box$ を空にする。 $set(box, 0)$ とする。
• ボールを何周配るかは $cycle = \lfloor balls / N \rfloor$ 、周回の端数は $rem = balls \quad mod N$ で求まる
• ボールを $cycle$ 周配る。これは $apply(0, N, cycle)$ でできる。
• ボールを $box$ の次を先頭として(ここが引っ掛かりやすい)、 $modN$ で順に $rem$ 個順に配る。
  • $box + 1 + rem \leq N$ なら $[box + 1, box + 1 + rem)$ に配る。 $apply(box + 1, box + 1 + rem, 1)$ でできる。
  • $box + 1 + rem > N$ なら $[box + 1, N)$ と $[0, (box + 1 + rem) mod N)$ に配る。同様に $apply()$ でできる。

最後に箱にあるボールの数を $get(i) : i \in [0..N)$ で取得して出力する。上記は公式解説そのものであり、遅延セグメント木が想定解法である。

双対セグメント木を使うと実行速度が速くなる。 こちらの記事 にあるコードを参考にいたしました。解答は こちら 。

コードはこちら

三角形の面積は外積の絶対値の半分であることと、拡張ユークリッド法までは分かった。しかしそこから先をどうしていいか分からないままコンテストが終わってしまった。

解き方は公式解説通りである。最後に $2/gcd(|X|,|Y|)$ を掛けるところが分からなかった。それと条件を満たす $(A,B)$ が複数あるならどれを答えてもよい。例えば $(X,Y)=(2,0)$ なら $Y= \pm 1$ を満たすすべての点が条件を満たす。これが分からなくて入力例1が通らないと思い込んだ(明言されていないが、出力例以外にも答えはある。英文では Find a pair of integers (A,B) that satisfies とあり、いずれか一組を返すよう要請していることが分かる)。

コンテスト17回目である。A,B,C,Dの4完である。C,D問題に時間を掛け過ぎ、E問題を解いたのが 22:44:29 だった。あと5分早く提出していたら5完だったが、その5分ができなかった。

コードはこちら

10 を $N$ 回出力し、続いて 1 を1回出力する。公式解説は逆で、 1 を1回出力してから続けて 01 を $N$ 回出力している。

コードはこちら

添え字の大きな通貨を添え字の小さな通貨に換金するすることは無い。よって $i=1..(N-1)$ の順に $A_i$ を $\lfloor A_i/S_i \rfloor \times T_i$ に換金する。

コードはこちら

少し実装が重い。

始点 $(r,c)$ を $r=1..(H-1)$ , $c=1..(W-1)$ に決め打ちして総当たりする。陸から外れずに(海に入らずに)パスを最後までたどり着いたら、最後の場所を std::set<std::pair<Num,Num>> に追加する。最後の場所の大きさつまり、重複を数えない集合の大きさが答えである。答えるのは不時着した場所ではなく現在地というか終着地なので注意する。

この問題に49分掛けてしまったために、E問題を解く時間が足りなかった。

コードはこちら

最初に $M > N$ と入れ替える。 $M < N$ でも、 $M$ が $N$ の倍数であってもなくても解けそうな気がするが、この辺りを整理しないと解ける気がしなかった。

$N$ または $M$ のいずれか一方だけの倍数には周期があり、それは最小公倍数 $L = LCM(N,M)$ である。 $[0..L)$ に含まれる $N$ または $M$ のいずれか一方だけの倍数は $S = L / N + L / M - 2$ 個である。2個引くのは $0$ が $N$ の倍数でもあり $M$ の倍数でもあるからだ。まずここがややこしく時間が掛かった。

LCMを何個足すかは $\lfloor (K-1) / S \rfloor$ 回である。 $\lfloor K / S \rfloor$ ではない。 $[0..L)$ の何番目の数を見るかは、0-based indexing で $R = (K-1) mod S$ 番目である。次に添え字の操作がややこしく時間が掛かってしまった。

後は $[0..L)$ に含まれる $N$ または $M$ のいずれか一方だけの倍数のうち、 $R$ 番目の数を選ぶ。これを $[0..L)$ で全数サーチするとTLEする。昇順の優先度キューに $N,M$ を積み、キューから値を取り出したら $N$ の倍数には $N$ を足し、 $M$ の倍数には $M$ を足す。D問題に取り組んで40分経った焦りから、足すところを掛けてしまい計算が合わなかった。とにかくグダグダである。 $L$ 以上の値はキューに積まなくてよい。

上記の通り順を追って考えれば解けたのだが、全体的に扱いがややこしい。上記の方法は公式解説2とほぼ同じであるが、優先度キューを使うまでもなかった。ここの考察に至らなかったのが49分掛かった原因である。上記を理解してれば、再実装は数分で 完了する 。

公式解説1の通り二分探索でも 解ける 。答えを $t$ に決め打ちしたときに、 $N$ または $M$ のいずれか一方だけの倍数になる正の数は $\lfloor t / N \rfloor + \lfloor t / M \rfloor - 2 \lfloor t / LCM(N,M) \rfloor$ 個である。これは0を数えないのと、 $LCM(N,M)$ の倍数を二度引くのが間違えやすい。

コードはこちら

D問題に時間を掛け過ぎて、最後の詰めが間に合わなかった。

問題自体はほとんど 322-F である。遅延セグメント木を用意し、ノードを以下の通り定義する。

• 範囲の最左の数字 $left$
• 範囲の最右の数字 $right$
• 範囲の幅 $width$
• 範囲がいい文字列かどうか $good$

ノードのメンバ関数を以下の通り定義する。

• 空の範囲について、 $left=0, right=0, width=0, good = true$ とする。実はwidthではなく、空かどうかだけ分かればよい。ここで0に決め打ちしたのがまずく、おそらくoptionalにすべきだった。
• 入力 $S$ に基づいて、 $S$ の $i$ 文字目が数値 $d$ なら $left=d, right=d, width=1, good = true$ とする
• 反転(flip) を $left:=1-left, right:=1-right$ とする。 $width, good$ は変えない。
• 連続する範囲の統合(merge)を定義する。一方の範囲が空 $width=0$ なら他方を使う。これを思いつかなくてコンテスト中に間に合わなかった。両方の範囲とも空でなければ、以下の通り定義する
  • $left$ は左の範囲の $left$
  • $right$ は右の範囲の $right$
  • $width$ は両方の範囲の $width$ の和
  • $good$ は両方の範囲が $good=true$ かつ 左の範囲の $right$ と右の範囲の $left$ が異なればtrue、それ以外はfalse
• 作用素の与えるパラメータは反転回数だが、LSBのxorにする。2回反転するのは反転しないと同じである。
  • 作用素の合成はxorである
  • ノードに作用素を適用するとき、0ならそのまま、1なら反転(flip)したノードを返す

後は $S$ でノードを初期化して、クエリに答える。

1. クエリ1は、 [L,R) に1を引数とする作用素を適用する
2. クエリ2は、 [L,R) の prod を取ってノードを返り値として取得し、 $good=true$ なら Yes を、そうでなければ No を出力する。

AC時刻は 22:44:29 で本当に惜しかったが、D問題に時間を掛け過ぎである。幅0の区間を統合するところでバグを出してしまい、バグに気が付いたのはコンテスト終了の3分後くらいだった。ここが分かればE問題から着手して20分で解答できた可能性があり、経験の浅さが出てしまった。

実装を 整理 して、幅0のノードを適切に表現すれば、もう少し早くバグに気が付いたと思う。

• $left$ は std::optional<bool> で、幅が0なら値を持たない。幅が1以上なら true, false はそれぞれ文字列の 1 , 0 に対応する。
• $right$ も $left$ と同様に定義する
• $width$ を無くして left.has_value() で幅0かどうか分かる
• $good$ は同じ

公式解説では遅延セグメント木ではなく、普通のセグメント木を用いている。実装は こちら 。一見単純に見えるが、センチネルを上手く思いつかないと解けない。公式解説2のように、セグメント木を使わずに 解ける 。

コードはこちら

ちらっと見えたヒントは忘れたので自力ACということで。コンテストの翌日に2時間近くかかって解いた。解けたのは嬉しいが、2時間掛かったらコンテストには間に合わない。

$\sum_{y \in S} W_y < W_x$ が実はナップザック問題である。コマを配る頂点の集合 $U \subseteq S$ について、配ることの良さを最大にする頂点集合 $U$ を求めることに等しい。

配ることの良さとは、頂点 $x$ にあった $A_x$ 個のコマが、頂点 $x$ に直接つながる頂点 $y$ と、頂点 $y$ から先に間接的につながっている頂点にどれだけ伝搬するかである。つまりコマ1個につき、頂点 $x$ から $B_y \geq 0$ 個の頂点にコマが直接間接に伝搬するなら、コマ1個が $A_x \times \sum_{y \in U} B_y$ 個に増えると言える。

このような $B_x$ を求める。 $W_x$ の昇順に $B_x$ を求める。 $B_x$ をナップザック問題として解くと $x$ に対する $B_x$ の最大値が得られるのでそれに1を足す。これは頂点がつながっていてもつながっていなくてもコマを減らすことはできることと、 $B_x$ に入ってくる頂点に直接寄与する分である。頂点 $x$ については $A_x \times B_x$ 回の操作を行う。これを繰り返し、すべての頂点に置ける操作回数の和が答えである。

ナップザック問題は、縦軸(DPを更新する方法)を $B_x$ につながっている各頂点 $B_y$ を $U$ に含めるか否か、横軸を重みの総和 $[0..W_x]$ 、値を操作回数とする。更新式は省略する。この解法は公式解説と同じだった。

コンテスト18回目である。A,B,C,Dの4完である。E問題は設定が大変そうなのでF問題に59分取り組んだのだが、明らかにE問題より解答者が少ない(終わってみればG問題より正解者が少ない)F問題を自分がどうして解けると思ったのか、自分でも分からない。

コードはこちら

文字の出現回数をそれぞれ数えて、出現回数が1回の文字の場所を出力する。つまり文字列を二度スキャンする。

コードはこちら

配列の作りかたに気を付ける。 $P[x]$ は 人 $x$ の位置が $P[x]$ という意味である。0-based indexingにするならインデックスに気を付ける。

コードはこちら

Union-find木を取り出して時間を溶かし、依存グラフを作ろうとして時間を溶かし、英小文字は26種類しかないことを思い出した。英小文字の変換表(変換元は26種類、変換先は最大26種類)を更新して、最後にできた変換表に基づいて $S$ を変換すればよい。変換表は文字をキーとして作ってもいいし、 a とのアスキーコードの相対値 a..z = $0..25$ でもよい。

公式解説2の方法を作ろうとして上手くいかなかったと言える。

コードはこちら

非負整数なので例外処理が大変である。

最初に $A$ に含まれる0の数 $NZ$ を数える。 0に何を掛けても平方数0である。 0同士の組 $NZ (NZ - 1) / 2$ と、 0と非0の組 $NZ (NZ - 1)$ がある。2で割るか割らないかがややこしい。

次に $A$ に含まれる平方数を求める。1は平方数である。1以外なら $A_i$ を素因数分解して、素因数 $P_j$ が $count(P_j)$ 個含まれるとき、すべての素因数について $P_j$ が偶数なら $A_i$ は平方数である。平方数が $NS$ 個あるなら、平方数の積も平方数なのでそれらの組み合わせは $NS (NS - 1) / 2$ 組ある。

$A_i$ を素因数分解して、ある素因数 $P_j$ が 奇数個 $count(P_j)$ 個含まれるとき、そのような素因数の集合 $S_i$ を作る。平方数でない $A_i$ についてこのような集合を列挙する。それぞれの集合に属する $S_k$ が $NP_k$ 個なら、それらを組み合わせて作れる平方数は $NP_k (NP_k - 1) / 2$ 組ある。

これらをすべて足したものが答えである。

公式解説は集合ではなく、素因数の積を使っている(素因数が何個あるか決まれば、その積は一意に決まり、逆も然りなので)。 std::map のキーが集合なのにTLEしないのはC++の速さに助けられた。

コードはこちら

翌日43分掛けてACした。F問題を無視して解いていればコンテスト中に間に合ったと言えるし、問題選択の時間を含めると残り時間で解けたかどうか分からないともいえる。この43分には問題文を理解する時間が入ってないので。

ダイクストラ法をちょっと工夫すれば解ける。

電車の向きを逆向きのグラフとして持つ。つまり $B$ から $A$ に向かう有向グラフにして、配列 $Edges[B]$ の要素を $A,l,d,k,c$ にする。駅 $N$ に最後に到着する電車の到着時刻を $T_N$ とする。駅 $N$ に最後に到着する電車の到着時刻がない、つまり到達不能なら、 $f(1..(N-1))$ はすべて Unreachable である。

駅 $N$ に到達可能なら、ある時点で駅 $i$ の最終出発時刻 $T_i$ を定める。 $T_N$ は上記の値、それ以外は未初期値にした std::vector<std::optional<Num>> にする。さらに優先度キューに、ある時点で駅 $i$ の最終出発時刻 $T_i$ の組 $(T_i, i)$ を降順に積む。最初は $(T_N,N)$ だけ積む。

この優先度キューをダイクストラ法てきに処理する。その駅に到着するすべての路線 $j$ について、出発時刻を求める。遅くとも $T_{ij} = T_i - c_j$ に出発している必要がある。

• $T_{ij} < l_j$ なら始発に間に合わないので無視する
• そうでなければ出発時刻にキリ良く合わせる。 $t = l_j + min(k_j - 1, max(0, \lfloor (T_{ij} - l_j) / d_j \rfloor)) \times d_j$ が最終出発時刻である。
• $T_i$ を $t$ と $T_i$ の遅い方(もしあれば)で更新し、更新したら優先度キューに積む。出発地と到着地が同じ路線が複数あるかもしれないのでまとめて行う。

これを繰り返せば、 $T_i$ を最終出発時刻の遅い順に更新して求まる。

コードはこちら

確率DPだとは分かったが、コンテストの時間内で上手く定式化できなかった。

ディーラーには行動の選択肢が無いので、 $L \leq y \leq N$ になる確率を求められる。これは $DP_d[i=1..N]$ を $y = i$ になる確率として、 $DP_d[max(0,i-D) , min(i,L)]$ からもらうDPする。遅延セグメント木を使う。配るDPにすると 計算誤差が大きすぎてWAする 。

プレイヤーはサイコロを振るかどうか(Black Jackではカードを引くhitか、これ以上引かないstandか)の選択肢がある。よって $x = N..0$ の順に、hitとstandのどちらか有利な方を選べばよい。ちなみに $N$ を超えることをbustという。 $DP_p[i=N..0]$ を $x = i$ のときの勝率として

• Hit : Bustしない範囲でより大きな $x$ での勝率の和 $\sum_{j=(x+1)..N} DP_p[j] / D$
• Stand : ディーラーがbustせずプレイヤー以上の値を出す、つまり $y \leq N \land x \leq y$ の確率なので、 $1.0 - \sum_{j=max(x,L)..N} DP_d[j]$

のどちらか大きな方を選ぶ。プレイヤーは $x = 1..N$ でhitかstandするか決めたので、 $x=1..N$ の順に $x$ になる確率 $DP_q[i]$ と勝率を求める。

• Hit : サイコロをもう一回振って、 $DP_q[i]$ を $DP_q[i+1,i+D]$ に配るDPする
• Stand : $DP_q[i] \times 1.0 - \sum_{j=max(x,L)..N} DP_d[j]$ を勝率として足す

コンテスト中に提出した解は、hitとstandを上手く使い分けていないので入力例しか解けない。その後夜中まで掛かってWAと取り除けなかったのだが、公式解説を読んで配るDPをもらうDPにしたらACした。黄diffを自力ACできるまでほんの少し足りなかった。

コードを整理すると こうなる 。ディーラーの状態を遅延セグ木、プレイヤーがstandしたときの状態をベクタ、hit or standのどちらかいい方の勝率の累積和、ですっきりまとまる。配るDPにすると WA する。もらうDPなので、遅延評価しないセグメント木で 解ける 。

コンテスト19回目である。A,B,C,Dの4完である。E問題は明らかに難問で、F問題に82分掛けたが解けなかった。解法はだいたいあっていたが画竜点睛を欠いた。

コードはこちら

問題文をそのまま実装する。答えは一つではないので、答え合わせに時間を掛けない。

コードはこちら

問題文をそのまま実装する。0-based indexingのときに数字がずれないことと、空行を忘れずに出力するよう注意する。空行の確認に時間を使ってしまったので、空行を _ に置き換えて空行を目立たせる。

make && ./343b | sed 's/^$/_/' | grep --color -e "^.*"

コードはこちら

$N \leq 10^{18}$ なので、 $i=1..10^6$ を全探索すればいい。 $i = 1, i^3 = 1$ は回文立法数なので答えは必ずある。組み込み数値型から文字列への変換は、パディングなどがなければ std::to_string でできる。

本問では使わないが、0パディングは以下のように行う。

long long int r {343};
std::ostringstream oss;
oss << std::setfill('0') << std::right << std::setw(10) << r << "\n";
const auto s = oss.str();

printf , snprintf の方が簡潔だが整数型を指定する手間が要る。それと ios::sync_with_stdio(false); で std::cout と printf の同期を切ると上手くいかない。

long long int r {343};
printf("%010lld\n", r);

コードはこちら

F問題にも通じる。

得点 $A$ の選手が $B$ 人いるという連想配列 $(A,B)$ を持つ。ただし $B$ は正の値に限り、 $B = 0$ なら $A$ をキーとするエントリを削除する。

入力ごとに得点 $A_i$ の選手が一人減り(0人になったらキーが $A_i$ の要素を削除する) $A_i + B_i$ の選手が一人増える。 std::map<int,int> だとキーに対応するエントリがなければ値が0のエントリができるので、エントリを明示的に作らなくても0が1になる。 std::map::size() はエントリ数を返すので出力する。

コードはこちら

解説を見ずに解けなかった。

値 $A_i$ が $C_i$ 個あるという連想配列をセグメント木に載せる。セグメント木でこの連想配列をマージすると、ある区間において値 $A_i$ が $C_i$ 個あるか分かる。基本的には、タイプ1のクエリでセグメント木の一要素を変更し、タイプ2のクエリで連想配列のうち、値が2番目に大きい要素の個数(値が2番目に大きい要素がなければ0)を返す。

連想配列を全部入りにすると TLEする 。なので必要最小限の要素を載せることを考える。公式解説にある通り、ある区間について値の上位2位まで保持すれば、3位以下は要らない。詳しい説明は公式解説にあるが、部分木の3位以下は木全体の2位以内にはならないことがコンテスト中に分からず、全部入りにこだわってTLEのまま終わってしまった。

セグメント木の2区間のマージが大変である。左区間の1位 $LA1_i$ が $LC1_i$ 個、左区間の2位 $LA2_i$ が $LC2_i$ 個、右区間の1位 $RA1_i$ が $RC1_i$ 個、右区間の2位 $RA2_i$ が $RC2_i$ 個、というのを統合して、1位 $MA1_i$ が $MC1_i$ 個、2位 $MA2_i$ が $MC2_i$ 個あるとする。 std::set<int, int> を使って値が重なる場合に対処するのと、1,2位は無いかもしれないので $A > 0$ であること利用して値 $0$ を単位元にすればいい。ここの工夫を間違えるとデバッグに苦しむかもしれない。

セグメント木に載せるものは分かったのに、セグメント木トーナメントの勝ち上がり方式が分からなかったのは、後一歩惜しかったが実力が足りなかった。セグメント木にmin, maxが載ります、という程度の理解ではこの種の問題を完答することはできない。

2要素x2を2要素にするのに、std::setを使うとTLEすることがあるので、マージソートを書き下すと 速くなる 。その代わりデバッグで苦労する。

コンテスト20回目である。A,B,C,D,Eの5完である。E問題を回り道しないで速く解きたかった。

コードはこちら

| の最初の出現位置と、2番目の出現位置をスキャンする。最初の | の出現位置までと、2番目の | の出現位置から後を出力する。

コードはこちら

問題の制約をよく読む。値を1個取り出して、0か否かに関わらず保存して、0ならこれ以上読まない。出力の書き方は色々あるが、 std::ranges::reverse() した方が分かりやすいならそうする。

コードはこちら

候補を全列挙しても高々100万通りなので、候補を全部 std::set に入れてクエリに答える。

コードはこちら

祈りが通じた。

これまで作った文字列とそのコストを連想配列で保持してDPする。初期状態は(空文字列,0)である。連想配列に載っている文字列 $U$ に候補となる文字列 $S$ をつなげて $V = U + S$ を作り、( $V$ 、最小コスト) を追加する。適度に枝刈りしないとTLEしそうだが、枝刈りが十分だったかどうか確信が持てないまま、祈るように提出した。

• $|U| > |T|$ なら連想配列に追加しない
• $U$ が $T$ の接頭辞でなければ連想配列に追加しない。実はこれだけで十分だった(後述)。
• $U$ が未登録なら連想配列に追加する。コストは $U$ のコスト足す1である。
• $U$ が登録済なら、 $U$ の既知の最小コストと、 $U$ のコスト足す1のどちらか少ない方で最小コストを更新する

公式解説には計算量が書いてある。私には計算量を即座に見積もれなかった。 $U$ が $T$ の接頭辞でなければ連想配列に追加しないのを、先頭 $|U|$ 文字までのコストを確定すると解釈すればあっている(記事)、というかそのことに気づかなかった。

コードはこちら

まさかC++の理解度テストだった。

$A$ を連結リストとみなして、挿入削除操作を行えばいい。 std::list の検索は要素数 $N$ に対して $O(N)$ なので、計算量を下げる必要がある。

$A$ の要素 $a$ は常に一意なので、 $a$ からリスト要素への参照も一意になる。そこで、要素からリスト要素を指すイテレータへの連想配列を作る。Dangling iteratorが怖いのでこういうコードは普通書かないのだが、残り時間が圧していたのでやむを得ない。こういうときの decltype である。後はクエリに対応する操作を作る。

• クエリ1で、 std::list::insert() は引数のイテレータの 前 に要素を挿入して、挿入した要素を指すイテレータを返す。なので挿入前にイテレータを一つ進めて置く(要素は必ずあり std::list::end() を指さないことが分かっているので一歩進められる)。挿入した要素を指すイテレータを連想配列に入れる。
• クエリ2で、リストからイテレータが指す要素を削除し、その後で連想配列から値が指す要素を削除する。

公式解説は、これと同等の実装を手作りしている。手作りの仕方によっては、リストの先頭と末尾の扱いが大変そうである。実際に 実装 してみると、センチネルノードの扱いを慎重に定める必要があり、 $N=1$ を特別扱いしないとREする。

よく考えたらこれは Boost.MultiIndex で実装されていることを再実装するのに等しいので、Boost.MultiIndex を使って 実装 できる。コンテスト中に実装するには時間が足りなさそうだが。

最初思いついたのは、挿入操作を木構造に対応させる方法だった。しかしどこに挿入すべきかの管理と、枝の管理が煩雑で上手く整理できないままWAし、結局この方法を諦めた。上手くいかなさそうな方法に見切りをつけて正解にたどり着いたのは、過去の経験が活きたのかもしれない。逆に最初から正解を思いついていればもう数十分早く解けてパフォーマンスが大幅に上がったので、アルゴリズム力ではなくC++実装力で推す決断が最初からできていたら、と思う。