第3回日本橋ハーフマラソン 予選

失敗したと思ったが(75位で,恐らくボーダーだが)予選通過したので,少し復習した。

A:ツーリストXの旅行計画

A - ツーリストXの旅行計画

コンテスト中にやったこと

山登り/焼きなましでよさそうだと思ったので,0,1,\cdots,N-1という順から初めて,2点をswapする山登り法を試した。山登り法というのは

  • 現在の状態から「少し変わった状態」のスコアを計算して,それが現在の状態のスコアより良ければ,「少し変わった状態」を現在の状態とする。

ということを繰り返すものである。この「少し変わった状態」を近傍と呼ぶ。2点swapというのは,点を訪問する順番を表した順列において,2点を入れ替えたものを近傍とするという意味である。これをすると28万点くらいになる。
Submission #4232922 - 第3回 RCO日本橋ハーフマラソン 予選
ビジュアライザの結果はこちら。
f:id:sigma1113:20190216174359p:plain
ところで,分散の計算には「(2乗の平均値)-(平均値の2乗)」が使える。これを用いれば,実は近傍のスコアの計算をO(1)で済ませることができる。つまり状態として訪問順の他に,距離の総和と距離の2乗和をもっておけば,点を入れ替えたときに減る距離と増える距離をそれぞれ計算することができて,これは高々4箇所であるので,O(1)で更新が済むというわけである。これは差分更新と呼ばれたりする。
しかし,これをやればスコア伸びるでしょーと思って出したのだが,なんと全く伸びない。このあとBを解き,Aに戻ってきてからいろいろと試したが,結局28万点のまま終了した(152位)。悲しいね。

反省会

山登り/焼きなましというのは悪くなかった。問題は近傍の選び方であった。2点swapでは,パスを構成する辺が4つ変わっていることになる。これは全然「少し」変わった状態じゃないという問題があった。ここから,近傍として「パスのうち2辺を変更する」ということを考える。これは2-optと呼ばれる手法(?)らしい。そんなこと簡単にできるのかとちょっと思うが,訪問する順番の順列のある区間をreverseするだけでできる(絵を描くとわかる)。
なんとこれだけでスコアが150万点くらいになる(!?)。およそ5倍になっている。コンテスト終了後,TwitterのTLでは,「スコアが5倍になった」というツイートが散見された。
Submission #4238797 - 第3回 RCO日本橋ハーフマラソン 予選
ビジュアライザはこちら。大幅に改善している...。
f:id:sigma1113:20190216180528p:plain
この提出は差分更新をしていないのだが,2点swapのときと同様に差分更新にして,焼きなまし法に変更すると,220万点が出る(30位相当)。焼きなまし法はパラメータの調整が面倒なのだが,以下の記事を参考にいろいろ試したらうまくいった。ありがとうございます。
焼きなまし法の適用メモ - Negative/Positive Thinking
提出はこちら。
Submission #4276320 - 第3回 RCO日本橋ハーフマラソン 予選
ビジュアライザはこちら。
f:id:sigma1113:20190216181033p:plain

上位陣の考察を見ていると,使う辺の長さの範囲を限定したり,ある長さを決め打ってその長さに近い辺を使うということをしていた。この長さを決め打つという手法は有効らしく,「長さを乱数で決め打って,決め打った長さに最も近いものを選びながら,先頭から順番にパスを構成していく」だけで80万点が出るらしい(自分は試していない)。マラソンわかりません。

B:ファーマーXの収穫計画

B - ファーマーXの収穫計画

コンテスト中にやったこと

