PCK2020 参加記

高校生として出た最後のプログラミングコンテスト。チーム戦楽しかった。

チーム

with sinatori
戦略としては、最初の方は交互に解き、後半はそれぞれが得意なものをやる感じ。地力の差があまりなさそうだったので。
データ構造、グラフは自分で解きにいき、文字列、幾何は相方に投げていた。本選前のバチャの感触としては、8位以内はまあいける、3位以内も狙えそうだと感じた。

予選

あんまり覚えてないので適当に。
11完2ペナで1位。何気にプログラミングコンテストで1位取ったの初めてかもしれない。
2,4,6,8,10,12を担当。この時は完全に偶奇で担当が分かれた。

1~4はスムーズに通ったが、6が正四面体を転がすとかいう謎問題で、詰まった。そのため1~6が通ったのが開始80分後とかで、この時は普通に通過圏外だった。
6はずっとスマートに解こうとしていたが、諦めて紙を破って正四面体を実際に作り、それを見つつ大量の場合分けをして通した。

そこからすぐ7,8をほぼ同時に通し、9,10に取り組む。ここまで2人の提出タイミングがずっと同じだったのが面白かった(別々の問題のはずなのに)。
10は平方分割を考えるとすぐに解け、奇跡的にノーペナでAC。ここまでで2時間半くらい。

9がかなりつらそうだったので応援しつつ、どこかのチームが通していた12を眺める。
雰囲気で重心分解を考えるとうまくいくことが分かるので実装すると、ほぼ詰まることなくAC。
しかもこの間に9のバグが取れていたらしく、9もACして11完に。9と12を同時に提出したので、ほぼ同時にACが帰ってきてテンションが上がり、思わずハイタッチしてしまった。

順位表を見た感じかなり高順位で通過できそうだったのでとても嬉しくなった。11は少し考えたが解けなかった。

10、12がこの速度で解けたのは完全に運だが、ともあれ成功したのでヨシ。

本選

こっちはかなり強烈な記憶になった気がする。
10完∞ペナで7位。悔しい。
2,4,7,8,11,12を担当。

1~3はスムーズに通る。
4の解法が10分考えてやっと分かったので、かなり焦りながら実装した。するとWA。
初期化忘れかと思って直してもWAのままで、序盤で2ペナを作ってしまったことで完全に冷静さを失った。そこで、落ち着くために7に行くことにする(6が幾何だった)。
すると7も全然綺麗な解法が分からず、分かった解法も自力で多倍長整数を実装する必要があり、ライブラリも持っていなかったので焦りまくった。
それでもなんとか適当に実装するとAC。この時点で75分位経っていた。

4が嘘解法だと思ったので、7をやっている最中に相方に4を考えてもらったが、普通に合っているらしい。コードを確認すると最後の処理を書き忘れていただけだった。申し訳なさすぎる。
8の見た目がまともそうだったので考えると、2番目の最短路を求めるだけの問題だったので安心した。普通にAC。この時点で2時間くらい。

その間に相方に投げていた6がバグが取れないらしかったので、9に行ってもらう。
ここで自分が6を見たほうが(精神衛生上)良かった気もするが、焦っていたのでそんなことは考えず、12に特攻する。たぶん2人とも焦っていて良くなかった。

12はJOIのバブルソートを解いていれば貼るだけの問題で、当然貼るのは不正なので頑張ってライブラリを写経する。SuperConで鍛えた写経能力の見せ所(適当)。
2Dセグ木は中々重かったが、1ペナでAC。この時点で2時間半くらい経っていたが、流石にこのあたりになると頭が冷静になってくる。ペナ数ももはや気にしても仕方のない領域に来ていた。
そこで6を眺めると、すぐにバグの原因が分かる。ACして一安心した。

相方が、9が分からなくて10が分かったらしいので、自分が9をやることにする。しかし分からない。AtCoderみたいな問題を出さないでくれ。

残り1時間くらいのタイミングで初めて順位表を見ると、7位くらいだったが、今から10,11を通せば良い位置に行けそうだと踏み、11をやることに。
秘技・制約エスパーを用いるとO(3^n)のDPが使えそうだと分かる。パスごとに最小コストを前計算し、強連結成分にパスを追加しながらDPしていく感じ。
残り30分くらいで実装は終わったが、微妙にバグっていたので気合を入れてデバッグをすると残り10分でバグが分かり、残り7分くらいでAC。流石に脳内物質がドバドバ出た。

