hogecoder

tsutaj 競技プログラミングの記録

ACPC 2018 参加記

勉強会参加記

会津大学プログラミング合宿 2018 に参加しました。ACPC は実は初参加です。

0 日目

JAG に行っていたので東京にいた。TIke さんと seica さんと ferin さんと olphe さんでボドゲカフェに行ってあそんだ。ワイナリーはワイン農家をやめた者が勝つゲームだった (いやプレイングが悪かったのもあると思うけど)

その後夕食を食べに行ったが seica ちゃんが限界をしていておもしろかった。夕食後解散になったが実は宿を取っておらず (は？) 東京駅近くで適当に発見したネカフェに泊まった。これがまた結構あたりを引いて、ネカフェなのに完全に個室だしコインランドリーはあるしシャワーも追加料金なしで使えてとてもよかった。次に東京行くときはまたお世話になります。

1 日目

東京からバスで会津に移動。会津に着いてバスから降りた瞬間 olphe さんと waku 君に遭遇したので一緒に会津大学まで歩く。けっこうあるくね

この日のチームはランダムに決めていただきました。pachicobue さん、tubuann さん、moritaoy さんと 4 人でチームを組みました。自分は C の篩書くやつと E の虚無 DP と B の戦犯を担当しました。(制約をよく読まずに、積分するみたいなミスリードをしてしまい多大な迷惑をおかけしました・・・)

解説聞いたら E は貪欲でも解けるらしいんですが貪欲が世界一苦手なのでしょうがないね。あと不可能が 2 〜 3 問あっておもしろかった

この日の懇親会は中止でしたが、宿が近い人たち 10 人くらいで集まって中華料理屋行って魔女ラーメンを食べてきた (魔女なので (いいえ))

2 日目

5 時間の会津セット、この日は事前にチームを組んでいて、drken さんと TIke さんと一緒に出ました。

自分は D を担当したんですが FA が取れなくてかなしいね。あと G は結構悩んだのですが場合分けすれば簡単に解けてしまい、場合分け力のなさをかんじた。あとは TIke さんとペアプロしたりしなかったり、一緒に考察したりしなかったりしてました。後ろの問題はほぼ drken さんが通していました (流石すぎる・・・)

†懇親会† ではお酒が無限に出るのでもちろんビールをたくさん飲んだんですが、体の許容量が有限だったので破滅しました。記念撮影から記憶が全くなくて気づいたら宿の和室で寝てました。ご迷惑をおかけしました・・・

3 日目

なんか普通におきられたので大学に行った。この日はコンテストの運営でした。やはりコンテスト開始 2 時間前に会場入りする作戦はかなり有効で、今回もちょうどよく準備を終わらせることができました。

特に大きなミスもなくコンテストが無事終わったので、とてもよかった！ (ただ、G が既出なのはすいませんでした・・・)

終わった後は TIke さんと ｼﾝﾔｶﾄｰ さんと Noimin さんとカラオケに行きました。みんな仕上がってた。次の機会までにまた練習しとくか〜

この日は引き続き会津に泊まることにしていて、まだ行ったことがなかった富士の湯に行った。あれは最高だったね、至急札幌にもつくってほしい

その後帰ろうとしたんですが道中にボウリング場を発見したので 2 時間投げてきてしまった、温泉の後にボウリングをすると汗をかくのでオススメしません (それはそう)

4 日目

適当に観光をした。

あとこの日の宿は郡山で取っていたので郡山まで移動した。爆睡しすぎて駅員に起こされた (もうしわけない)

宿に着いた後に CODE FESTIVAL 予選 A がありましたが、解ける数え上げがたくさん出たので通過した。いえい

5 日目

空港まで移動して、飛行機で新千歳へ。まだ新千歳空港のフードコードが復活していなくてかなしい・・・

そんなこんなで帰宅

作問について

気づいたら自分が作った問題がセットの半分以上を占めていました。RUPC で簡単めにしたらやたら解かれたのでちょっと難しくしましたがそれでもやたら解かれました。合宿のレベルがあがっているのを感じますね。

B 問題

