Codeforces Round 966 (Div. 3)に参加した

8月13日に開催されたCodeforces Round 966 (Div. 3)に参加した．結果はABCDEFGの7完で275位．

Div. 3はコンテスト終了後にHackのフェーズが12時間ありその後でようやくシステムテストが始まるので，レート更新を待つ時間が永遠に感じられた．

A - Primary Task

問題概要

問題文

整数$a\;(1\leq a\leq 10^4)$が与えられるので，以下の条件を満たす整数$x\;(x\geq 2)$が存在するかどうか判定せよ．

• 条件：$a$の（leading zeroなしの）$10$進表記と，'10'の末尾に$x$の（leading zeroなしの）$10$進表記を追加したものが一致する．

考えたこと

コーナーケースに注意して丁寧に判定していく．$a$の$10$進表記を$\tilde a$とすると，以下の条件がすべて満たされていればよい．

• $\tilde a$は$3$文字以上
• $\tilde a$の最初の$2$文字が'10'
• $\tilde a$の$3$文字目は'0'でない
• $\tilde a$の$3$文字目以降を$10$進整数として解釈したとき，その値が$2$以上

Rustでの文字列操作はやっぱりまだ慣れない．

提出：https://codeforces.com/contest/2000/submission/276116576

B - Seating in a Bus

問題概要

問題文

$n$個の座席$1,\cdots, n$が$1$列に並んでいるバスがある．$n$人の乗客$1,\cdots, n$がこの順にバスに乗り込み，乗客$i$が座った座席は$a_i$であった．このとき，以下の条件が成り立つか判定せよ．

• 条件：$i>1$ならば，乗客$i$の座った座席に隣接する座席であって，すでに別の乗客が座っているものが存在する．

考えたこと

座席iが埋まっているかを表す配列occupied[i]を管理しつつ，乗客$1,\cdots, n$の順に条件が満たされているかどうかを逐次的にチェックしていけばよい．座る席が端っこのとき配列外参照しないように注意．

提出：https://codeforces.com/contest/2000/submission/276133887

C - Numeric String Template

問題概要

問題文

長さ$n$の整数列$(a_i)$と整数$m$が与えられる．$j=1,\cdots, m$に対して，以下の$m$個の判定問題を解け．

