CPSCO2019参加記(２日目) - Tallfallの日記

昨日(一週間前のこと)の
CPSCO2019参加記(1日目) - Tallfallの日記
の続きです。

2日目

この日は本当に眠かった。例え4時に終わるコンテストだとしても4時に寝れる訳ないんですよね。

2日目位になると人見知りの僕でも色んな人と話ができました、同チームになった人と運営と同大以外だとくるさんとかnadareさんとかしいさんとか（他にもたくさんですが割愛）ですね、なんだかんだ緑～青の人と話すことが多かったです、次あったらそうじゃない人とも色々話したいですね。

話していて少し意外だったのは皆さんAtCoder以外はそこまで出ていないということでした、まぁ時間が日本向きではないですものね。Codeforcesの過去問バチャとか立てたら人集まるでしょうかね、需要あるなら自分のペースメーカーにもなるしやりたいですね。

さて、はにーまさんの買ってきたお菓子を食べていたら(チョイスが良かった)チーム分け後すぐにSession2が始まりました。人来るの結構待ってんのにあの速さで割り振りできるの凄い。

この日は記憶が死んでるのでところどころ変なこと書いてるかもしれません、すいません。

Session2

writerはゴジラさんとやむなくさん、ゴジラさんは会場で二人しかいない元々お会いしたことのある人でした（学部で結構有名でしたし）。やむなくさんはTwitterで見たことあるくらいでしたが強そうなオーラが出てました笑。

チームはpmh(それぞれの頭文字)、調べたら既往歴って意味らしいです。

問題文
CPSCO2019 Session2

A - Scholarship Repayment
奨学金を返す問題、実際のシステムと同じらしい、面白い。実際にN-1月でどれだけ払ったかを求めて、Mから引いたのが答えです。
はにーまさんがAC

提出:
Submission #5304809 - CPSCO2019 Session2

B - Telephone Q
知ってる人少なそう。「こんばんはゴジラです」、普通に災害では？
＋かーか*が書かれたパネルを開けていき、書かれた数字だけ対応する操作をする問題。
$(a \geq 0), b\geq 1, c\geq1 \Rightarrow (a+b)c \geq ac + b$
なので+0は無いも同然だから+全部取って*全部取るのが最適、コーナーケース(?)の*0がサンプルにおいてあって優しさを感じました。
はにーまさんがAC

提出:
Submission #5304825 - CPSCO2019 Session2

C - Delicious Burgers
美味しいハンバーガーを作る問題、各文字列の隙間における括弧の深さを求める問題に帰着できます。そういう時は(を+1,、)を-1に置くといいって誰かが言ってた。担当僕でしたが最初誤読してて閉じた括弧の中にしか|を置けないと思って2WA、死ぬほど焦りました。問題文はちゃんと読もう!

提出:
Submission #5304857 - CPSCO2019 Session2

D - Two Piles
これ好き、ゲームの問題。二つの山から合計が片方の山にあるコインの数になるようにとっていき、取れなくなったら負け
なんか見た感じ偶奇っぽいので(和とか差をとって変化しない状態量になりやすい)少し考えると奇数奇数はめっちゃ弱そうみたいなことやただ0,0の時は負けだからうーん？ってなってました。1,Xの状態を考えれば一発だったっぽいです。
pelnoさんが通してくれました。

提出:
Submission #5304877 - CPSCO2019 Session2

E - Mogu Mogu Gummi
制約が $O(n^{2})$ で間に合い、かつ木の問題で部分木の情報をもっておけば解けそうなので二乗の木dpかなと思いました。ただ実装したことなかったのでaisingの奴ちゃんと復習しておくべきだったと結構後悔しつつ(その時まだレート1000とかだしまだ早いとか考えた気がする、駄目駄目でした)実装を進めることにしましたが残念ながら時間切れでした、流石に解くべき問題だったかなぁとは思います。DとEでそんな崖にはならないはずだった難易度差なんじゃないすかね。

提出:
Submission #5304962 - CPSCO2019 Session2

F - Treasure Collector
コンテスト中は見てません。
任意の列か行についてロボットがただ１つ存在する正方形のグリッドをなんやかんやする問題。
解説を聞いてから解き始めたので、燃やす埋めるだということはわかっていました。ただコインをとる方法が二個ちょうどだったり制約が小さかったり、複雑にそれぞれのコインの取り方の条件が絡んでいるのでフロー使いそうだなとは思ってた気がします。
まぁ実装は一回しか(むる)やったこと無かったんでコンテスト中に通すのは無理でしたね。
(コイン)Aが縦(向きでロボットに取られる)ならBも縦 $\iff$ Bが横ならAも横
が成り立つのが面白いですね。少し込み入った場合分けの時はelse使わない方がミスらないんじゃないかということを学びました。

提出:
Submission #5333709 - CPSCO2019 Session2

G - MSTX
これ面白い、辺の重みが変数になっているグラフのMSTをクエリ毎に答える問題。コンテストの序盤でちらっと見たんですけど、結構悩んでもしかしたらクエリ先読みして少しずつ頂点をマージしていくのかな、とか最初から変数辺以外をまとめて尺とりかなーとか適当なことを考えました。自力ACしてたら気持ちよさそうですね。
x=0でも使う辺は絶対使うので最初からつなげておいた状況で定数辺(この場合c=0の意)のみでクラスカル法を行います。u, vを結ぶコストwの辺に着目するとこの辺で初めてuとvが連結になった時、この辺が予め使われていなかったことを考えると、
この辺が実際に使われる $\iff x\geq w$
ということが分かります。これらの情報を使うと二分探索でクエリに $O(log{N})$ で答えられます。