大きい数字である9や8をたくさん作って収穫したいと思った。ところが,1とか2を9にしても手数がかかるのでよくなさそうだ。そこで,てきとうに閾値を決めて,閾値以上のマスは収穫したい数字にする,ということをした。閾値は収穫したい数字の半分以上とした。収穫したい数字は9から始めて,9を収穫しきったら8を試す....ということを繰り返した。実装上はBFSを何回かすることになる。なんとこれだけで54万点が出る。
さらに,9のマスはいくつかあるわけだが,収穫する順番を乱数で決め,時間いっぱい試すことにより,55万点に乗った。これが最終スコアになった(38位)。やったことは非常にシンプルだが,これでそこそこ上位が取れたのは助かった。
Submission #4236103 - 第3回 RCO日本橋ハーフマラソン 予選
ビジュアライザはこちら。ほとんど9で収穫している。よく見ると8も少しある。
f:id:sigma1113:20190216183234p:plain

反省会

大きい順にとる,というだけでは,手数の問題をまだ十分に考慮しきれていない。ある区画を収穫するときに,その区画を収穫すると1手あたり何点得られるか?ということを考えるのは,言われてみれば自然なことのように思える(まあ気づけなかったんですが...)。そこで,「ある区画を収穫するときに得られる得点/その区画を収穫するまでにかかる手数」を評価値とする。このとき,「その区画を収穫するまでにかかる手数」は小さくしたいから,収穫するマスの値をKとすると,「隣接するKマスの値Kにするのに必要な手数の最小値」を求める必要があるが,これはbfsの際に優先度付きqueueを用いることで可能になる。
すべてのマスについて評価値を計算した後,それが大きい順に実際に手入れ,収穫をする。評価値が最大でないマスは,すでに本当は使いたかったマスが収穫されていしまっているということがあり得るが,その場合は評価値を再計算する。これを手数の限り繰り返す。
なんとこれをすると60万点に乗り,2位相当となる(!)。何を評価値すればよいかということをしっかり考えることが重要だと思わされた。
Submission #4267434 - 第3回 RCO日本橋ハーフマラソン 予選
ビジュアライザはこちら。要はコスパの良い順なので,さまざまな数字が収穫されている。また,収穫されているマスが各段に増えている。
f:id:sigma1113:20190216185003p:plain


せっかくなので本戦も頑張りたい。

AGC009-C:Division into two

きれいな問題だなあと思った。

解法

 簡単のためA\lt Bとする。逆のときはswapしても問題ない。こんなのdpしかないやろという見た目がするので,dpを考える。制約を無視すれば,今何番目の数を見てるかということと,XまたはYに最後に振り分けた数はどれだったかということが必要に見える。そこでdp_{i.j}を「i番目まで振り分け済みで,最後にYに振り分けた番号がjのときの振り分け方の総数」とできる。遷移は,①S_i-S_{i-1}\geq Aならdp_{i-1,j}からdp_{i,j}に遷移できる。また,S_0 = -\inftyとして,0\leq j \leq i-1について,②S_i-S_j\geq Bかつ,j+1からiの間の2項間の差がすべてA以上であるときに,dp_{i-1,j}からdp_{i,i}に遷移できる。(なぜj+1からかというと,S_j-S_{j+1}\lt Aでも,S_jYに振り分けているから,j+1Xに振り分ければ問題ないからである。)もちろんこれを愚直にやるとO(N^3)で,到底間に合わない。
 よく考える。まず,「jからiの間の2項間の差がすべてA以上である」かということをdpの更新のときに逐一調べる必要はない。つまり,S_i-S_{i-1}\lt Aであれば,S_{i-1}より手前の数は,これ以降②タイプの遷移が不可能だとわかるので,そういう番号を管理する変数を持っておけばよい。これをidとし,定義を「現時点で②のタイプの遷移が可能な番号の最小値」とする。さらに,S_i-S_j\geq Bをみたす最大のjを二分探索し,それをsとすると,dp_{i,j}に遷移してくるのはj2つ目の添え字がidからsまでの数である。だから,累積和を取っておけば②のタイプの遷移はO(\log N)で可能である。
 タイプ①の遷移だが,これは1つ目の添え字が1増えるだけである。タイプ②の遷移も,1つの目の添え字は1増えるだけだから,結局dp_iを「最後にYに振り分けた数の番号がiであるときの振り分け方の総数」として,これをiが小さい順に埋めれば十分である。最後に,明らかに答えが0になるパターンの存在に気を付けよう。それは,あるiが存在してS_i-S_{i-2}\lt Aとなることである。S_{i-1}XにもYにも振り分けることができなくなるからだ。
 以上より,次のようにすればよい。

  1. S_i-S_{i-2}\lt Aとなるiがあったら答えは0
  2. dp_iを「最後にYに振り分けた数の番号がiであるときの振り分け方の総数」とし,dp_0=1とする。また,idを「現時点で遷移してくることが可能な番号の最小値」とし,id=0とする。iが小さい順にこれを埋める。最初に,dp_i += dp_{i-1}とする。S_i-S_j\geq Bをみたす最大のjsとし,s\geq idであればdp_i += dp_s-dp_{id-1}とする(s\lt idのときは遷移できない)。最後に,S_i-S_{i-1}\lt Aであればid=i-1とする。
  3. 答えは,dp_N-dp_{id-1}である。