• 英小文字だけからなる文字列$s_j$が与えられる．以下の条件がすべて満たされるか判定せよ．
  • $|s_j|=n$
  • $a_i=a_{i'}$となる任意の$1\leq i,i'\leq n$に対して，$s_i=s_{j'}$
  • $s_i=s_{i'}$となる任意の$1\leq i,i'\leq n$に対して，$a_i=a_{j'}$

考えたこと

要するに，整数と英小文字が1対1対応するかを判定すればよい．そのためには，$i=1,\cdots, n$の順に数列と文字列を同時に走査しながらHashMapなどを用いて「整数→英小文字」と「英小文字→整数」の対応を記録していき，対応先が複数存在する箇所を発見したら答えをNOとする．

提出：https://codeforces.com/contest/2000/submission/276161477

D - Right Left Wrong

問題概要

問題文

長さ$n$の正整数列$(a_i)$と，LまたはRからなる長さ$n$の文字列$s$が与えられる．あなたは以下の操作を$0$回以上好きな回数だけ行うことができる．

• 操作：まだ選んでいない整数の中から，$s[l]=$Lかつ$s[r]=$Rを満たす整数$l, r\;(1 \leq l < r\leq n)$を選ぶ．これにより$s[l]+\cdots +s[r]$点を得る．

このとき，最終的に獲得することのできる点数の最大値を求めよ．

考えたこと

操作が$1$回までしか許されないなら簡単で，最左にあるLと再右にあるRを選ぶのが最適である．操作が複数回許される場合でも，できるだけ区間の幅が大きくなってほしいというのは変わらないので，直感的には「まだ選んでいない端点のうち，最左にあるLと再右にあるRを選ぶ」ことを繰り返せばよいように思える．これは，累積和を構築したのちしゃくとり法の亜種のように区間の左端と右端を管理するポインターを左と右から走査させていくことで$O(n)$でできる．

さすがに未証明のまま満足するのはよろしくないのでざっくりに正当性を考えておく．最大値を与えるような操作列$(l_1,r_1),\cdots, (l_m, r_m)$があったとする．まず，操作順は得られる点に影響しないので$l_1<\cdots < l_m$としてよい．さらに，$l_i < l_j < r_j < r_i$とならないような$i < j$が存在した場合，端点を組み替えることで点の総和を悪化させずに$l_i, l_j, r_j, r_i$をこの順に並べることができる．よって最適解の形ははじめから$l_1 < \cdots < l_m < r_m < \cdots < r_1$の形だけ考えればよく，その制約下では確かに「まだ選んでいない端点のうち，最左にあるLと再右にあるRを選ぶ」のが最適である．

提出：https://codeforces.com/contest/2000/submission/276184108

E - Photoshoot for Gorillas

問題概要

問題文

$w$匹のゴリラがおり，$i$番目のゴリラの身長は$a_i$である．

$n\times m$のグリッドと整数$k$が与えられたとき，グリッド上の異なる$w$個のマスを選んでゴリラを配置することを考える．ゴリラ$i$をマス$(x_i, y_i)$に配置したとき，その配置の眺めの良さ$s$（spectacle）を，グリッド上の$k\times k$の正方形領域に含まれるゴリラの身長の総和をすべての正方形領域について足し上げたもの，と定義する．より厳密には

である．このとき$s$の最大値を求めよ．

考えたこと

マス$(x,y)$にゴリラ$i$を配置したとき，上の和に$a_i$が何回登場するかを考える．これはマス$(x,y)$を含むような$k\times k$領域の個数に一致し，その数は

と$O(1)$で求められる（あるいは2次元imos法を使って$O(nm)$かけてまとめて計算してもよい）．

こうして各マス$(x,y)$にゴリラを置いたときの重みが分かったので，あとは身長が高い順に重みの大きいマスに割り当てていけばよい．この貪欲パートの計算量は$O(nm(\log n+\log m)+w\log w)$である．

提出：https://codeforces.com/contest/2000/submission/276214198

F - Color Rows and Columns

面白かった！

問題概要

問題文

$n$個の長方形があり，$i$番目の長方形は$a_i$行$b_i$列のグリッドである．あなたは以下の操作を何回でも行うことができる．

• 操作：いずれかのグリッドのまだ色が塗られていないマスを選び，そのマスに色を塗る．
  • そのマスに色を塗ったことにより，そのマスを含む行のすべてのマスに色が塗られた状態になった場合は，新たに$1$点を獲得する．
  • そのマスに色を塗ったことにより，そのマスを含む列のすべてのマスに色が塗られた状態になった場合は，新たに$1$点を獲得する．

$k$点以上をとるために必要な操作回数の最小値を求めよ．$k$点以上を獲得することが不可能な場合は-1を出力せよ．

考えたこと

最適な手筋は単純な構造をしていなさそう．サイズの小さいグリッドから塗っていくのは必ずしも最適とは限らず，複数のグリッドをまんべんなく塗っていくほうが効率がよいこともありそうだ．また，グリッドを選んでもすべてのマスを塗るとは限らず，いくつかの行や列が埋まった状態で終わりにするほうがよい場合もあるだろう．

いろいろ考えるうちに，この問題を次のように言い換えるのがよいことが分かった．

それぞれの長方形に対して「色を塗るか塗らないか」「塗るとしたらどこまで塗るか」が選択できるとき，操作回数の最小値は？

このような枠組みで問題を捉え直すと，これがまさしくDPで解ける構造をしていることが分かる．具体的には，

• ${\rm dp}[i][j]$：$i$番目の長方形まで塗り方を決めたとき，獲得点数が$j$であるような塗り方に対する操作回数の最小値

のようなDPテーブルを定義して逐次的に値を求めていけばよい．

ただし遷移は少し複雑だ．まず長方形$i$を塗らない場合に対応して

という更新をする．

問題は長方形$i$を塗る場合だ．マスをどこまで塗るかによって得られる点数が異なるため，$p=1,\cdots, a_i+b_i$のそれぞれに対して，$p$点得る場合に要する最小操作回数$w_p$を計算する必要がある（得られる点数はマスを全部塗ったときが最大で，このとき行数と列数の合計である$a_i+b_i$点が入る）．注意しなければならないのは，「つねに行方向に塗る」「つねに列方向に塗る」などの戦略は必ずしも最適であるとは限らない点である．例えば$3\times 3$のグリッドを塗るとき，つねに一方向に塗るよりも

  xxx  3  ooo  2  ooo  2  ooo  1  ooo  1  ooo
  xxx  →  xxx  →  oxx  →  ooo  →  ooo  →  ooo
  xxx     xxx     oxx     oxx     oox     ooo

のように，交互に塗ったほうが（最終的に獲得する点数は同じでも）早く点数を獲得できる．より一般には，塗る方向を新たに決めるたびに，その行／列を塗るために必要な操作回数（まだ色が塗られていないマスの数）がより少ない方向を貪欲に選んでいくとよい．これを$p=1,\cdots, a_i+b_i$の順に行っていき，その都度

という更新を行えばOKである．

このDPの状態数は$O(nk)$，遷移は各$i$に対して$O(a_i+b_i)$で，制約が$1\leq n\leq 10^3, 1\leq k\leq 10^2, 1\leq a_i,b_i\leq 10^2$なので実行時間制限に十分間に合う．

提出：https://codeforces.com/contest/2000/submission/276255664

G - Call During the Journey

TL 4 secとRustに甘えてlogを2つ付けました……

問題概要

問題文

$n$頂点$m$辺の単純無向グラフが与えられる．あなたは頂点$1$を時刻$t\;(< t_0)$に出発し，辺を移動して頂点$n$まで移動する予定である．

各辺$i=1,\cdots, m$には$2$種類の重み$l_{i}^{(1)} < l_{i}^{(2)}$が設定されており，それによって辺$i$を通る際の所要時間が以下のように決まっている．

• バスを使って移動する場合，時間が$l_{i}^{(1)}$だけかかる．
• 徒歩で移動する場合，時間が$l_{i}^{(2)}$だけかかる．

また，あなたは任意の頂点で任意の時間だけ立ち止まってもよい．

加えて，時刻$t_1$から時刻$t_2\;(t_1 < t_2 < t_0)$には電話の予定があり，この間（端点$t_1, t_2$を含まない）にバスに乗っていてはならない．

このとき，頂点$n$への到着時刻が$t_0$以下であるような出発時刻$t$の最大値を求めよ．

考えたこと

問題設定は複雑だが解き方はシンプル．

ひとまず$t$を固定して考えると，頂点$n$への最も早い到着時刻はダイクストラ法で求めることができる．遷移がやっかいだが，時刻$t'$に頂点$v$を出て辺$i$を移動するとき，考慮すべきなのは

• $l_{i}^{(1)}$だけかけてバスで移動する（$t' + l_{i}^{(1)} \leq t_1$または$t_2 \leq t'$のときに限る）
• $l_{i}^{(2)}$だけかけて徒歩で移動する
• 電話が終わるまでその場にとどまってから，$l_{i}^{(1)}$だけかけてバスで移動する（$t' < t_2$のときに限る）

の3つで十分である．

$t$を固定したときの判定問題が解けたので，あとは$t$の境界を二分探索で求めれば$O((n+m)\log n\log t_0)$でこの問題に答えることができる．

後から気づいたが，頂点$n$を起点として逆向きにダイクストラ法を適用すれば二分探索なしで求めることが可能である．

提出：https://codeforces.com/contest/2000/submission/276275564