JAG夏合宿2019 参加記

2019/09/14-2018/09/16に行われたJAG夏合宿2019に参加してきました。

コンテストには三日間ともチームAobayama_dropoutで出ました。

day1

チームメイト3人全員そろって新幹線で行くことにします。どの新幹線に乗るかをうまく共有できなかったりして、結局新幹線の発車1分前に全員揃うことに成功します。あぶね~

オリセンについて、名前を言うだけの自己紹介をして、コンテストです。今年は初日から5時間セットでした。

コンテスト

チームの方針として、去年は10行くらいのテンプレートを書いていましたが、最近はbits/stdc++.hのインクルードと575;だけにしています。

まず初めに碧黴さんがA、ゆきのんさんがB、僕がCを読みます。それぞれ解けたのでその順番で書きます。AC。

他の問題を全部読んでしばらく考えたところ、D問題が解けることに気づきます。書いたのですが、WAが取れません。その間にゆきのんさんがE問題を書いて出しましたが、これも通りません。

J問題が多く解かれているので碧黴さんとゆきのんさんが考えたところ、部分問題のうち片方が解けます。もう片方は僕が二部マッチングであることを指摘し、通ります。

ずっとD問題のWAの原因を考えていたのですが、さすがにこれはlong longですらオーバーフローしているんじゃないかとなってPythonで書き直すと通り、キレました。

E問題はMODを取って同一性の判定をしていたのですが、このMODを適当に増やすことにします。ここで||と&&を間違えるとんでもないミスをしてしまいさらにWAを重ねましたが、最終的に気づくことができてAC。

ABCDEJの六完でした。

談話室でボードゲームをしました。日付が変わって談話室が使えなくなり314号室に引っ込みましたが、そこに数人の来客があって午前2時までおしゃべりをしていました。

特にある文字列から(連続とは限らない)部分文字列を取り出して別の単語を作るという遊びに熱中しました。以下に秀逸であると判定されたものを紹介します。

day2

コンテスト

問題の難易度が最初の3問を含めてすべてバラバラなので、全員が全部読むことにします。読んでいると近くの席にE問題の風船が配られており、急いでその問題を確認しなおすとギャグであることがわかるので慌ててPCを確保しAC。

次に碧黴さんがD問題を書きます。TLEが出たので、聞いていてちょっと怪しいと思った考察の部分をそれに依存しない方法に書き換えるとAC。

D問題が実装されている間にA問題もちまちま進めていて、ほどなくAC。

I問題が解かれているので、それを考えます。Nが小さいときはUFで愚直に書けて、Nが大きいときはかなりシンプルに判定できることが分かったので実装するとWA。閾値を変えてみましたが同じくWAです。

考察の見直しをしますが、まったく間違いが見つかりません。これはどうしたものかと悩んでいると、なんとジャッジが間違っていたことが判明。すでに投げたものがリジャッジされるので、それで通ることを祈ってほかの問題を考えることにします。

Iは通りましたが、そのあとほかの問題を解くことができず、結局ADEIの四完。残念……

コンテストが終わってないのにジャッジ側のらてあさんとにらめっこしたりしていたのはかなり意味不明でした。不正か?

ABCがあったので、自室からテザリングで出ます。AB問題をコードゴルフすると宣言しており、数人の観客に囲まれて開始時間を迎えます。緊張する……

まずAを開くと、sedが最短であることがわかります。しかしsedは改行コードを1Byteにする関係でsubmitに少し手間取ることが予想されたので、まずPascalで0msを出してfastestを狙うことにしました。

無事通ったのでsedも提出し、Bを開きます。これはぱっと見て最短がどんなものになるかわからなかったので、こちらも先にPascalで0msを出しておきます。

最短を狙うにあたって、まずPerlで数回提出します。最初はgrepを使っていたのですが、結局正規表現一回で書けることが分かったので、sedに移行してさらに縮めました。

あとは普通に問題を解いていきます。全完したのでJuliaでも提出しておこうとしましたが、ノーパソにJuliaの実行環境がなくてAtCoderのコードテストなどを使ったりするうちにコンテストが終了してしまい、F問題を時間内に(Juliaで)提出することができませんでした。

そのあとコードゴルフを続けましたが、ABの他は最短が取れずじまいで残念でした。

day3

今日は4時間セットです。

コンテスト

碧黴さんがAを読んでいましたが、チーム全員arbitraryを訳すことができず、WA。Bの考察が完了していなかったので先にCを書くとFA。Bを投げられたのでしばらく考えているとにぶたんできることに気づき、オーバーフローギリギリの値が入力されることにキレながらAC。

全部読むとJが解けそうな気になるので、ずっと考えていましたが、完全グラフから完全マッチングを取ってくることができず諦めます。この時点で残り一時間半とかで、5時間セットの感覚でいたことに気づきましたが時すでに遅し。

ゆきのんさんがDをずっと考察していて、僕はそれを横目にほかの問題を考えることにします。EとHが解かれていて、Hはかなり前にやることが分かっていましたが実装が全然見えなかったのでEを考えます。

最初に読んだ時からずっとDPだと思っていて、そういう風にみると降順でソートしてよいことが示せます。それからもかなり時間がかかりましたが次元を落とすいつものやつができて、PCを開けてもらって書くと通りました。

E問題のACは終了8分前でしたが、ABCの3問がかなり速かったのでペナ差で四完最速となりました。

帰宅

間一日挟んで09/18からACPCがあります。キツすぎる……