実装

Submission #4183566 - AtCoder Grand Contest 009
二分探索のとき,s=0のときの扱いに注意。あとid=0のときも注意。

ちゃんと考察すると綺麗な遷移でコードも短い,好き。

CODE THANKS FESTIVAL 2018-H:Median Game

これはわかればシンプルで楽に解けるので好き。

解法

このゲームでは,ある列の中央値がゲームのスコアになり,それを求めよと言われている(偶数のときは2つ候補があるが,大きいほうをとる)。中央値を求める問題では二分探索が有効である。中央値がx以上となるか?という質問に答えるには,数列の中にxより以上の数が半分以上含まれるかを調べるだけでよく,これは比較的容易にできるためである。

それでは,「ゲームのスコアはx以上になるか?」という問題に答えよう(この問題はxについて答えが単調なので,二分探索が使える)。このとき,Aliceはスコアを大きくしたいので,x以上の数を増やしたいはずである。一方Bobは,スコアを小さくしたいので,xより小さい数を増やしたいはずである。この2人の戦いをdpによって見守ろう。

  • dpAlice[i]:上からi枚目以降のカードが残っているときにAliceの手番で,(x以上の個数)-(x未満の個数)の最大値
  • dpBob[i]:上からi枚目以降のカードが残っているときにBobの手番で,(x以上の個数)-(x未満の個数)の最小値

dpの遷移であるが,とりあえずAliceの手番のときを考えよう。今回はこのdpにO(N^2)かけてよいので。i\lt j \leq N+1について,区間[i,j-1]のカードをとり,j枚目以降のカードを残してBobに手番を渡すとしよう(j=N+1のときはゲーム終了という意味)。これらのカードの総和をSとすると,Sxの大小によってdpBob[j]1を足すか-1を足すかすればよい。この結果のjについての最大値がdpAlice[i]である。Bobの手番のときも同様である。
dpの遷移は後ろから,つまりi=Nから行うことに注意。ゲームでdpをするときの定番だろう。「ゲームのスコアはx以上になるか?」という問題の答えは,dpAlice[1]\geq 0のときYes,そうでないときNoである。

実装

Submission #4127440 - CODE THANKS FESTIVAL 2018
実装は軽い。dp配列の初期化だけ注意。


本番はほとんど問題文を読まなかったが,もったいなかったかもしれない。

CODE THANKS FESTIVAL 2018-G:Sum of cards

詰め切るのが大変。本番で通した人たちすごい。

解法

カードiについて,A_i,B_iどちらか一方のスコアを獲得できるという状況だ。こういう状況は,グラフにしてみたくなる。1からNの数字が頂点,辺をA_i,B_iの間に結んだグラフを考えよう。このグラフは,どの頂点も次数が2であり,円形のグラフの集まりになる。A_i,B_iのどちらを表にするかということを辺の向きで表現しよう。A_i,B_iのうち,辺が入る方を表にする,ということにする。するとこの問題は以下のように書ける。

  • N頂点の,円形のグラフが集まったグラフがある。各頂点には1からNの数字が書いてある。このグラフの各辺に向きをつけ,各辺について,その辺が入る頂点に書いてある数字だけスコアを得る。少なくとも1本は辺が入ってくる頂点がK個以上あるという条件のもとで,スコアの最大値を求めよ。