隣を見ると相方が10のWAで苦しんでおり、自分は問題すら見ていないのでお祈りをしていたが、流石にヤバそうだったので見る。バグらしきものは修正できたものの、WAのままコンテスト終了。方針ミスだったらしい。幾何本当にむずそう。

感想

チーム戦、戦略とコミュニケーションが大事になってきて中々面白い。ただミスった時はだいぶメンタルが削られる。ICPCに出るかどうかは迷い中。
あと幾何2問は、きついです......。それでも全完するチームがいるの、何??

Dinic法について

理解にかなり手間取った&面白かったのでメモ。

アルゴリズム

やっていることは、「長さが短い順に増加路を使っていく」というだけ。
以下、頂点数 V 、辺数 E 、始点 S 、終点 T のネットワークを考える。

残余グラフを構築しておく。
増加路がなくなるまで、以下を繰り返す。この一回の繰り返しを「1ステップ」とする。

  • BFSで、「容量正の辺のみを使った時の、 S から v までの最短路長」 level_v を求める。
  • 長さ level_T の増加路がなくなるまで、DFSで増加路を選び、フローを増やす。 level_v=level_u+1 なる辺 (u,v) 以外はないものとして扱えば、増加路は全て長さ level_T になる。
  • DFSの際には、「その辺を使ったフローがこれ以上流せない」状態になった辺を記録し、以降の探索では無視するようにする。つまり、その辺を使おうとしたが、 T に辿り着けなかった時と、容量が0になった時、辺は死ぬ。

なお、辺が死んでも1回のステップが終わったら復活する。

計算量(一般のグラフの場合)

最短路の長さは O(V) で、1回で level_T は1以上減るので、全体のステップ数は O(V) 回。

BFSは何の工夫もしていないので、計算量は普通に O(E)

問題はDFSの計算量。このDFSは、Ford-Fulkerson法とは違い、同じ頂点/辺を何度も使うのが厄介。
辺が死ぬタイミングに注目する。
ある辺が死ぬのは、

  • T に到達後、戻ってきた時で、この辺の容量が0になる時(この時、寄り道せずに S まで戻っていく)
  • T に到達できず、戻ってきた時(この辺を使うフローはもう流せないので)

である。
つまり、1回DFSの末端まで到達して戻り始めたら、それに対応して1つ以上の辺が死ぬということが分かる。
1度戻り始めてから次に戻り始めるまでの動く回数は、全部 2V 回以下に収まる。戻るのも進むのも連続して高々 V 回しかできないからである。
これで、辺が死んでから次の辺が死ぬまでの動く回数が O(V) 回であることが言えた。
最初に辺が死ぬまでと最後に辺が死んでからの回数も同様に O(V) 回なので、DFSの計算量は O(VE)

これで、Dinic法の計算量が O(EV^2) であることが分かった。

計算量(二部グラフの最大マッチングを求める場合)

二部グラフの最大マッチングは、新たに頂点 ST を追加して、最大フローが最大マッチングと等しくなるように適当に容量1の辺を張り、フローを流すことで求められる。
この際、グラフの形が特殊なことから、Dinic法が更に高速になる。

まず、1ステップの計算量が O(E) であることが言える。
残余グラフの生きている辺の容量が全て1なので、ある増加路を見つけた時点で、増加路上の辺は全て死ぬ。また、増加路を見つけられなかった時も、戻る時に死ぬ(これは一般グラフの場合と同様)。
よって、辺を2度以上通ることがないので、計算量は O(E)