北大の B 問題は難しい説、そろそろ定着しそう (ア

あるデータ構造で管理するとクエリ O(1) で処理できて嬉しいです。他にも想定解はあったのですが、クエリ平方分割は完全に想定外でした。

正直なんでこの問題が生えたのかよくわかってません。生えるときは生えるんですよね、作問って・・・

E 問題

5 秒くらいで適当に思いついた問題です。分かる人にとっては解法まで一本道でいけると思いますが、コーナーケースにひっかからないように気をつける必要があります。実際、コーナーで引っかかった人は多かったようです。

F 問題

最初思いついた問題文が解法を隠しきれていなくてアレだったので、頑張って問題設定を考えた結果こうなりました。それなりに隠せたのではないかと自負していますが、隠しすぎて想定解通りに通してくれた人がほとんどいませんでした (ア

G 問題

ありがちな問題設定なので事前にかぶっていないかどうかこちらでも調べていたのですが、どうやら既出だったようです。すみません・・・。 コンテスト中に beet さんからこの問題の解説記事の印刷クエリが飛んできてすべてを察した

元々は unique でない数え上げをさせるつもりでした。ちなみに unique でない場合についても、真面目にやれば O(|S|^2) で、若干手を抜いてデータ構造に頼っても O(|S|^{2} \log^{2} |S|) くらいになります。興味があれば考えてみてください。

総括

合宿は楽しみながら圧倒的成長できる最高コンテンツですね (再確認)

来年もいくぞー！！！

JAG 夏合宿 2018 参加記

勉強会参加記 ICPC

初めて JAG 夏合宿に参加しました。同じ大学からは four-t のチームメイト (rsk0315 君と TAB 君) と waku 君も参加しました。以下、雑に記します。

0 日目

札幌から東京まで移動した。なんか自分が離陸した後に新千歳行きの電車が止まったらしく、わりとあぶなかった・・・

無事成田空港に着陸し、その場で本日の分の宿を取る (は？) なんとか新宿の宿が取れてよかった。計画性を身につけたい。

1 日目

オリンピックセンターに集合する前に four-t の愉快な仲間たちと昼食に行った。確かカツ丼を食べたような・・・

ご飯を済ませてオリンピックセンターに向かう途中、いつもの人々 (TL で限界をしがちな人々) がいたので一緒に会場まで行くことに。TAB 君が道案内のプロだった。

ガイダンスがあった後に自己紹介があった。名乗るだけで笑いがおきるこたつがめしゃん

チーム決めの時間があったがすでにチームが決まっているのでおしゃべりをする。そうこうしているうちにコンテストが始まる。1 日目は海外リージョンの国内予選の問題だったようです。

チーム戦の時は TAB が A を、rsk0315 が B を、自分が C をまず読むのが固定化されているので、今回もそれにしたがって読んでいった。C 問題はいもす法を知っていれば解けるやつだったのですぐ解けた。A も B もすぐ通ったので、3 完した時点で一瞬 1 位になっておもしろかった。

D は何すればいいかはわかるけど実装が大変・・・という感じだったが rsk0315 が 「list で常勝ｗ」 とか言っていたので書いてもらった。通った。はいプロ

この辺で E を TAB と一緒に解くが永遠に通らなくて悲しくなった。その間に、不可能に見えていた F を rsk0315 が頑張って考察して通していた。凄いなあ。

結果は 5 完でした。自分 1 人だったら 3 完で終わってそう、チームメイト様々でした。

コンテスト後に解説があって、その後は部屋に移動。今年は 3〜4 人で一部屋を使うようで、 algon さんと imulan さんと一緒の部屋になりました。

この日の夜に AGC があって、談話室で参加。C が解けたためレートが上がって嬉しかった。

2 日目

Writer が豪華なセットでした。

A は若干詰まっていたらしいので見る。 109 + 7 ずつ増やして全探索すれば良さそうということがわかったのでそれを伝えて書いてもらう。通った。うれしいね。

B も詰まっていたらしいので見る。1, 5, 10, 50, 100 円玉を使うパターンはとても少ないので全探索すれば良いことがわかったので書く。通った。うれしいね。

C は見たけど数学が壊滅的な自分には解けないのでチームメイトに解いてもらう。その間に他の問題を見てみたが、なかなか虚無で・・・ (この後 3 時間くらい無が訪れる、考察はしていたけど)

H は prefix の包含関係による重複数え上げをどうにかしたい気持ちになったので、Suffix Array と Rolling Hash を使ってどうにかする解法を思いついたので書く。通る。やったね。

E も解法はだいたい思いついたが高速化部分がどうも思いつかない (bitset 使ったけど TLE を食らった)。終了 15 分前くらいに FFT で行けることに気づいたけど時既に遅し、あまりにも時間が足りなすぎて終了。悲しいなあ・・・。

この日は 4 完でした。E は FFT もっと早く思いついていたら確実に解けていたので、本当にもったいない。こういうミス無くしたいですね。

3 日目

この日は JAG のセットでした。典型詰め合わせみたいなセットで割と好き。

A がなんかつらそうだったので見る。解法の確認をして落ち着いて通した。B は全く見てないけど rsk0315 が通してた。C はよくある DP をやれば終わりなので書いて通した。

この後に何をやるかは少し迷ったが、順当に順位表で解かれているやつを中心に考察をした。まず J は TAB と一緒に考えたところ偶奇で分けて考えると素直に解けることがわかったので自分が書く。少しバグったが通った。次に I は自分が J を書いている間に TAB ・ rsk0315 が大体考察を終えてくれていて、実装時に自分も少し手伝って通した。

この時点で G はあまり解かれていなかったが、なんか解けそうだったので考察していた。前から見ると今考慮している数字が何の位なのか扱いづらかったので、後ろから見ていく DP をすることにした。実装方針はかなり気をつけなければならないが、 TAB が条件を簡単にしてくれて助かった。ちゃんと紙で考察したのもあって一発で通ってうれしいね。

終盤になって、他がよく通している F が残っていたので通したいねーという気持ちになった。実験してみると条件はだいたい見えるが例外があるのかよくわからなくて怖い。とりあえずわかっている条件を全部書いたら通った (えぇ・・・) これは反省なんですが F を通すのが遅すぎで、もっと早くに実験すべきだと思った。これは自分の戦略ミスです。

総括

3 日間とても短かった。あと一週間長くても良いくらいだった (ホンマか？)

今回思ったのは長時間コンテストになるとライブラリの豊富さとか、そのへんの知識が結構要求されますね。もっと知識をみにつけていきたい。

ちゃんと復習もしつつ、明後日の会津合宿の準備もしつつ、精進していきたい！！！

ICPC 国内予選 2018 参加記

ICPC 大会参加記

昨日、ACM-ICPC 国際大学対抗プログラミングコンテストの国内予選 が行われました。自分が所属する北海道大学からは 4 チームが参加し、3 チームが 4 完・1 チームが 3 完しました。このうち 2 チームはアジア地区に行けそうで、弊学サークル全体のレベルの高まりを感じています。

f:id:tsutaj:20180707081755p:plain

チーム情報

今年も four-t として参加しました。メンバーは構文解析のプロ・ rsk0315 ( @rsk0315_h4x ) と幾何のプロ・ TAB ( @_____TAB_____ ) と数え上げが解けたり解けなかったりする趣味・自分 (tsutaj) の 3 人で、結成 2 年目です*1 。お茶汲み要員にならないようにがんばりました。

本番前

去年 Practice 1 位だったし*2 、今年も目指すか！例の数字をライブラリとして印刷して Practice も常勝！！！

・・・と思っていたけど、開いてみたら最後の問題が 500 円玉貯金 (2015 年国内予選 D) で草。まあこういう系統はかなり解いてきたし自分の担当分野でもあるので肩慣らしに解く。なんやかんやで今年も Practice 1 位になれました。

その後順位表のリセットが 2 回くらいあったけどその都度即座に提出して 1 位を防衛した (謎) (結果的にサブミットの練習になりまくった)

本番

本番の序盤の戦略は、TAB 君・えび君が A を読みつつ印刷クエリを投げ、自分は印刷されたものを眺めながら解けそうな人に問題を投げるという感じ。紙を届ける頃には A が終わっていたので (4:54)、実装ゲーっぽい B をえび君に、ちょっとした数学っぽい C を TAB 君に、そして自分は数え上げっぽい D をやることに。

D は見た目がアレなので (？) C を TAB 君と一緒に考えてみると、少し数学をして探索範囲を小さくすればよいことに気づく (割とすぐに気づいた)。 TAB 君と自分とで相談してみて方針が良さそうだったので TAB 君に実装してもらう。すぐ通してもらった (21:10) (ありがとう)

F は幾何で G が構文解析っぽいので、ここらへんで F を TAB 君に・G をえび君に投げて、解くべきかどうか判定してもらうことに。G はなんか無理そうで F は頑張れば行けそうな感じだったので、F を TAB 君に考えてもらう。

B はなんかつらそうにしていたので先に D を詰める。よく見るとサンプルの最後のケースが最悪ケースだが場合の数が少ないし、そもそも全チームの勝敗数が同じなら全チーム \frac{N-1}{2} 勝 \frac{N-1}{2} 敗しているはずなので、枝刈り全探索で良さそうなことに気づく。

ここで F を考えていた TAB 君が解法を思いついたらしいので、D と F を並行して実装していく。やがて D が書き終わったので実行するも、やはりサンプルの最後の実行にはそれなりに時間がかかる。「D は書けたけどテストケースの実行にそれなりに時間かかりそうだし、F の実装してる間に並行して D を実行させるか〜」とか言ってたんだけど、最適化オプションつけたら爆速で終わって草。並行してやる必要ないやんけ！そんなこんなで D を通す (53:12)

B は書けたらしいが提出すると WA が返ってきたので、えび君がソースコードを印刷してバグを探す段階に入っていた。また F は途中まで書けたがその後の実装方針を詰めなければならないらしい。自分は他の問題を眺めるもすぐ解けそうなものはない。ここで取れる戦略としては色々あったと思うけど、自分は順位表と残りの問題の感触からまず B を優先すべきと判断し、F を引き続き TAB 君に考察してもらいながら、自分とえび君で B のソースコードを読むことに。

B のソースコードの問題点はしばらくしたら見つかった。PC を使っていた TAB 君に交代してもらって B を直して提出するもまたもや WA が返ってくる。操作中の配列を visualize しても挙動は間違ってなさそうなので、悶々とするなどした。

こういうときは「実装方針を変えれば良い」ということを去年のアジア地区で身をもって知っていた*3 ため、B の楽な実装方針を考えてみる。すると今まで考えていた場合分けが不要な実装方針を思いついたので、それを自分が書くことにした。

問題文を読みながら、入力を受け取ってここはこう処理して〜と書いてるうちに、実は誤読しているのでは？ということにここでようやく気づく。どうやら縦に折るときは紙の下から何番目の線で折るかが指定されるらしい (今までの実装は上から何番目かで考えていた)。ということでそこを直して提出すると、やっと通る！！！ (2:13:31, 2 penalties)

次にどの問題を優先すべきかを考えてみる。順位表を見ると F が全然解かれていないし、F の解法を説明されても完全な理解ができない (申し訳ない・・・) ので、E をやることに。この判断は大反省です (後述)

E は残り 15 分でそれっぽいものは思いついたので書くも、そこで時間切れ。よくよく考えたら桁落ちを考えていない解法だったためどちらにしろダメでした。

B で割と詰まったけど、ACD の早解きが効いて 39 位で終了。今年もアジア地区に行けそうで嬉しいです。

反省

序盤の立ち回りはアレが正解だったと思う。事実、開始 1 時間時点では 1 桁順位だったらしい (あんまり見てないけど)

問題はその後で、まず B を助けに行くのはおそらく間違っていなかったと思う。ただし助け方にもいろいろあって、今回は既にあるものを直すか新しく書きなおすかがあったと思うけど、結果論にはなるが新しく書きなおしたほうがもしかしたらよかったのかもしれない。新しく書きなおそうとしてみて思ったけど、複数人が「問題文を読む」だけでなく「実際に実装する」と、読むだけでは気づかなかった欠陥を発見できるので、詰まったらとりあえず別の人が書いてみるというのは有効だと思う (ただし 1 から書きなおすほうがタイムロスが大きい場合も当然あるので、既にあるものを直してどうにかなるならそれに越したことはない)。

B を助けるタイミングおよびその速度は、いろいろ改善の余地があるけどあれは仕方ないと思う。自分は他の人のソースコードを見るのがそれほど苦に感じないし、どちらかというとバグ直しが得意な方ではあるけど、あれよりも速くバグ直しができるようになるのかはよくわからない。

チームの指令塔的役割として最大のミスはやはり 4 完後の立ち回りだったと思う。F は解法がある程度見えているにも関わらず、順位表の感触から E に行ってしまって申し訳ない気持ち・・・。これは完全に自分のミスです。F をもう少し詰めていればもう 1 問解けていたのかもしれないです。結果的に F がうまくいってもいかなくても反省すべき。

さいごに

やっぱりチーム戦は奥が深くて楽しいですね。ずっとやっていたいけど今年と来年しかできないの悲しいなあ・・・ (早生まれだし来年があるだけでも幸運なんだけどね)

もっと強くなって横浜でも存分に戦いたいです！！！

*1:去年の様子はこちら → ICPC 国内予選 2017 参加記 - hogecoder

*2:例の数字を暗記していたため

*3:当時のガチ反省記 → ACM-ICPC 2017 Asia Tsukuba Regional Contest 反省記 (コンテスト部分のみ) - hogecoder