この問題を解いていこう。

円形のグラフが1つのとき

まずは円形のグラフが1つのときを考えよう。これをどう解くかで既に難しく思えるが,なんとここでdpをする(初見厳しくないか...)。どのような状態を持つべきかを考えよう。まず,便宜的に頂点番号を0,1,n-1とする。nは円形を構成する頂点の数とする。今どの頂点をみているかということは当然必要だろう。また,辺が入ってくる頂点の数に制約があるので,これも状態としてもっておきたい。さらに,この「辺が入ってくる頂点の数」をカウントするために重要な情報がある。それは,頂点i-1頂点iの間の辺の向きである。この頂点の向き次第で,頂点i-1から頂点iに移るときに,辺が入ってくる頂点の数が変わってくる。では

  • dp[i][j][k]:頂点iまでで辺が入る頂点の数がj個,kは頂点i-1と頂点i間の辺の向きを表す。k=0のときに頂点iから頂点i-1に辺が入る。k=1のときはその逆とする。

で十分だろうか?とりあえずこの場合の状態遷移について考えてみよう。便宜上,i=1から始め,i=n-1まで見た後,i=0をみることにする。

k=0のとき

i-1k=0のときは以下の図のようになる。i-1には辺が入っていなかったが,iから出る辺で入ってくるようになるので,jの添え字が1増える。
f:id:sigma1113:20190130234314p:plain
また,i-1k=1のときは以下の図のようになる。i-1にもともと辺が入っていたので,jの添え字は増えない。
f:id:sigma1113:20190130234332p:plain

k=1のとき

同様に考えればよい。
i-1k=0
f:id:sigma1113:20190130234637p:plain
i-1k=1
f:id:sigma1113:20190130234702p:plain

というわけで遷移が書けた。めでたしめでたし...と言いたいのだが,ここには罠がある。そう,いま考えているグラフは円形であったから,頂点0と頂点1の間から順に見ていって,最後に頂点n-1と頂点0の間を見ることになるが,このときに,上で述べた遷移にはならないパターンがある。以下の2つの図を見比べてみよう。
頂点0から頂点1に辺が出ているとき
f:id:sigma1113:20190131000413p:plain
頂点1から頂点0に辺が出ているとき
f:id:sigma1113:20190131000423p:plain
i-1からiに辺を伸ばすときは基本的に辺が入る頂点の数は増えるはずであったが,一周して戻ってくるときだけは,そうならないのである。よって,この3次元DPを素直にやるだけではうまくいかないのだ。ではどうするか?答えはシンプルで,「0から1に辺が出ているか」それとも「1から0に辺が出ているか」ということを状態としてもてばよい。そうすればn-1から0の遷移の際にのみ気をつけることで,この問題を回避できる。つまり

  • dp[i][j][k][l]:頂点iまでで辺が入る頂点の数がj個,kは頂点i-1と頂点i間の辺の向きを表す。k=0のときに頂点iから頂点i-1に辺が入る。k=1のときはその逆とする。lは頂点0と頂点1の間の辺の向きを表す。l=0のときに頂点1から頂点0に辺が入る。l=1のときはその逆とする。

これで円形1つのときの問題を解くことができた。頂点が1つのみのときに注意。

円形のグラフが複数あるとき

