ferinの競プロ帳

競プロについてのメモ

JAG夏合宿2017参加記

競技プログラミング

初日

歩いていたらICPCの話をしている人がいておーとか思いながらオリセンに向かう。早く着いてしまって暇だったたのでtwitterリストを作りながらチームメンバーを待つ。周りの人々がみんなレッドコーダーに見えてこわい。 f:id:ferin_tech:20170925011107j:plain

チームメンバーと合流した。2人しか来ていなかったので一人の人とmergeしてもらいYang33さんと出ることに。

手分けしてABCを読むとどれもそこまで自明な問題ではない。Bが二部グラフでは？（嘘）とかAでうまく文字を使っていけば算数すれば解けそうといった話をしていると後ろの問題が解かれている。Aでうまく文字を使っていく方法について相談していると気づいたらdivさんがJを通していた。Dが解かれていたので読んでいると気づいたらdivさんがKを通していた。Dは算数をすればいいので実装すると通る。Aの実装に交代してEを読む。BNFがあるのでそのまま構文解析かと思ったがvectorとexprをうまくまとめて扱わないとだめでどうしようとか考えているとAとHが通っている。チームメンバーにEを相談するとまとめて扱える構造体か何かがあればよさそうと言われ実装してくれた。その間にsolvedが多かったFの"極小"文字列を読む。sum(T_i)が105なのを使うんだろうなあとか検索っていうとtrieとかSAとかかなあとか思っているとEが通っている。この時点で残り1時間くらい。文字種jがi番目の次に出てくる位置を覚えておけばO(T_iの長さ)でできるじゃん！とか話しているがよくよく考えると開始位置の候補が多すぎる…尺取りみたいに開始位置、終了位置をずらすとか3分探索とかSAとか色々考えるが不可能でコンテスト終了。

チームでは6完だか個人では1完（ア
このコンテスト中にfor文すら書いていない…コンテスト終了後に問題文を読み直しているととんでもない事実が発覚する。最小の部分文字列を探す問題を解こうしていたが"極小"の文字列を探す問題だった…誤読に気づくと前後から貪欲すればいいのではい。3人で誤読していて悲しいね。

TLの人々がボドゲをしているのを観測したので遊びに行く。TLでよく見るプロ各位が大集合していてボドゲ会が開かれようとしていた。競プロerは地頭力が強いのでみんな強くてすごかった。Coupとコードネームをやった。Coupは最初に動きたくないから早く10枚にはしたくないけどコインを集めないとコインレースに負けるジレンマのバランスのとり方とかブラフとか難しいなーといった感じだった。 f:id:ferin_tech:20170925011114j:plain

2日目

翌日、無事起床AC
ボドゲをした人々と朝ご飯に行く。ご飯とパンが別の場所にあるため貪欲に取ると大量に炭水化物を食べることになる罠を無事切り抜け朝飯を食べる。貪欲に取っていったらナップザック問題の最適化に失敗してお腹がMLEしている人々がいた。

コンテスト前にチームメンバーを募集しているとゆらふなさんに組んでもらえることに。マクロや開発環境とかの確認をしつつコンテストの開始を待つ。

記憶が曖昧なのでちょっと違うかも。
前の方は難しいらしいので後ろから手分けして読む。Jがぱっと見自明だが制約を見ると何もわからない。Lが読解が少し不安だけどそこまで難しい問題ではなさそうといった感じ。順位表を見るとBとGが解かれていてチームメンバーが読んでいたので残りの問題を読んでみることにした。Iを読んでみるとコンビネーションの和で整数を表せればいいらしい。上の桁(?)のから取れるぎりぎりの大きい数を貪欲に取っていくみたいな気分になったが証明ができない。Bの実装に入っていたがWAが出ていてつらそうなのでいっしょにデバッグをしているとゆらふなさんがGをAC。Lの読解がおそらく最初のであっていて解ける問題ということを確認する。順位表を見るとBH,次いでIJが解かれているといった感じなのでHを読む。borderingって何？隣の方がenergy低いの違和感がすごいし端に移動するのか？といったことを考えたりしているととゆらふなさんがLをAC。borderingについて相談するとやっぱり隣では？と言われる。問題として隣と一個飛ばしは確かに自然ではあるのでその方向で考察することに。この時点でBがかなりハマっていてつらい感じ。Bのデバッグをチームメンバーがしてくれている間にHの考察を進めることに。SとFが端にあるかどうかで場合分けしていく。両方とも端にない場合まずFがない方に移動をはじめないとだめで～といったことを考えていると、num/3+num%3+(端にない数), num = f-s-(端にない数)といった式が出て来る。これを一回実装して出すとWAになる。Bの実装に一旦交代し考え直す。制約をよく読むとs<fとは限らない。BがACされたのでこれを直して提出するとAC。この時点で4完で残り1時間半くらい。Dが似たような問題を見たことがあったのでクエリを逆読みすると各頂点一回しか見ないのでみたいな話をするが距離d以下の点を列挙するパートが難しい。Fも少し考えるが順位表通りやはりI,Jをやろうという話に。蟻本の数論のあたりを読むとそれっぽいことが書かれているがやはりmodが素数でないのでだめそう。残り30分くらいで最初に考えていたIの貪欲を実装してみることにするが、二分探索をバグらせたりオーバーフローの扱いを間違えたりいろいろ実装を手間取ってるうちにコンテスト終了。

