okimochi ICPC2019 模擬国内予選 参加記

参加資格ありのチーム内で5位!チームとしての上限に近いパフォーマンスだったと思う。

 

 

Aをまず通す。その間にBは01bfsやるだけですと言われたので受け取り、難なく通す。少しバグらせたのでここまで15分くらいかかってしまったが、そこそこ早かったようだ。

 

一方Cが怪しいながらもこるとんが書き始める。その間にDとEを読み、EがすぐにはわからないのでDがわからないというrisujirohにEを投げる。数分でEの解法が分かり(早い…)、Cが通らないらしいのでrisujirohがEを書き始め、僕がC、こるとんがDを見る。EがバグったがこるとんがDがいけるというので交代する。その後DとEを交代しながら連続で通しきる。なんかEはbitsetの宣言がよくなかったらしい。

その後、Cが注意力だけどいけそうという気持ちになる。1回WAを貰ったあと(ごめん)テストケースを見られることを思い出し、落ちているケースを探す。(0,奇数)みたいなケースが考慮できていないとわかり、実装して通す。ここまで90分で、8位くらいだった気がする。

 

ここから苦しい時間が続いた。Fは誰もわからないので捨て気味に。Hをこるとんが考えて、Gを僕とrisujirohで検討する。凸包から始めて、何らかの探索をするという方針まではrisujirohが立てていた。risujirohが幾何テンプレを書いている間に、詳細な方針を考える。凸包のアルゴリズムが動いていそうなことを確認した後、再度方針を立て直す。ここはかなり苦悶したが、「上位K番以下は持たなくてよい」ことに気づき、bfsを提案する。よく考えると「探索の深さはKまででよさそう」ということもわかり、計算量解析は怪しかったがrisujirohが不可能実装ではないと言うので実装に入ってもらう。僕は隣で見ていた。実装方針に悩んでいたので、priority_queueを用いた方針を提案。受理されるが比較関数を渡すのがうまくいかず(僕はそういうときは構造体を書いているのでそうじゃないときにどうするのかわからなかった、だめ)、risujirohがsetならわかるというのでsetでやることに(なにこれ)(重複除去を勝手にやってくれるので結果的にはよかった)。この辺からHを諦めたこるとんも加わり、3人体制で実装に入る。bfsパートはbfsだったのだが、探索を打ち切る実装が思いつかなかった。ここでこるとんが探索の深さを明示的に管理することを思いつき、書ききる。サンプルを試すと-1の処理を忘れていたので追加し、再度サンプルを試すと合う。やるしかないのでテストをダウンロードして実行すると爆速で終わり投げるとテスト1が通る。「これ通ったらやばい、マジ…?」とか言いながら興奮気味でテスト2を投げる。通る。さすがに嬉しくて3人で肩を組んだ。

残り10分とかだったので終わりムード。順位表を見たら6位(上に参加資格なしのチームがいた)でよかったのではという話をしつつ反省会した。

 

今日はチームとしてとても良く動けたと思う。CDEは誰かができないというものを他の人が1問ずつしっかり通した。Gは誰かが欠けていたら通らなかったと思う。これなぜか全くバグらなくて1発で通ったのかなりすごいと思う。Gは2チームしか通っておらず、FAもとることができた。2チームしか通ってないので作戦ミスにも見えるが、あの状況でGに振ったのはチームとしては正解の選択肢を取れたと思う。一人ひとりが力を発揮できるセットで、チーム戦ならではの瞬間が多くあり、充実した3時間だった。

個人としてはABを比較的すんなり通せた(Bはもっと早く書けたはずだが)。Cをしっかり通せたのもよかった。Gの解法にも貢献できて、自分としては十分仕事ができたかなと思う。あと2週間で少しでもできることを増やしたい。

 

結果的な順位はよかったが、模擬国内予選に参加していなかったり、人が揃っていない有力チームが複数あるので全く油断できない。でも、このタイミングで良い感触を得ることができて本当によかった。本番はせめて、「これでだめなら諦めがつく」くらいのパフォーマンスを出したい。

 