さて,この問題でグラフを作ったときに,N個の頂点すべてが連結になるとは限らない。よって,上のようにして各円について問題を解くことはできるが,その結果をまとめてやる必要がある。しかしこれは難しくない。円が全部でM個あるとしよう。各円について,辺が入る頂点がk個あるときのスコアの最大値がわかっている。このとき,floor(\frac{M+1}{2})\leq k \leq Mであることに注意しよう。それならば

  • dp2[i][j][k]:i個目の円のj番目のありえる辺が入る頂点の個数まで考えたときに,合計で辺の入る頂点の個数がkのときのスコアの最大値

j番目のありえる辺が入る頂点の個数」というのは,t=floor(\frac{M+1}{2})とすると,t,t+1,\cdots,Mに新たに1,2,\cdots mという番号を振りなおしたと考えればよい。遷移はナップサック問題のような形になる。このうち,kKより大きいものの最大値が答えとなる。

この解法全体の計算量はO(NK)である。

実装

Submission #4129625 - CODE THANKS FESTIVAL 2018
これが参考になるかわからないが,上で述べたことを書くとこんな感じになる。各円の結果をまとめる部分で,前の円の大きさを保存しておかないといけなかったりなど,実装上面倒なことは多い。もう少し楽な実装方針があるかもしれない。

大変だが,勉強になる問題であった。ちなみにうまくやると最大費用流になるらしい。

CODE THANKS FESTIVAL 2018 F-Coins on the tree

本番は誤読をした...。

解法

 辞書順最小を作れという指示がある。辞書順最小ということは,前の数字が小さいことが正義である。ならば,先頭から「1にできるか?」を判定し,できるなら確定,できないなら「2にできるか?」ということを判定,というように貪欲に試していこうという方針は自然である。

 それでは,試しに1番目のコインを頂点vに置けるかということを判定することを考えよう。まず,コインを頂点vに置いたのだから,木の根からの距離をd_v(ただし,d_{根}=1とする)とすると,手数をd_vだけ消費する。ここから,残りのM-1枚を,K-d_v手でピッタリ置ききる必要がある。このようなことが可能であるvの条件がわかればよい。
 まず,vに置くと決めたら,vの子孫たちはもう使えないことに注意しよう。つまり,1番目のコイン以後に使える頂点の数が減るのである。このとき,もし使える頂点の数がM-1を下回るようなことがあれば,1番目のコインをvに置くことはできない。
 使える頂点の数はクリアしたとして,手数の問題を考える。残り手数をピッタリ消費する,という条件は扱いにくいが,このような場合は可能な手数の上限と下限を考えるとうまくいくことがある。まず,手数の上限は,到達可能な頂点のうち,d_uを大きい順にM-1個取ったときの和である。消費する手数をできるだけ多くするには,できるだけ根から深いところにコインを置くようにすればよいので,このことがわかる。同様に,手数の下限は,d_uを小さい順にM-1個取ったときの和である。理由は上限と同様である。そして,この上限と下限の間の手数の消費は必ず可能である。手数の下限の状態から,手数の上限の状態までコインを順番に動かすことを考えれば,このことがわかる。以上より,K-d_vがこの上限と下限の間にあれば,コインを頂点vに置くことが可能となる。
 この判定は高速にできるだろうか。高速といっても,本問ではO(N)くらいかけてよい。それならば,到達可能な頂点をすべて訪問し,d_uのリストを作る。リストのサイズがM-1より大きいことを確認した後,これらの大きいほう,そして小さいほうからM-1の和をそれぞれとり,K-d_vと比較すればよい。sortを使ってもO(N\log N)でできる。
 1番目のコインをvに置くことが可能だとわかったら,Kd_vだけ減らし,2枚目のコインについても同様にどの頂点に置けるかを番号の小さい順に調べる。このようなことを繰り返せば,辞書順最小のコインの置き方が求まる。もし,あるコインがどの頂点にも置けないということであれば,-1を出力すればよい。