大体ゆらふなさんに助けてもらっていて申し訳なさがある。ICPCの弊チームは個人が勝手に練習が基本でチーム練習をあまりしていないのでもうちょっとチーム戦に慣れたい。

divさんとチームaotenjouの皆さんと夕飯を食べる。初心者の育成は大変とかするめが少なさ過ぎてレートが上げられないといった話をする。1年生に競プロを布教するのはやっぱりどこも大変なんだなあといった気持ちになる。

この日はこどふぇすの予選があったので色々準備しつつゆっくりする。ネットを求めて談話スペースに行くとプロ各位がすでにいらっしゃったのでお話したりしていた。コンテストではAで用意したcodefestival2017を使わなくて残念とかBで2倍を忘れて10分掛けたりDは全く違う方針で1時間半突っ走っていたりした。thanksボーダーには遠かったが3完それなりの速さでレートがもらえたのでよかった。コンテスト終了後はいつものtwitterのみたいなやりとりがリアルで展開されていておもしろかった。

3日目

日本時間を理解しているので起床AC。朝ご飯を食べてシーツと鍵を提出する。チームメンバーを1人募集しているとravenさんに組んでもらえることになる。今日は難易度順に並んでるのでは？ということで前から読んでいこうといったことを確認しつつ準備する。

ABCを分担して読む。ぼくはBを読むことになった。やること自体は簡単そうだけどバグらせそうなやつだなあと思い気をつけながら考察しているとdivさんがAをAC。Bを実装しはじめるが途中で考察漏れに気づく。Cが考察が終わっているみたいなので実装を交代して考察をし直すことにする。冷静に考え直すと別に難しいことはない。Cの実装を待ちつつDの考察に加わることにする。Nの制約からまず明らかにbitDP。残っている人が与えられたときに最適な行動はレートが1位か否かで場合分けすればできそうといった話をする。しかし遷移が2^nかかりそうなので合計O(4^n)に思えて計算量がオーバーする。Cが詰まっていたので交代してBを提出して通してCに交代する。Dの計算量が落とせる気がしないのでEの考察をしてみる。+だけなら自明。*をうまくつぶして+に置き換えるみたいなことを考えるがどうやればいいんだろうなーといった感じになる。順位表を見るとDEFが解かれているのでFも読むことにする。手元で色々実験しているとある頂点がcurrentに含まれると次のステップで隣接した点がcurrentに含まれてさらに次のステップでまたcurrentに含まれることに気づく。一回currentに含まれると偶奇が一致するステップでは必ず含まれることが分かる。なので最初に偶数ステップ目と奇数ステップ目でcurrentに含まれるタイミングを求めれば答えがわかりそう。ただ頂点を2倍取ってBFSすればいいだけだが謎の勘違いをしていて実装で詰まっていたら教えてもらって通せた。Fの実装をしている間にEの考察を進めてもらっていて先に×を前計算してから+を計算すればよさそうといった感じになっていた。ただ実装がめちゃくちゃ重そう。Eを詰めつつDの計算量の落とし方について色々考えたりする。Eが実装は重いが一応計算量的には問題なさそうといった感じになりdivさんに実装してもらう。Dの計算量が一向に落とせないのでGを読む。N,M,Kの制約が非常に小さいので色々できそう。ravenさんの考察に口をはさみ色々考察をすすめる。普段なかなか見ないような計算量が出てくるが確かにできないことはなさそう。が、実装が重すぎてできる気がしない。divさんのEがサンプル全て通ったらしいのでそっちを考えるのに集中する。提出するとWA。long long intを一箇所直して提出するとWAが減る。バグを消せれば通せそうということで3人でバグを探すことに。色々試してみるが通らなさそうなケースがない…そうこうしているうちにコンテスト時間が終了。

終了後にEのハックケースが見つかって直したらACに。Gの想定解法を読むと方針は合っていたらしい。DはO(4^n)ではなくO(3^n)のbitDPができるので計算量が問題ない。個人的にはFを思いつけたのはよかった。BもFも実装をつまらせたのは反省。

プロ各位とちょっとお話をして帰路につく。

コミュ障でもTLでよく見かける方とは話せたのでやはりtwitterは大事。コンテスト+ボードゲームで楽しい3日間だった。 参加記を書くまでがJAG合宿らしいのでJAG合宿を終えました。お疲れ様です。