提出:
Submission #5380237 - CPSCO2019 Session2

個人的にはめちゃくちゃ勉強になったセットでした。チーム戦としては2WA生やして300しか通してないので悲しくなりました。

さて、解説の後すぐSession3が始まりました、もう死ぬほど眠かったです。

Session3

Nキチさんとぺいさんとでした、水緑緑でいい感じでした。Nキチさんとは初日にそこそこ雑談してました。この回については記憶が半分くらい無く、本当に他の二人には申し訳無い限りです。

writerはけんちょんさんでした
やっぱり頭文字には気づかなかったです

A - ASOKO
文字列のAとOを入れ換える問題、言語によって色々違うらしくて面白いですね、pythonだと文字列はイミュータブルなので少し面倒ですね。
ぺいさんが通してくれました、流石に速かったです。
提出:
Submission #5380680 - CPSCO2019 Session3

B - Balloons
手持ちの風船からM個選ぶ、この時色の種類を最小化したい！という問題。
ソートして大きい方から選べば良さそう、複数のクエリに答えるわけではないのでそこから累積和して二分探索とかはやらなくて良さそう。
ぺいさんが通してくれました。

提出:
Submission #5380727 - CPSCO2019 Session3

C - Camp Reception
一次元の区間が挙げられてその連結成分の個数を数える問題。sとtの大きさが $O(n)$ しても間に合うのでテーブルを作って[s, t]を塗りつぶして塗られてないところで分ければ良さそうです、imosで世界を変えられるので世界を変えるとAC出来る(解説見てないと意味不明ですね)
もしs,tがもっと大きいならSession1のFみたいにしてキューが空になる度答えをインクリメントすれば良さそうです(提出はこっちです)。
NキチさんなんとFA!つよい

提出:(かなりギリギリでびっくり,whileが遅いのかな？)
Submission #5380851 - CPSCO2019 Session3

D - Decode RGB Sequence
はい戦犯は僕です。
かなり難しそうな第一印象で、必要条件を列挙するくらいしか思い付かなかったです(RGBと塗られたところから左右に見ていくみたいな実装も考えたけどあのときの頭じゃ実装無理なので...）
で、普段はこういうことしないんですけどプレッシャー等で取り敢えず投げてみると4WAでそのあと少し変えて3WAだったのでその事を伝えてチームメイトに任せました。十分性を証明できぬまま出したので結構後悔と反省してます(証明が間違っていた時との心理的な差がよく分からない。)
割と十分性は非自明だと思うんですけどどうやったらコンテスト中に素早く分かるんですかね...
そのあと条件を厳しくしてぺいさんが通してくれました。（本当に感謝）

提出:
Submission #5381069 - CPSCO2019 Session3

E - Enumerate Xor Sum
戦犯2。
タイトルが凄い怖かったです、400詰まって問題眺めてたら取り敢えず桁毎に見れて、その時の1の個数だけ見れば良いのと遷移が簡単だと言うことには気づきました。ただその実装ができる気がしないのと(この時半分夢の中でした)pythonで通るか微妙な計算量(実際一回TLEした、流石にこちらが主理由)だったこともあり、C++でこんな奴書いて欲しいみたいな事になったんですけど僕の説明が下手すぎました...本当に申し訳ないです。
コーラをがぶ飲みして少し目が覚めたのでpypyで通しましたが遅かったですね。
(本当にすいませんでした)

提出:
Submission #5381097 - CPSCO2019 Session3

F - Flexible Permutation
戦犯3。
順列Pの元の位置との大小が指定され、それを数え上げる問題。
残り３０分位から見始めました。
位置が変わらないのは(前もって掛けとけば)無視していいことにはすぐ気づけて残りは大きいのと小さいのだったのですが。dpの遷移が見えず(変えたくないのは絶対位置なのを考えると出さないといけない発想な気はする)挙げ句の果てに
「うーん、何か挿入dpとかでは無さそうだしdpじゃないかもなぁ」
とか言ってたのでチームの足引っ張りまくりでした。とてもとても反省してます。
次例えば順列Pの $P_i \geq P_{i+1}$ となるiの数が与えられる数え上げとかの問題が出たときは流石に詰まりたくないですね。
貰うdpで考えると楽そう。

提出:
Submission #5383848 - CPSCO2019 Session3

G - Grand Election
コンテスト中は見ていません
見事に嘘解法に引っかかりました。 $O(X\log X)$ 解まではあってたんですけどそこからの高速化で嘘を踏んじゃいました...
pythonには有理数型があるんでそれをheapqに乗せて(乗るの知らなかった)実装した所当然TLEしたので、今度はfloatで実装すると誤差で2WA出しちゃいました。decimal使おうかなぁとか結構考えて(多分どうせ遅い)結局 $lcm(lcm(1,2,3...100), \sum{A})$ 　を分母にした所何とか通りました。疲れました。