以上をまとめて,次のようにすればこの問題が解ける。

  1. 最初に,各頂点vについてd_vを求める。
  2. i番目のコインを頂点vに置けるか,ということをvが小さい順に試す。到達可能な頂点を訪問しながら,d_uのリストを作って,判定を行う。置ける条件は,①d_uのリストのサイズがM-i以上であること かつ ②d_uの小さいほうからM-i個の和をsum1,大きいほうからM-i個の和をsum2とすると,sum1 \leq K-d_v \leq sum2であること の2つ。ただし,このKi番目のコインを置こうとしている時点での残り手数を表している。頂点vに置けるとわかれば,Kd_vだけ減らして,次のコインに進む。置けないなら,次の頂点を試す。どの頂点にも置けないとなれば,-1を出力して終わり。
  3. M枚目のコインまで置けたら,結果を出力して終わり。

全体の計算量はO(MN^2\log N)である。

実装

Submission #4123308 - CODE THANKS FESTIVAL 2018
dfsが3つあるが,それぞれの役割は以下にようになる。

  • dfs(n):d_nを計算する関数。
  • dfs2(n,m):判定パートで,到達可能な点を訪問する関数。used_nというのは,それがtrueのときに頂点nにはコインを置けないということを表してる。頂点nを訪問したら判定用のリストにd_nを追加する。nの子がmまたはused_nがtrueなら,その子孫はもうコインが置けない頂点なので,その先には訪問しない。
  • dfs3(n,m):ある頂点vにコインを置くと決まった後,vの子孫にはもうコインは置けないということを記録しに行く関数。頂点番号の小さい順から試すということをするため,この作業を怠ってはいけない。

判定パートが若干混乱するが,整理すると綺麗な問題だなあと思う。

NIKKEI Programing Contest-E:Weights on Vertices and Edges

良問だと思ったので記事にすることにした。Cさえなければ....。

解法