okimochi練(6/29)

3時間2セット。

 

RUPC2017Day3

こるとんがAを通す。僕がBをやろうとするがうーんとなり、DがいつものDijkstraらしいのでBをこるとんに渡してDを受け取る。risujirohがCを通したあとDを僕が書く。問題を誤読していて(え…)焦るがまあ通る。その後Eが遅延セグ木を使いたいらしいので、遅延セグ木を写経するが、僕がiと1を見間違えていたので大変なことになった(え…)。Eが通りFをこるとんやるが、木のハッシュに問題があったらしくそのまま終了。Gもやろうとしていたが、短時間でやるには場合分けが厳しかった。 

 

国内予選2014

Aをこるとんが通す。B余裕じゃんと僕がやるが何故かバグる。こるとんに見てもらって通る。Cが通る。この時点でこるとんがDもEもわかったらしいので実装の早さも考慮して丸投げして通る。その間に他の2人でFとGを見るが、まあわからない。DEが終わったこるとんがvalidationさえできればあとは貪欲とわかり、その条件を考える。誰かが必要条件を見つけ、十分性は怪しいけどこれしかないので実装が始まる。TLEが解消されなかったが、AOJからテストを引っ張ってきて手元実行してdiffを取ったら大丈夫だったのでACと判断。Gはいろいろ案が出たが結局だめだった。

Fが通せたのが偉く、成績としては4位相当だった。Fは通すだけならそんなに難しくないと言われさすがだなあと思った。ところで1位はあのチームで、ぶっちぎりの1位だった。こわい。

 

個人の反省としてさすがに自分の実装でバグらせすぎ…。本当にまともにかけるのがDijkstraしかなくないですか?チームとしては全体的に今後のムーヴの判断が早く適切になっていると思った。

AGC023-D:Go Home

こういう問題を解いていると競プロ楽しいなと思う(やはりパズルが好きなのでは?)。

問題

D - Go Home

解法

 すべてのマンションが地点Sから見て同じ方向にあるときは自明なので、そうでない場合を考える。
 初期状態から考えるとつらい気持ちになるので、終了状態から近い方から考えてみる。Sから見て最も座標の小さい側にあるマンション1の住人と、最も大きい側にあるマンションNの住人だけが残った状態のバスは、今までのバスの軌跡によらずP_1P_Nの大小だけでバスの動きが決まる。仮にP_1\gt P_Nだとすると、マンションNの住人はマンション1の住人がバスを降りるまで、つまり一番最後までバス取り残されることになる(かわいそう)。そうなると、マンションNの住人の目標は、マンション1の住人にできるだけ早くバスを降りてもらうになるので、彼らの目標はマンション1の住人と同じだと考えてよい。するとマンションNのことはもう考えなくてよいから、マンション1からN-1までだと思って同様に考えればよい。このことを最初に述べた自明な形になるまで繰り返すことで、逆順でバスがどのように動くかを決めることができるので、この問題が解ける。時間計算量はO(N)になる。

実装

Submission #6134992 - AtCoder Grand Contest 023
実装が一番難しかった。実装で明示的にバスの動きを追わなくてもできそうだけど、そうしてしまった方が実装が楽だった。

diverta 2019 Programming Contest 2-D:Squirrel Merchant

方針立ってから時間かけ過ぎた...。

