RUPC2018不参加記

RUPC2018に不参加したので問題の感想を書こうと思います．

不参加に至った経緯

btkプロとかに参加するように勧められてわりかし行く気でいたんだけど，就活を全く進めていないので断念．
3月下旬というのは就活が忙しくなる時期だそうです．

Day 1

本当は問題を見るだけにするつもりだったのに...

A

単純に二重ループ回すだけだけど，よく見ると出力が index じゃない罠

B

3日間で1番問題文が難しいと思った問題． g(i)じゃなくて g(a_i)を出力するんだ...

C

mapとかmultisetとかで持ってもいけるんだろうけど，同じかどうかの判定の時間がわからない．
素直に前から見た時と後ろから見たときの差分を持ちながら合致してない種類を数える．

AOJの仕様上(?)余計な空白があると受け入れられないらしくめっちゃWA数を稼げた

D

貪欲でできるのかな～～と思うけど無理っぽいから区間DPかな～～と考えて無理っぽいからよくみるとただのDP． O(n^3).

E

問題文を素直に読むと(いたずらされる前は)有向グラフの問題だし有向グラフでの最短路を求めるもんだろうと思う
そう思うと「 a_iから b_i」とかも有向辺を意味するように解釈できちゃうんだなぁ．有向でも解けるんですかこれ？
無向だと思うことにしてもなんか難しくてよくわからない割にみんな通してるから，とりあえず全部辺貼ってダイクストラしたら通った．
解説読んだらそれはそうという気持ち．

F

桁DPにするか包除でやるか悩んで思考停止桁DPへ．
最初[515]の状態を区別しなきゃいけないことに気づかずサンプルが合わなかったけど，ちゃんとオートマトン書いたら解決．最初から書けばよかった．

G

i階と i+1階がつながったときに頂点 iと頂点 i+1をつなげるみたいなUFを書きたくなる．
何日目で i階と i+1階がつながるかを調べるためには愚直じゃだめで，setのupper_boundとかでいけるっぽい．
でも面倒なので区間更新・点取得のセグ木を貼る．
（日数 iを後ろから見て区間 [s,t)を E_iに更新すれば最後に残った数値が初めてつながった日．）
座圧とかいろいろあって若干面倒だけど一発で通ってラッキー

Day 2

就活の事情で1時間半経過したところから参加

A

ちゃんと問題文を読んだので引っかかりません

B

最上位bitの位置を出力したくなるけど Nに1を足しておくと楽

C

貪欲アンド貪欲みたいな感じ

D

問題文からして難しそうですが．結局 |S|分木みたいな感じになるから答えはせいぜい \log_2 |S|で小さい．
答えを決め打ちしてチェックすればOK．運が悪いと比較対象の文字列がめっちゃ長くなるっぽくてMLEする(した)．

E

これ難しすぎでしょ．最初 O(1)でできるんじゃね?とか思ってたけど自明な例を考えると自明に不可能だった．
結局コンテスト中には解けず，あとで考えたら(街頭のID＆そこに使うコスト)をキーにダイクストラやんけ．

F

長さ3の順列は6通りだし，最大6個つなげれば絶対可能．「 i個めをつなげたときの順列」の順列を考えて O(6!)で解ける．

G

消せる条件のお気持ちが全くわからんけど，とりあえずグラフを書いてみる．一般マッチングができればこの問題の性質とか無視して解けるなぁと思ったから一般マッチングのソースを貼ると通る．(まだ解説読んでないしもうちょい考えたい)

H

そこから右に何個0が連続してるかをあらかじめ数えておく．するとimos法とかで(先頭0を除いたあとの) i桁の数がいくつあるかを求められる→桁数確定．
あとはその桁数の数を全部vectorに突っ込んでソートすればいいやとか思ったけどもしかしたらTLヤバそうなのでSAを使う．
バグらずかけて最高

I

n=14だしどうせ O(3^n)でしょ．とりあえず O(2^n n^4)かけてすべての部分集合に対して最小包含円を求めておいていつもの部分集合DP．
途中で偉くバグってしまい厳しくなったわけですが，その原因はベクトル v,wが平行な条件を v \times w < EPS にしていたせいでした．しょうもない．

J

コンテスト中には区間更新じゃなくて点更新だと勘違いして書き始めたわけですが，途中で気づいて撤退．遅延セグ木にうまく個数情報乗せられなかったからあきらめて平方分割でやる．平方分割意外と早くて余裕で通るし重宝しそう．

残り

まだ解けない

Day 3

起床即参加

A

A問題から難しい．初めて矛盾するクエリ番号を答えるものとばかり．

B

どう考えても難しすぎる．1個も選ばないときの値を0だと思い込んでいたせいでWAが取れず1時間費やしてしまった．悲しい(一人参加だとこういうので心が折れがち)

C

わざわざ'o'マスが用意されるくらいなんだから適当にやっても大丈夫なんだろうと思ったけどなんかWA．
これ近傍マスと(関係ない)枝が隣接する場合を考えていなかった．

D

変なDPっぽい問題．寝起きすぐに一番最初に解いた問題だったからか異様にバグった．24分6WAってなんや

E

どうみてもオイラーツアーだなぁという感じ．この問題を残して残り10分だったから手つかず．考察としてはGとWを1と-1で表すといいとして，区間に一様に-1を掛ける操作を区間総和さえできれば十分．セグ木に書くのは嫌だったから結局こっちも平方分割でごまかした．

F

ICPCつくば以来(個人的に)よく見る最短路DAGの問題．どの枝集合を伸ばそうかと絵をかいて眺めていると最小カットになることに気づくから，最大フローを貼る．綺麗．

G

エイホコラシックを持ち合わせておらず終了．しょうがないからSAを貼って二分探索して対応する区間を全列挙．
最悪ケースだと区間の個数がめっちゃ多くなってしまいMLEしてしまう．時間もないし適当にヤバそうなケースだけ別の方法で対応するようにしたら通っちゃった(?)

まとめ

まだ解説読んでないからちゃんと確認しよう
チーム組まずに一人でやると苦手な問題も解かざるを得ないからある意味練習になる
セグ木抽象化しようかしら
就活が想像以上につまらない