こういう重み付きの辺を追加/削除して連結成分が...という問題は,辺が一本もない状態から,一定の順番で辺を追加していくことを考えることで道が開けることがある。
N頂点の辺が0本のグラフから,辺の重みが小さい順に辺を追加していくことを考えてみる。このときに,連結成分の重みをもちながら連結していく必要があるが,これはUnion-Findにちょっと書き足せばできる(コード参照)。さて,ある辺eを追加したときにできた連結成分S_eが,問題の条件を満たしたとしよう。すると,辺の重みが小さい順に追加していったという仮定から,この連結成分S_eに属するすべての辺は,問題の条件を満たす。つまり,S_eに含まれる辺は残してもよいことになる。このようにして,辺を追加していきながら,条件を満たす連結成分の集合S_{e_1},S_{e_2},\cdots.S_{e_n}がわかる。これらの和集合に属する辺たちを残しておけば,条件を満たすグラフが作れる。では,残すべき辺たちはどのようにして調べることができるだろうか。Union-Findしながら,重複をはじきつつ辺の数を数えるのは難しく見える。
ここで,S_eの見方を変えてみる。辺eの重みをw_eと書くと,S_eは,「eから重みがw_eの辺のみを使っていくことができる頂点の集合」であることがわかる。つまり,S_eを求めるためには,eが結ぶ頂点から適当にdfsやらbfsやらをするだけでよいことがわかる。本当に求めたいのはS_{e_1},S_{e_2},\cdots.S_{e_n}の和集合で,何も考えずにやるとO(N^2)かかってしまうが,e_1,\cdots,e_nのうち,w_eの大きい順に調べていけば,w_e \leq w_e'かつS_e \cup S_{e'}\neq \emptysetのとき,S_e \subset S_{e'}になるので,O(N+M)で終わる。
以上のことより,次のようなアルゴリズムを考える。

  1. まず,重みの小さい辺から順にグラフに追加していく。もし,この辺eを追加したことによってできた連結成分が条件を満たすなら,eをリストに追加する。
  2. 上の作業が終わったら,リストに追加した辺のうち,重みの大きいものからS_eを求め,残すべき辺の数を数える。
  3. M-(残すべき辺の数)が答え。

最後に,このアルゴリズムが正しい解を返すことを確認しよう。まず,グラフの重みが最大の辺が条件を満たさないなら,その辺は削除されなければならない(1の正当化)。満たす場合,その辺と同じ連結成分に属する他の辺も条件を満たすので,その連結成分については辺を削除する必要がない(2の正当化)。この議論に沿った手続きを再帰的に行っているのが上のアルゴリズムであり,正当性がわかる。(解説の通り帰納法で書いた方がすっきりするかも?)

提出

Submission #4117234 - 全国統一プログラミング王決定戦予選/NIKKEI Programming Contest 2019

  • Union-Findのsという配列が,連結成分の重みをもっている。
  • 2に使う辺の管理だが,小さい順にリストに追加して,大きい順に取り出すので,stackを用いるのが楽だと思った。

Cでハマってしまい本番はこの問題を詰め切れず,本選出場も逃したが,観戦権は得ることができた。よろしくお願いします。(誰に対して言ってるんだろう...。)

ABC116-D:Various Sushi

解法自体は素直なので400点なのだろうが,見た目はとっつきにくいので難しいと思った。

考察・解法

食べることにする寿司の集合をSSのネタの種類をf(S)と書くと,\sum_{i\in S} d_i + f(S)^2の最大値を求めることになる。解法はさまざまだが,ここではd_iの和にまず注目することにする。この部分を最大化するのは簡単で,d_iが大きいK個を取ればよい。これらK個の集合をS_0としよう。これが最適解とは限らないというところが難しいのだが,これより良い解があるとしたら,それはネタの種類がf(S_0)より大きい場合に限る。だから,f(S_0)からネタの種類が増えるようにS_0の要素の寿司を交換していくことを考えたくなる。さらにこのとき,おいしさの和の項ができるだけ大きくなるようにする(どうしても小さくなるわけだが,それを最小限にする)必要がある。これはどのようにすれば効率的な計算時間で可能だろうか?

まず,S_0を決めるために(d_i,t_i)でソートしておく。これによりd_iが大きい方からK個とり,S_0f(S_0)を計算する。さらに,実際にS_0に含まれるネタの種類とそれぞれの種類の寿司の数を記録しておく。ここまでやってスタートである。
ここからネタの種類を増やしていく。まず,K+1番目にd_iが大きい寿司iのネタt_iの種類を見る。同じネタがS_0にあるなら,S_0のどの寿司を入れ替えてもネタの種類は増えないし,おいしさの和は減るだけなので,交換する必要はない。t_iS_0にない場合,何かと交換することでネタの種類が増える場合がある。この場合,交換に出すべきS_0の寿司として最適なものは,「S_0に2つ以上含まれるネタの寿司の中で,もっともおいしさが小さいもの」である。このような寿司を選ぶことで,おいしさの和が小さくなることを最小限に抑えることができる。S_0に1つしか含まれない寿司を交換に出しても種類が変わらないことに注意しよう。
以上の手続きを繰り返すことで,おいしさの和を最小限に抑えながら,ネタの種類を増やしていくシミュレーションができる。食べる寿司の集合Sが更新されるごとに答えの候補として試し,最大値を出力する。計算時間はO(N)またはO(NlogN)でできる。

提出

Submission #4063050 - AtCoder Beginner Contest 116
これを実装してくださいと言われてもまだ大変かもしれない。上のコードでは,S_0を求めたあと,r=N-K+1とおき,これを交換する候補の最初のindexとしている。また,食べる寿司の集合のネタの種類と数はmapで管理した。ここから寿司rが交換に出す寿司の候補としてふさわしいか判断し,だめなら寿司r+1を試すということを繰り返している。r=N+1となったら,もう交換に出せる寿司の種類はないということなので,処理を終了してよい。mapを使っているので計算時間はO(NlogN)となっている。

  • ABC Only回としては難しい,でもこういう問題好きです。
  • こどふぉと被っていて,こどふぉはratedなのでそっちに出ていた。
  • 〇〇 Sushi という問題は難しめという謎の習慣...?