解法

 まず1つの金属について考える。例えばg_A \lt g_Bなら、Aでどんぐりを金にして、Bで金をどんぐりにするという行為以外ありえない。このように不等号の向きを見れば、ある程度取るべき行動が確定する。金属の種類の違いを無視すれば、3つの不等号の向きの組み合わせは4通りなので、これで場合分けをし、全探索をすることを考えよう。g,s,bの3種類の金属をまとめてmを書くことにする。

  1. 3種類すべてm_A\leq m_Bのとき、取引所Aで金をi個、銀をj個買うと決めると、銅を買う個数も勝手に決まる。よって、i,jについて全探索してO(N^2)となる。
  2. 3種類すべてm_A\geq m_Bのとき、1の場合と同様にすればよい。
  3. m_A \leq m_Bとなる金属が2種類のとき、取引所Aでその2種類の金属をいくつか買い、取引所Bでどんぐりにした後、m_A \geq m_Bである金属を買えるだけ買い、取引所Aでその金属をすべてどんぐりにするという行動を考えればよい。したがって、最初に取引所Aでm_A \leq m_Bとなる2種類の金属をそれぞれいくつ買うかを決めることでO(N^2)の全探索が可能となる。
  4. m_A \leq m_Bとなる金属が1種類のとき、取引所Aでその金属を買えるだけ買い、取引所Bでその金属をどんぐりにしてから、m_A \geq m_Bである2種類の金属をうまく買って、取引所Aですべてどんぐりにするという行動を考えればよい。全探索すべきは、取引所Bでの金属の買い方だが、これは片方を何個買うかを決めればよいので、取引所Bについた時点でのドングリの個数がネックになる。これはO(N\max(ga,sa,ba))であり、全探索して間に合う。

これで問題を解くことができた。

実装

Submission #5936228 - diverta 2019 Programming Contest 2
算数パートが注意が必要で6WA...。この実装は「ある金属を買うのに使うどんぐりの数」をi,jとしているので参考にする場合は注意を...。

ナップサックdpでできるらしい。類題を解いたことがあったのに見えなくて悲しかった。

CODEFESTIVAL2018 Final G:Chicks and Cages

解法

 dpっぽい雰囲気はあるが、何の整理もなしにはうまくいかない。まず、ある鳥かごに振り分けられたひよこの集合をXとする。この鳥かごで発生するストレスの値は|X|\sum_{i \in X} A_iである。つまりストレスの値の総和は、ひよこの大きさに、そのひよこが入っている鳥かごのひよこの数を係数としてかけた値の総和ということになる。これがわかると、小さいひよこにできるだけ大きい係数を、大きいひよこにはできるだけ小さい係数をかけたくなる。実際、2つのある鳥かごに振り分けられたひよこの集合をX,Yとし、|X| \lt |Y|とする。このとき、i\in X,j\in YかつA_i \gt A_jがなりたつ(i,j)の組があるとき、ひよこiとひよこjを入れかえることで、ストレスの総和を小さくできる。このことは、A_iの小さい順にひよこを鳥かごに振り分けることで得られる最適解が存在することを意味する。
 ここまでくると、A_iを昇順にsortして、dp_{i,j}:i番目のひよこをj個の鳥かごを用いて振り分けたときの最小値 というdpができそうという気分になる。更新式は、A_iの累積和をS_iとして

  • dp_{i,j} = \min(dp_{i-k,j-1}+k(S_i-S_{i-k}))  (1\leq k \leq i)