次に、ステップ数が O(\sqrt{V}) 回であることも言える。
今までで \sqrt{V} ステップが行われたとする。このとき、残余グラフの S-T パスの長さ( =level_T )は \sqrt{V} 以上。
元のグラフの現在のフローを F 、最大フローを F' とすると、残余グラフでは F'-F だけフローが流せるはず。
ここで、残余グラフの容量は全て1で、かつ入次数または出次数のいずれかが1である(場合分けをすると分かる)から、残余グラフに流れるフローは ST を除いて頂点を共有しないことが分かる。
つまり、残りのフローで使われる頂点数は (F'-F) \times \sqrt{V} で下から抑えられる。
(F'-F) \times \sqrt{V} \leq V より、 F'-F \leq \sqrt{V} なので、これ以降のステップ数が \sqrt{V} で抑えられた。
よってステップ数は全体で O( \sqrt{V}) 回。

以上を合わせて、この場合の計算量は、 O(E \sqrt{V})であることが分かった。

いかがでしたか?

非自明な計算量解析って面白いですね!

JOI2020春合宿 参加記

結果から言うと、5位で代表にはなれませんでした。
以下、日記です。(全てその日のうちに書いたもの)

Day0

朝起きると体調がよろしくない。本選の時もそうだったので情報オリンピックに呪われているんじゃないかと思う。
Library Checkerを埋めて「やがて君になる」を読んでいると夜になっている。
早めに寝付けたものの、1時ごろに目が覚めてしまう。ここ数年でこんなことは一度もなかったので不安になった。

Day1

体調はあんまり変わっていないが、とりあえず5時間はやりきれそうなので出発。
控室が同校率80%とかで面白かった。競技会場に入るとさすがに緊張してきたが、今までの5時間バチャの戦略を思い返して心を落ち着けた。

競技

最初に全部ざっと問題文を読んだ。構築-構築-クエリゲーで、嫌な気持ちになった。
1問目の見た目が明らかに簡単枠なので、絶対に解くという気持ちで考える。
一瞬で判定の方法(未証明)が思いついたが、証明していないので当然構築できない。
緊張もあって1時間ほど進展がなかったので、とりあえず判定が正しいか確認した。"-1"を提出した場合と同じケースがACしていたので、正しいと分かる。(最悪)
これが正しいなら絶対にみんな通すはずだと思い、一度トイレに行って頭を切り替えると、普通に構築できることが分かる。
1時間半で満点。2回目の春合宿にして初めて満点が取れて嬉しくなった。

2問目が不可能枠、3問目が難易度11くらいに見えたので、3問目を考えると、小課題3まで分かる。
どうせデータ構造に強い人間が小課題4を解くだろうと思い、小課題4を1時間ほど考えるが、分からない。
後は部分点回収をしただけだが、3問目の小課題3がWAになり、1時間以上原因が分からなくて焦った。
原因は、二分探索のokの初期値を便宜上0にしていたが、実際は0でOKかどうかは確認しないと分からないというミスだった。こういう時は-1にして、判定関数内で場合分けするようにしたい。
2問目は、K=1の時は遅延セグ木で解けるのでそれで2点を得たが、実際はもっと楽にできるらしく煽られた。

結果・反省

結果は100+2+12=124点で4位タイ。やるべきことをやれたかなという感じ。難易度は10-12-12だと思った。
2:30くらいから部分点回収しかしていないのは、単に「とりあえず取っておこう」で書き始めたものが無限にバグったせいで、後半の時間はほぼ考察ができていない。
おそらくインタラクティブが出た時にも同じようになるので、最初の2時間の考察の集中力を上げていきたい。

Day2

よく休んだら体調がかなり良くなって安心した。代わりに花粉がつらくなり、ティッシュを買いに行ったらなかったので、ラムネを買った。(英断)
ラムネを体に詰め込んでから競技開始。

競技

全部読むと、インタラクティブ-グラフ-数え上げ というセットだった。どれもそれなりに点数が見込めるので、時間配分に迷った。
直感で、2->3->1の順に見ていくことにした。(敗因)
2問目の見た目が過去問と似ており、途中まで似たような考察ができたので、簡単枠だと思って考察をする。
10分ほどで解法(嘘)が思いついたので実装する。実装をサボってまず1点を取りにいった。しかしWA。
実装ミスだと思い、色々書き直したりしていると1時間半ほど経っている。ここで落ち着いて図を書くと、1回の追加で2つ以上マージされる場合があることに気づく。この場合でも17点が取れる正解法がすぐにわかったが、面倒さに比べて点数が少ないと思ったのでやめる。
3問目を見ると、意味不明な数え上げをDPでやれと書いてある。図を書いて観察すると、状態数3^N*NのDPが分かるが、6点しか取れない上に実装が重い。そして多項式時間に落とせそうもない。
この時点で3時間ほど経っていて、まだ1点も取れていないことからかなり焦っていた。そのため、2問目がやっぱり簡単枠なんじゃないかと不安になって何度も2問目と3問目を行き来していた。
結局、2問目も3問目も不可能枠だと信じ込むことにして、それなりの点数を得やすいインタラクティブに行くことにした。

小課題1すら分からないが、先に小課題2,3を考えてみることにすると、嘘考察を交えながらも何とか思いつく。一瞬で実装でき、40点。ここまで3時間半。少し精神に余裕ができる。
小課題4を考えてみる。制約が二分探索をしろと言っているので考えると少し変えるだけだと分かるが、バグらせる。それでも30分ほどで通る。冷静な心を取り戻す。
2問目の17点を実装するか、1問目の満点を考えるかで迷ったが、他の人間が3桁点取っていると思っていたので、代表争いを考えて1問目の満点に行く。
しかし、疲れからか、嘘解法に突っ走ってしまう。結局解けなかったが、その嘘が小課題1に偶然適用できたので、使うと4点が取れる。そしてコンテスト終了。

結果・反省

結果は64+0+0=64点で、Day2/累積ともに3位。順位的には申し分ないが、6位と24点、13位と88点差と、全く安心できない。他の人の失敗に救われた感じはある。
最後の1時間で、2問目の17点を取りに行くべきだった。そこは戦略ミス。
また、最初に2問目の嘘解法の実装に時間を溶かしたのがとても痛い。競技の最初で失敗すると後に響くので、実装は慎重にしていきたい。
1問目を解いているときに、何度も諦めて2問目をやろうかと思ったが、解法に近づいているという感覚を信じられたおかげで耐えられた。大事。
難易度は11-11-12だと思った。もう少し差がつくセットを出してほしい気もするが、抜かされるのは嫌という...。

Day3

行く途中は緊張していたが、競技会場に入ると3日目なだけあって落ち着いた。

競技

最適化-グラフ+データ構造-コミュニケーション というセット。
1問目がとっつきやすそうなので見ると、ちょくちょく良い性質が見つかるが、スルーしてしまう。小課題がDPだと主張しているが、順序付けを色々考えてもうまくいかない。不安だったが難問枠だと信じ、1時間ほどで飛ばす。
2問目は、勘違いをしていて15分ほどで嘘解法を思いつく。幸いすぐ気づいたが、正しい考察をすると、実装量が異常であることが分かる。本質部分が2つに分けられるが、簡単な方のパートの時点で既にヤバいので、最後にやることにする。

3問目を読み始めたのは開始2時間後くらい。すぐに15点解法(嘘)が思いついたが、提出しても4点しか取れない。ただ、15点と85点で完全に問題が分かれているので、一旦飛ばした。
小課題5はすぐにわかったが、面倒なので実装しなかった。
小課題6は、本質的な考察は30分ほどでできたが、実装を始めると、枝分かれで詰むことが分かる。考察ミスだと思って30分ほど考えても分からなかったので、問題文をもう一度読み直すと、見落としていた情報に気づく。
これを利用すると満点が取れることが分かったが、この時点で4時間経っていた上に場合分けが多く、ミスを埋めこんでいた時点で詰むと思った。だが、1,2問目はこの状態からまともな点数を取れる気がしなかったので、これに賭けることにした。
実装しながら場合分けを考えていたので、書き上がったのは残り30分のとき。しかし提出すると0点である。WAケースを探そうと手作りのケースを色々試すと、運良く見つかる。それが合うように直して祈ると、85点が帰ってきて安堵した。
この時点で残り18分で、絶対100点を取るという気持ちで残り11点の考察をする。すると5分ででき、手を震えさせながら提出すると、合計100点になる。安心したので後はお祈りをしていた。

結果・反省

結果は0+0+100=100点で、Day3/累積ともに5位。2人に抜かされた形だが、4位との点差は絶望的なわけではない。
1問目で小課題1すら取れなかったのは完全に実力不足。2問目は3人に解かれているが、正直実装コストを考えると手を出さなくて正解だった。
3問目は、問題文の見落としが痛かった。明日は絶対にないようにしたい。また、場合分けは実装前に詰めておくべきだった。立ち回り自体は悪くなかったと思う。
難易度は12-11-11だと思った。
明日の今頃は代表が決まり、自分のJOI人生も終わると思うと感慨深い。Day4は悔いのないようにしたい。代表目指し頑張りましょう。

Day4

二度寝をしてしまったせいで、競技開始前にあくびがたくさん出た。こういう時にやったバチャは大体失敗しているので、不安になりながら競技開始。

競技

木-Output only-最適化 というセット。
1問目を見ると木の問題で、得意だと思っていたので嬉しくなる。小課題1,2を考えるといくつか嘘を思いつくので実装すると、0点。少し考えてもうまくいきそうにないので小課題3を考える。
すると、また嘘を思いついてしまう。ちゃんと考察すれば満点に繋がる解法だったが、適当すぎたせいで実装しながら頭を壊してしまった。
1時間半くらいで、一度諦めて3問目へ。小課題2までは一瞬で分かるが、小課題3以降は人間に不可能そうな雰囲気が漂っている。
この感じだと1,3問目が不可能枠で、Output onlyで点数を稼がないと代表になれないと思ったので、2問目でまともな点数を取りにいく。

少し考えると、焼きなましが効きそうだと思ったので、山登りのようなものを一旦書く。しかし、多く回すとWAになってしまう。この原因究明に1時間ほど掛けてしまった。提出すると37点。少し改善すると39点になった。
この時点でもう冷静に戦略を考える頭は残っていないので、そのまま2問目を伸ばしに行くが、全く伸びない。
そこで、とりあえず自明な3問目の小課題1を実装しながらプログラムを回すことにしたが、3問目は0点で、2問目は回数を増やしても全くスコアが伸びない。3問目のWAは意味不明だったので2問目と心中することにする。
実は「山登りのようなもの」は山登りになっていないことに残り30分ほどで気づく。しかし、もう自分の頭には肥大化したプログラムをどう変えれば山登りになるのか分からず、気がついたらコンテストが終わっていた。

結果・反省

0+42+0=42点、Day4で9位、累積5位。代表ボーダーとの点差は100点以上開いた。
もうガチでOIをやることはないので特に書くことはないが、受験生となる身としては、大事な日には二度寝をしないようにしたい。

供養

JOI過去問埋め
f:id:TA1SA:20200323172839p:plain
海外OIなど(oj.uz)
f:id:TA1SA:20200323172359p:plain

ポエム

くやしい
受験勉強頑張ります
日本代表を応援しています
PCKはいい成績とれるといいな(誰と組むんだろう)

JOI'17春合宿 Dragon 2

幾何パートとデータ構造パートに分かれている問題。幾何パートで下手な考察をして、場合分けと実装を爆発させてしまった。
データ構造パートで解説と違うことをしていたので、主にその部分について整理する。

問題

atcoder.jp

解法

解説にある最初の満点解法の、「aとbを入れ替える」条件を、サイズに依存するようにした解法。
(D1,E1)を点P1、(D2,E2)を点P2とする。また、i番目のドラゴンの位置をp[i]とする。
図を書いて頑張って考えてみる。
すると、各クエリでは、iを種族fの点、jを種族gの点として、(p[i]とP1のなす角,p[i]とP2のなす角)と(p[j]とP1のなす角、p[j]とP2のなす角)がある順序関係を満たすような(i,j)の組の数を数えればよいということが分かる。
これは、それぞれを二次元平面上の点と見て、x座標でソートしてy座標をBITで見れば、O((fのサイズ+gのサイズ)logN)で可能。全てのクエリでこれをすると、計算量はO(QNlogN)で、小課題2が解ける。
ここで、「同じペアはクエリに現れない」「各種族のサイズの合計がNで抑えられる」ということに注目すると、オーダーをmin(fのサイズ,gのサイズ)のみに依存するようにすると計算量が落ちそうという予想が立つ。
毎クエリでf,gの小さい方だけ走査するとき、走査数の合計はどのくらいだろうか。各種族のサイズで場合分けしてみる。
・サイズが√N以上のもの:それを走査するのが必要な相手はO(√N)個で、サイズの合計がO(N)なので、O(N√N)
・サイズが√N未満のもの:毎クエリO(√N)なので合計でO(Q√N)
よって、O((N+Q)√N)回となる。
fとgが非対称に見えるが、図を書いて頑張って考えると、逆にしても実際の処理は同じような問題に帰着できることが分かる。
サイズの大きい側のvectorにpush_backしていき、クエリを読んだ後に全てオフラインで処理すれば、1クエリO(logN)で分かるので、全体でO((N+Q)√NlogN)で解けた。

実装

ラムダ式でまとめたけど場合分けがひどい......。
atcoder.jp

感想

「本番中に通す難易度」は絶対に難易度12だと思う。2017年のめちゃくちゃ強い人たちが誰も小課題2以降を取ってない時点でお察し。

JOI'17春合宿 Port Facility

天才数え上げな見た目をしているのにゴリゴリデータ構造ゲーに落ちるという面白い問題。
かなり苦戦して通したので整理しようと思う。

問題

atcoder.jp

小課題1

条件を満たすように、区間の集合を2つのグループに分けた時の通り数を求める問題。
問題文にやることが書いてあるので、O(2^N)で全探索した後にO(N)でシミュレーションすれば良い。これでO(2^N*N)で解けた。

小課題2

どういう時に条件を満たすか考えると、「同じグループ内に、部分的に交差している2つの区間が存在しない」時だと分かる。
このような区間同士に辺を張ったグラフを考える。グループ分けを頂点への色塗りとして捉えると、辺の2端点の色が全て異なることが条件。
つまり、求めるものは二部彩色の通り数である。
二部グラフでないならば答えは0。二部グラフならば、連結成分ごとに2通りの彩色方法があるので、2^(連結成分数)が答えとなる。
二部グラフ判定と連結成分数を求めるのはDFSで容易にでき、グラフの辺数はO(N^2)本なので、O(N^2)で解けた。

小課題3・4

定石通り、区間を左端でソートし、順に見ていく。
この時、iと辺が張られるのは、「今までに出てきた区間のうち、Ai≦右端≦Biのもの」である。
区間にまとめて辺を張りたいので、Segment Treeで右端を管理してみよう。
各ノードには、「ノードが表す区間に含まれる、今までに出てきた右端の集合」を乗せる。
まず、連結成分数だけを求めることを考える。
「[Ai,Bi]に対して辺を張る」というクエリが飛んできたら、それが被覆するノード内の集合とiが同じ連結成分になるので、これら全てと辺を張れば良い。
こうすることで、愚直に張ったグラフと連結性が等しいグラフが出来上がる。
これだけだと計算量的には何の改善にもなっていないが、辺を張った後に集合をクリアするようにすれば、全体でO(NlogN)でできるようになる。今は連結性だけに興味があるので、ノード内に同連結成分のものは2つ以上必要ないからである。
右端をSegment Treeに追加する際には、その座標を含むノード全ての集合に追加するだけで良い。
構築したグラフ上でDFSすれば、連結成分が求まる。ここまで全てO(NlogN)で可能。
だが、このグラフでは二部グラフ判定はできない。ここからは二部グラフ判定の方法を考える。
連結成分を求めるのに使ったSegment Treeを活用したい。
ここで、各ノード内の集合について、「右端を追加する時に集合に入ったもの①」と、「辺を張る時に便宜上加えたもの②」に頂点を分けることを考える。②は高々1つしか存在しないことに注意。
この時、①と②の色は必ず異なり、①同士、②同士の色は必ず等しくなることが分かる。辺を張る時、両端がどっちに属しているかは明らかなので、各辺ごとに両端の色の関係が分かる。
この情報によって、DFSをする際に、色を決めてしまうことができる。ただし、ここで決めた色は必要条件にすぎないことに注意。
後は十分性をチェックすればよく、色が決まっていることから、実際にシミュレーションすれば良い。
全体でO(NlogN)で解けた。

実装

Segment Treeのノードにはvectorを乗せている。
定数倍で落ちたので、グラフの辺数を抑えるために、UnionFindを使って必要な辺だけ張るようにした。
atcoder.jp

感想

考察中にいい性質(使えるとは言っていない)が色々見つかって迷走してしまった。
こういう問題を短時間で解ける日は来るのかな......

JOI2020本選 参加記

去年
ta1sa.hatenablog.com

0日目

夜に謎の熱っぽさに襲われ、頭も痛かったので厳しい気持ちになった。

1日目

朝起きたら体調がマシになっていたので、難易度9バチャをする。しかし、1年前に自力で解けたTentsという問題が全然解けず、冷えた。
普通に一人で電車でつくばに向かった。去年と同じように毒蛇の脱走を考えていたが、小課題3以降の進展は結局なかった。
つくば駅ではラムネを買った。これが後の運命を左右することとなる(ほんまか?)
会場まではあまり迷わなかったが、途中つくばカピオに無意識に向かいかけてしまった。2年前にTwitterに大量に流れてきてたからしょうがないね。

行くと知っている人が結構いたが、この時点で体力をかなり使ってしまっていたので席でダラダラしていた。
ラクティスは、全完した後にEmacsのAdventureというゲームをやってみようとしたが、何を打ち込めばいいのかよく分からずまともにできなかった。
講義でOSSへの理解を深め、夕食では、炭水化物を大量に摂取した。ここでもあんまり積極的に交流はしなかった。人々の若さを感じた。

宿に着いた後はTentsを通して自信をつけようと思っていたが、スマホを入れた上着を脱ぎ捨てた際に独房のベッドの角にぶつけたらしくスマホの画面が割れ、とても悲しくなった。本選1週間前にPCの充電器とイヤホンを壊したばっかりだったのに...。
それを煽りに来た人々とわちゃわちゃした(なぜか名札が消え去った)。なんだかんだでその夜は色々な人と話した気がする。あとTentsは自分の方針だと先に進めないと知ってしまった。
22:30くらいに消灯したが、その後は体調の悪さ+緊張で体が火照ってしまい、ひたすらつらかった覚えがある。気がついたら眠っていて、朝だった。

2日目

6:15くらいに起きて外を見ると夜明け前で、空がグラデーションしていてなかなか良かった。朝食は、THE 日本食という感じで、質素だが自分は割と好きな感じだった。
気分を上げるために音楽を聴いたりし、本選会場に向かった。
開始まで謎の待機時間があり、その間に頭が痛くなってしまって険しかった。開始5分前からはワクワクの気持ちが勝っていた。

競技が開始すると、問題を見る前に諸々の前準備を済ませた。

1問目はすぐに貪欲が見え、証明もできたが、自分の頭を信用していなかったので部分点から取りにいった。あまり迷わず、22:12に満点。

2問目は、しばらくまともな解法が思いつかなかったが、「尺取り」というキーワードが思い浮かぶとすぐに解けた。47:54に満点。

3問目は、小課題1つ1つの意図がかなり明らかだったので、正当性を犠牲にまずDPテーブルを考えた。そして普通に正当性が分かったので実装すると、一発で満点が取れて感動した。74:50に満点。

4問目は、小課題1,2は割とすぐに分かった。メダルを取る気だったので満点を考えたが、不可能に見えた。そこで、安全策を取ろうと小課題1,2を先に実装したが、小課題2しか取れていない(129:07)。
「高々1つ」の誤読に加え、様々なバグを埋め込んでいたので、小課題1が通ったのは5問目の部分点を取った後、172:36のことだった。

5問目は、見た目は仰々しいが、問題文を読むと好きなタイプのクエリゲーであることが分かる。それぞれの小課題も意図が明らかで、ほぼ考察することなく分かってしまった。全人類これ取れてるんだろうなーと怖くなった。
RMQセグ木とBITを生やし、ほぼバグらせずに163:16に20点。

4問目の小課題1が最後の得点となったわけだが、そこから先は、5問目の満点 or 4問目の小課題3 で迷い、残り1時間であることを考えると、どう考えても実装が重そうな5問目は選ばないべきだと考えて4問目の小課題3をひたすら考えていた。
しかし、体力・集中力のなさからあまり考察に身が入らず、嘘解法を生やして悲しくなっただけだった。ただ、解説によるとあまり遠い方針でもなかったらしい。
もっとも、ラムネがなかったら3問目を通した時点で力尽きていただろう(伏線回収)。糖分大事。

結果は 100+100+100+16+20=336 という人間に取れる問題を全て取りましたねという点数だった。実際、自分の取ってない小課題はメダリストしか取っておらず、取った小課題は大量に通されていた。
去年も同じような取り方をしていて、結局1時間以上残してしまったので、成長を感じられなかった。

競技終了後は昼食だが、去年と同様お通夜ムードだった。治安は去年よりは良かったが、ボーダー予想が飛び交っていたのは変わらなかった。どうやら300前後らしい。
あと、自分より高い点数の種類数が3以上であることが確定し、悲しくなった。去年は3位だったが銅賞がもらえず、今年こそメダルが欲しいと思っていたからだ。
ただ、多分春合宿に通ったということで、若干の安心感もあった。シンガポールに行きたいのはもちろんだが、春合宿に行くことで得られるものはとても多いと思っていた。

解説と自分の感触を総合して、今回の難易度は 6-7-8-11-11 のようだった。4も5も完全に不可能な問題ではなかっただけに、自力で解けなかったのが悔やまれる。

今年はカラオケには行かず、普通に帰った。帰りながら4,5の考察をしようと思ったが、疲れからかあまり身が入らなかった。

反省

1-3のムーブはそれなりに理想的だった。1で部分点を実装せず、2をもう少し早く考察できればよかったという感じ。
問題はそこから、使う頭が変わってしまったというところにある。
1-3を解いている時は、脳をフル回転させていたという感覚があった。しかし4を解いている時は、意味もなく図を書いて考察した気になり、まともに頭を使えている時間が少なかったという感じがある。5に関してはそもそも満点は不可能だと思ってまともに考えなかった。
これは、難しい問題を、解けると信じて解いている時のモードで解く経験が全くなかったということと、体力不足に起因すると考えられる。
ただ難しいところは、満点を取れると信じて部分点の考察をおろそかにするのはかなりリスキーだということ。つまり、全ての小課題をまともに考察できる体力・集中力が必要。
春合宿までにこれをなんとしてもなんとかしたいので、色々やってみようと思う。(決死の十時間バチャ?流石にやりません...。)

10/27-11/9

文化祭でまともに競プロができていなかったので2週まとめて。
AtCoderのレートがいっぱい上がったしHTTFもユース枠で通ったのでよかった。

出たコンテスト

AGC040 90位 2043->2111
HTTF2020予選 73位
第2回全統プロコン予選 102位 2111->2163

解いた問題

ABC144-F Fork in the Road

https://atcoder.jp/contests/abc144/tasks/abc144_f
消す辺を全探索すると間に合わない。Nが小さいので、頂点ごとにそこから出る中でどの辺を消すのが最適かがわかればよい。
Nから逆順に「dp(i):iからNまでの通る辺数の期待値」をO(M)で求める。すると、各頂点ごとに、向かう先のdpの値が最大であるような辺を使えばよいと分かる。dpの遷移を考えると明らか。
これで消す辺の候補がO(N)本になったので、あとは各場合について愚直に計算すればO(NM)で解けた。

CF1246B Power Products

https://codeforces.com/contest/1246/problem/B
なんでコンテスト中に解けなかったんだろう...。
条件は、「ai*ajの素因数の指数が全てkの倍数である」ということに言い換えられる。
各aiについて、「根」を「aiの各素因数の指数をmod kしたものの積」とおくと、ai*ajが条件を満たすようなajの「根」が一意に定まる。よって、各aiについて素因数分解して「根」を求めれば、O(N√maxa)で解けた。

ABC020-D LCM Rush

https://atcoder.jp/contests/abc020/tasks/abc020_d
S(i):gcd(j,K)=i なるjの和(iはKの約数,1<=j<=N) とする。Kの約数の個数をLとおく。
T(i):iの倍数であるようなjの和 とすると、O(L)で全てのTが求まる。
S(i)=T(i)-(iの倍数jについてのS(j)の和) となるので、iを降順に見ていけば、O(L^2)で全てのS(i)を求められる。
lcm(i,K)=i*K/gcd(i,K) から、答えがS(i)*K/i の和だと分かるので、全体でO(√K+L^2)で答えが求まる。

第4回 ドワンゴからの挑戦状 予選-E ニワンゴくんの家探し

https://atcoder.jp/contests/dwacon2018-prelims/tasks/dwacon2018_prelims_e
重心分解をすることを考える。
次のような戦略でできる。
・今の部分木の重心を取り、その子をサイズの大きい順に並べる。
・2つずつ調べ、返ってきた方の部分木に潜る。
・もしなければ重心が答え。
サイズに大きい順に見ているのがミソ。
1回で見つかれば木のサイズが1/2以下になる。
2回で見つかれば木のサイズが1/3以下になる。
3回で見つかれば木のサイズが1/5以下になる。
全部3回必要になるケースで通るか怪しいが、N<=2000なおかげでギリギリ通る。

JSC2019予選-E Card Collector

https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_e
Ri-Ciグラフを考えると、「全頂点の出次数が1を超えないように向き付けられるような辺集合について、重み和の最大値を求めよ」という問題になる。
実は、各連結成分について「辺数<=頂点数」を満たす時が最適。これは木+1辺、または木となるので、適当に向き付けていけば上の条件を満たすことがわかる。逆に、それ以上辺が増えると条件を満たすことがない。
後は、辺を重みの大きい方から見ていき、加えても条件を満たすなら加える、というクラスカル法のようなことをすればよい。正当性はクラスカル法と同様に示せる。

第二回全国統一プログラミング王決定戦予選-D Shortest Path on a Line

https://atcoder.jp/contests/nikkei2019-2-qual/tasks/nikkei2019_2_qual_d
最終的な最短路を考えた時に、辺の張り方から、「逆行」がないようなものが必ず存在。つまり、DAGとして考えてよい。
dp(i):iまでの最短路の長さ というDPをする。区間を終点でソートして考える。
ある区間[L,R]を見ている時、実はdp(R)のみ更新すればよいことが示せる。
遷移は、dp(R)=min(dp(k)+C)(L<=k < R) となり、これはセグ木でO(logN)ででき、全体でO(NlogN)で解けた。

感想

文化祭休み最高!