である。しかしこれではO(MN^2)となり間に合わない。この遷移を高速化できないだろうか?
 「大きいひよこにはできるだけ小さい係数をかけたい」という気持ちを思い出そう。この気持ちに立ち返ると、iが大きくなるにしたがって、調べるべきkは小さくなっていくのではないか?という予想が立つ。実際、sortした後であれば、j番目の鳥かごのに入ってるひよこの数をk_jとすると、最適解においてはk_j \geq k_{j+1}が成り立たなければならない。これを勘案すると、dp_{i,j}を更新する際には、kの値としてi/jまで考えれば十分であることがわかる(k_1=k_2=\cdots=k_jみたいな状況がk_jが最大となるときに考えられる振り分け方だから)。従って更新式は

  • dp_{i,j} = \min(dp_{i-k,j-1}+k(S_i-S_{i-k})  (1\leq k \leq i/j)

となる。このときの計算量は、計算量に調和級数が現れる形になるのでO(MN\log N)であり、十分間に合う。

実装

Submission #5713037 - CODE FESTIVAL 2018 Final
dpそのものは基本的だと思う。

ABC128-F:Frog Jump

コンテスト中に解き切りたかったけど、細かいところも少し要求されるので厳しかったかな...。

問題

F - Frog Jump

解法

蓮以外の点に行かないようにしないといけないので、まず0 \lt B \lt A\leq N-1という条件が得られる。この下で、A,Bを決めたときの動きを観察すると、以下のように書ける。
0,A,A-B,2A-B,2A-2B,\cdots, (k+1)A-kB=N-1
ここで、C=A-Bとおけば、
0,A,C,A+C,2C \cdots A+kC = N-1
と書ける。つまり、k,Cさえ決めれば動きが定まり、kC\lt N-1より、あり得る(k,C)の組を全部試しても、各組をO(1)で調べることができれば全体でO(N\log{N})で間に合う(計算量が調和級数になるやつ)。実際、Cを固定してkを1増やすと、新たにs_{N-1-kC},s_{kC}に訪れることができるようになるから、各Cに対してkの小さい順に探索を進めればよい。
問題は、一度訪れた蓮の上には再度訪れることができないという条件だ。再度訪れることがあり得る(k,C)については探索してはいけない。このようなことが起こる(k,C)の条件を考えよう。動き方から、このようなことがあるとしたら、非負整数の組(k_1,k_2)が存在して、k_1C = A+Ck_2という等式が成り立つはずである。これはk_1=k_2+\frac{A}{C}と変形できるので、まずACで割り切れると危険だということがわかる。さらに、この等式を満たし、かつk_1が最小になるような(k_1,k_2)の組は当然(\frac{A}{C},0)である。このことより、\frac{A}{C} \gt kであれば、ACで割り切れても、蓮を再度訪れるということが起こる前にN-1の蓮にたどりついてゲームが終了する。したがって、条件を満たす(k,C)の組の条件は以下の12が同時に成り立つことである。

  1. A(=N-1-kC)Cで割り切れない。または、ACで割り切れるが、\frac{A}{C} \gt k
  2. 0 \lt B \lt A\leq N-1

実装

Submission #5662288 - AtCoder Beginner Contest 128

実装的には「条件が満たされないときに答えを更新しない」という書き方をした方が楽。

実装はたったこれだけ....。考察力が試される良問。

Educational Codeforces 65-E:Range Deleting

これが解けて紫になった。

解法

 (A_i,i)をsortした列を考える。この列を眺めていると、区間(l,r)を消去できることの必要条件は

  • 上で述べた列について、A_iの値がl未満のところまでは昇順である」かつ「A_irより大きいところからは昇順である」

が成り立つことである。M(a)a=A_iであるiの最大値、m(a)a=A_iであるiの最小値とする。すると、aa+1が昇順に並ぶかどうかは、M(a)\lt m(a+1)かどうかを見ればよく、容易に判定できる。
 このことをもとに、lを固定したときに条件を満たすrがいくつあるかを数えよう。例えばl=1のとき、条件を満たすrの値の最小値はm(r-1)\gt M(r)かつM(1)\lt m(r+1)を満たす最大のrである。m(1)\lt M(2)だとしてl=2のとき、条件を満たすrの値の最小値は、l=1のとき以上であるか、存在しないかのどちらかである。これは、M(1)\lt M(2)であることから容易にわかる。このようにして、lの値を小さい順に調べ、その都度あり得るrの値の最小値を尺取り法の要領で更新することで、組(l,r)の個数を数えることができる。計算量はO(N+X)であり、十分高速である。

実装

Submission #54221712 - Codeforces


問題を見てこれは解けないといけなさそうだと思ったので、解けて嬉しかった。こどふぉのレートが上がるのは自力がついてきた実感があって良い。