memo46

競プロの精進記録その他。

ACPC2019 参加記

ACPC(会津大学競技プログラミング合宿)2019に参加しました。

Day1

yamadさん、tsubasaさん、suta、Hyado君と東京駅に朝集合し、一緒に会津大学に向かいました。朝東京駅でHyado君が東京駅の改札前で競プロし始めて驚きました。熱意がすごい...

 郡山駅から電車に乗ると、続々と色々な競プロerの方々が乗車してきました。

 

 おおお、これがACPCか...とワクワクしながら電車の中で蟻本を読んでいると、会津若松駅に着きました(忘れました、蟻本を読みながら寝落ちしていたかも...)

 

会津若松駅から徒歩で|会|津|大|学|まで行きました。

 オンサイトでもらう名札、すき

 他の競プロerの方々は早速交流をしていらっしゃいましたが、自分は知り合いが少ないのも相まって1人でEDPCを埋めていました。

そして、チーム決め。自分は全日ランダムでチームを組ませていただくことにしていました。チーム名が決まらなかったので、mtsdさんが「チーム名 かっこいい」と検索して出てきたものをチーム名にすることになりました(?)

まず、チーム内でレートが一番低い自分がAを読むことになりました。まあはいなのですぐ書いてAC。続いてokさんがBをAC。Cを読んでmtsdさんに概要を伝えると、

「あ、強連結成分分解をすればいいですね。ライブラリ持ってますか」

「持ってません...」

ということで、mtsdさんが爆速で書いてAC。すごい...

続いてD、Eの考察も終了していたそうで(早すぎる)、概要を聞いて実装を試みるも詰まったのでmtsdさんにバトンタッチをお願いすると、mtsdさんが無限にデバッグに苦しむ。mtsdさんは死闘の末にDを通していましたが(すごい)その間はずっと椅子を温めていました...

 コンテスト終了後は喜多方ラーメンを食べ、ホテルの近くの銭湯に行きました。ぼくは疲れて風呂で寝てしまうなどしてしまいましたが、まあこれで1日目は終わりました。

 

 Day2

day1の疲れからかホテルで8hほど爆睡しました。気持ちの良い朝でした。

day2はgoodbatonさんとharuさんとのチームでした。5hセットでできるだけ椅子を温めないように頑張ろうと思っていました。

 A,B,Cが難易度順で、D~Mはランダムだと聞いていたので、まずharuさんとぼくでA,B,Cをやり、後ろの問題をgoodbatonさんが見ることになっていました。まずharuさんがAをサクッとAC。BをぼくがAC。

Cの概要をharuさんから聞くと、next_permutationで全探索すればよさそうだったのでぼくが書くことに。幾何に慣れていなかったのでバグらせてしまう。その間にgoodbatonさんがJを書きますとおっしゃっていたので、バグっている箇所を探す。幾何ライブラリをググって、その使い方を調べることをしていました。その後幾何ライブラリの使い方が分かったので、書くとサンプルがやっと合う。(ソートし忘れて1ペナ生やしてしまったけど)なんとかAC。goodbatonさんもデバッグに苦しんでいらっしゃいましたが、ついにJをAC。オンサイトFAだったそうです。すごすぎる...。

順位表を見るとMがやたら解かれているので見ると、goodbatonさんが「式変形を頑張るといけそう」とおっしゃったので、Mを僕に渡してもらい、goodbatonさんが他の問題を考えることに。

僕が式変形をゴリゴリ頑張っていると、まずはO(N^2)の形になる。goodbatonさんがIを書き始めたので、そのまま式を眺めているとO(NlogN)に落ちることに気づく。goodbatonさんがIをACしたので(すごい)、その後Mを僕が書きAC。

その後はgoodbatonさんがHを読み、「これは包除で...」とおっしゃっていたが、正直よくわからなかったです(ごめんなさい...)。包除原理を調べたりしていました。デバッグに苦しんでいらっしゃいましたが、HをAC。オレンジコーダー強い...

その後はLを考えたり(ここで45度回転を知った)Gをgoodbatonさんが実装しているところを眺めているとコンテストが終了してしまいました。

かなり勉強になったコンテストでした。

 その後は懇親会でした。5hコンテストで昼食を食べそこねたので、かなりお腹が空いていました。懇親会は果実酒も堪能したし、本当に様々な競プロerの方々と交流することができてとても満足することができました。特にNOSSさんやmtsdさん、goodbatonさんとよくお話させて頂いたような気がします。ありがとうございました。後、酔ったbeetさんが四足歩行していたのが面白かったです。

 その後はまた銭湯に行き、ホテルに帰ってday2の復習をしていたらいつのまにか3:30とかになっていました...

後、この日あったえでゅふぉがsemirated?みたいなよくわからないことになっていて面白かったです。

day3

 day3はc7c7さんとそすうささんとチームで参加しました。チーム名さん...

 c7c7さんが二日酔いでつらそうにしていて面白かった

 

まず自分はAを読んでAC。Bも実装が重かったらしいんですが、そすうささんがサクッと通していた。すごい。Cはc7c7さんが書いて、コーナーケースに苦しみながらもAC。Dは見た目が桁DPで、「これはいける!!!」と思ったんですが、たくさん介護してもらったにも関わらず無限にバグらせてしまいました(悲しい...)

Eは見た目がセグ木だったんですが、実装がつらそうでした...

結局、たくさんPCを占拠してしまったのにDを通せず、3完で終了しました。

Dは通り数を求めるDPと総和を求めるDPを2つやればよくて、かなり勉強になりました。これでACPC2019が終わりました。

帰りは爆睡をしたり、day3のDやday2のI問題を復習したりしていました。

感想

本当にとても楽しかったです。特に、今まではあまりできていなかった競プロerの交流を懇親会で満足にできたことがとても嬉しかったです。勉強したい事柄も色々増えました。来年はもっとチームの戦力になれるよう精進してまたACPCに参加したいです。

運営の皆様、また作問者の皆様、楽しいコンテストをありがとうございました!

ICPC 国内予選2019 参加記

7/13のICPC国内予選に、SUAN(@apt_get)とwbiraki(@biraki_prg)とチーム SASUSHIRO で参加しました。

icpcsec.firebaseapp.com

結果は、A,B,Cの3完 156位 学内6/11位でした。

 

 

 

以下、当日の流れと反省です。

当日の流れ

午前中はリハーサルをwbirakiと2人でJ,K,Lを解く。PCの設定やコマンドを確認する。

3限後すぐに本番の会場にチーム3人で向かう。他のチームとお菓子を食べながらワイワイ喋り、時間を潰す。楽しかった。

ちゃんと印刷ができるかどうかを確認して、蟻本やライブラリも準備できることを確認して、数分Twitterをすると本番3分前ぐらいになったため、Twitterを閉じる。

コンテストが始まると即問題用紙を印刷、その間にAを僕が書いてAC。続いて印刷が完了し、wbirakiはB、ぼくがC、SUANがDを読む。

ぼくがCを読むと、まぁ全探索だなあとなり実装方針を考えていると、wbirakiがBいけると言ってくれたのでwbirakiにPCをバトンタッチ。SUANもDはいけるがかなり面倒くさそうとのことだったので、僕はその間にCの実装方針を練る。

あらかた実装方針が定まったところで、wbirakiがBのバグに苦しむ。SUANと一緒にデバッグする。その間に僕は他の問題を読んだり、DやFを考えたりする。Fは最小全域木では...などと思う。(そんなことはなかったんですがね...(泣))そんなこんなでBが通る。

ここでPCをバトンタッチし、ぼくがCを書く。サンプルを試すと通らない。なんでやねん!となる。CをSUANと一緒にデバッグする。すると、3bit全探索をしなければならないことに気づき、書き直すとサンプルが通るがWA。泣いた。

一旦Cを紙デバッグし、SUANにバトンタッチしてDを書いてもらう。がサンプルが通らない。みんなで絶望的な気持ちになる。

ここからは紙とPCをいったりきたりして、CかDを必死に通そうという話になる。しかし通らないC。ダメかなあと思ったが、SUANがCの探索し忘れているパターンに気づく。1行追加して投げるとCorrect Answerが返ってくる。ここで残り2分、そのままコンテストが終わりました。

反省点

・考察をしっかりしよう(Cみたいな全探索はぼくの役割だったはずで、ここはしっかり1人でACしたかった)

・ライブラリの印刷は前々からしっかりやる(前日夜に急いで印刷したため、印刷し忘れがあった(は?))

・チーム練習を増やす。

・精進する。AOJ-ICPCを埋める。

まとめ

最後残り2分でCが通った時は思わずチーム全員で声が出ました。なんとか3完できてよかったです。

 

とはいえ、自分的にはかなり不完全燃焼でした。自分は実装が苦手なのでSUANに割と頼っているところがあったのですが、流石に今日のCは自力でサッとACできるべきでした。来年は寒色コーダー(欲を言えば暖色)になって、ライブラリをしっかり準備して、チーム練習も十分に積んで、アジア予選進出を目指したいです。

 

最後に、ここまでICPCのサポートをしてくださったり部屋を貸してくださったり、ピザと寿司とお菓子を奢って下さった弊大学の先輩方、先生方、本当にありがとうございました。本当に至れり尽くせりでした。

また、ぼくが頼んで一緒にICPCに出ることを承諾してくれたチームメイトにも感謝しています。

来年はもっといい結果が残せるようにしっかり精進したいと思います。

P.S.

競プロerと食う寿司とピザは美味え

 

 

 

ICPC 模擬国内2019 参加記

6/30 のICPC模擬国内に、同じ学科&同じサークルの友人のSUAN(@apt_get)とチーム名「SASUSHIRO」 で参加しました。(もう1人のチームメイトであるwbiraki(@biraki_prg)は用事により残念ながら来られず)

jag-icpc.org

結果は、A,B,Cの3完 89位、学内6/10位でした。

以下に当日の流れと反省点等を書いていきたいと思います。

当日の流れ

印刷がまだだったのでAをSUANと一緒に読む。するとSUANがすぐにいけると言ってくれたので、SUANがすぐに書いてくれてAC。

その間に印刷が終わり、ぼくがBを読む。しかし問題を誤読し、任意の点から任意の点へ移っていったときのダメージの最小値だと思い込み、全く解法が浮かばない(それはそう)。

Bを考察している間にSUANがCを読み、考察を済ませる。はじめはSUANが実装していたもののWA。途中でぼくが実装し直し、さらにその後SUANが実装し直し、2WAでなんとかAC。

その後EやFを読んだりするが、無理だなあとなってDをSUANと一緒にやる。編集距離であることはすぐにわかったので、先に回転させてあとでDPをやる方針に走るが、実装していたぼくが無限にバグらせ、DPテーブルをプリントデバッグしたりと粘りまくる。

SUANが必死にデバッグしている横でふとBに目を通し「Bなんで解けねえんだろうなあ」と思いながらぼんやり眺めていると、ここでやっと誤読に気づく。(目的地を目指す順番は1->2->3...と決まっていたのにそれを勘違い)ごめんなさい...

誤読に気づくとすぐに実装を始めるが、バグる。SUANが書き直すが、やはりバグる。2人で必死にデバッグし、なんとかAC。Dに全力投球する。

必死のデバッグの結果なんとかサンプルが通るもWA。ここでタイプアップ!

反省点

・お前何もしてなくない?(書いてはバグを生み書いてはバグを生み、つらかった)

・問題文はよく読もう(AtCoderに比べてICPCの問題文は冗長なので、それの練習をしなければならない)

・精進不足(特に実装力。これがないともうどうしようもなくチームのお荷物になってしまう)

・ルールを把握してなかった(紙媒体なら閲覧可能で、蟻本と螺旋本を持ってたのに見ちゃ駄目だと思ってコンテスト中一回も見なかった...)

まとめ

とまあこんな感じでめちゃくちゃ反省点があるんですが、やっぱりチーム戦は楽しいですね。本番はwbirakiも来るはずなので、チームSASUSHIROがどこまでいけるか楽しみです。課題や試験で忙しいですがなんとか時間を作って精進を頑張りたいです。

 

最後に、模擬国内を開催してくださったOB/OG会の皆さんをはじめ、模擬国内に参加する環境を整えてくださった弊大学の先輩方、先生方、ありがとうございました。本番はもっと頑張りたいです。

P.S.

プロメアはいいぞ。

RUPC2019参加記

0日目

 

 

不安だったので前日入りしました

瀬田駅前のアパホテルに泊まりました

この日は特にやることもなく、元々ぼっち参戦だったのもあって、ずっとホテル内で精進したりサークル内企画の作業をしたりテレビを見たりスマブラをしたりして過ごしていました

一人で新幹線に乗って知らない土地に行くのは初めてだったのでなんか冒険感がありました 次の日のことを考えてワクワクしていました

 

1日目

名札もらった

 

初めに自己紹介がありました

ぼくは自己紹介で少し緊張して本名で挨拶しかけてしまいました...(あぶない)(いや別にいいんだけど)

 ぼっち参戦だし競プロを本格的に始めてからまだ3ヶ月ほどしか経っていなかったので右も左もわからず、ランダムでチームを組ませていただくことにしました(このチームランダム抽選はぼっちの僕にとてもありがたいシステムでした。運営様に感謝以外ありえません。本当にありがとうございます...)

抽選の結果、Hecさん、c7c7さん、nomiさん、ぼくの4人チームになりました

事前に少し話し合った結果、初めにぼくがAを解き、nomiさんがBを解き、c7c7さんがCを解き、Hecさんが後ろの方を見てくださることになりました

「確実に足を引っ張るけどなるべく最善のムーブを取らなきゃ...」と少し緊張していたらコンテストが始まりました

 

Aを少し読むと、まあなんかいけるやろと思い実装したらサンプルが通らなくて、問題文をちょっと読むと縦と横を見落としていました。焦るな焦るな

Aを通したことを伝えて周りを見るとほぼすべての机に赤い風船がついていて、RUPCのレベルの高さを思い知らされました(ぼくがたぶん一番遅かった)

そのあとすぐにnomiさんがBを通し、HecさんがEを通しました

Cの問題概要をc7c7さんが伝えてくださり全員で考えました(全く役に立てませんでしたが)

Hecさんがすぐにシミュレーションをして、奇数行偶数列には絶対石が置かれないことと、その軽い証明(あるマスに石を置くには、その位置から距離2の位置に同色の石が必ず存在しなければならない、今回は(5, 4)に初め石がないため、そこから距離2のマスには必ず石が置かれることはない)を教えてくださりました それを聞いた時は「すげぇ...」とため息が出ました感動しました writerさんは天才です

こういうシミュレーション系は紙よりもエディタでぱぱっとやるのが早いそうですね

ここまで来ると茶色コーダーのぼくは椅子を温め続けるしかありません

オセロの感動の余韻に浸りながらDを読んで、「この問題形式は初めて見た、何もわからん」と言っていると、c7c7さんがすぐに考察を終了させたようでした 話を聞いていましたが正直ほとんど何もわかりませんでした...

c7c7さんがDを実装してAC ぼくは椅子を(ry

そのあとc7c7さんとHecさんがGの考察をされていて、HecさんがGを通しました いや本当にすごい...

ぼくは何をしていたかというとずっとFをコネコネしていました 

「降順ソートしたい でも回数制限ある じゃあ貪欲にswapしたいなあ でも計算量が その時点でabsの小さい右端と左端をswapすると良いのでは」

みたいなところまでずっと考えていて、ダメ元で皆さんに伝えてみると「試す価値はある」と言われ、c7c7さんが実装してくださいましたがサンプルが合わず時間切れ

 結果は6完でした 圧倒的無力感

 コンテスト後にc7c7さんとnomiさんとABCの話をしたりしていました c7c7さんに「AOJ-ICPCを埋めて実装力を付けましょう」といわれ、やる気をホテルに持ち帰りました

 

2日目

fuu32さんとfuncsrさんとぼくのチームで参加させていただくことになりました。まぁレート順的にぼくはAをやることになりました

コンテストが始まって、ぼくはまずAを通しました

fuu32さんとぼくでBを一緒に考察していましたがかなり苦戦しました

その間に圧倒的速度でfuncsrさんがGとHを通していました すごすぎる...

funcsrさんがアドバイスを下さり、fuu32さんが実装してBを通しました。

次にfuncsrさんがすでにC、Eの考察を済ませていて、まずCの実装をぼく、次にEの実装をfuu32さんが担当しました。実装が重かったですがfuncsrさんに何度も助けられながらなんとかCが通りました

fuu32さんが実装をしている間、次にDの実装をお願いできないかとfuncsrさんに言われ、軽く紙コーディングをしたりFを眺めてなんじゃこりゃ...と言っていました

fuu32さんがEの実装に苦しんでいたのでその間Dの実装を始めました。面積を場合分けして求めてDPだと言われそのように実装しましたがずっとバグらせて苦しみました。

ずっとバグに苦しんでいるとコンテストが終了しました...この日は本当に辛かった......

funcsrさんが凄すぎました。ぼくなんもしてないやん...

 

3日目

 フェリンさんとrollmanさんとチームを組ませていただくことになりました

 

いつものようにぼくがAをやりはじめましたがWAを生やしました。フェリンさんがミスを指摘してくださりAC。実装力の無さを痛感しました...

続いてフェリンさんに「Cは約数と素因数を求めて欲しいです」と言われ、助けられながら通しました その後rollmanさんがBを通しました

その後はフェリンさんがDを考察し、rollmanさんが実装されてました

Eをフェリンさんと考えましたが、ほぼフェリンさんが考察して、フェリンさんが「ロリハか...?」と言い始めたあたりから知らない単語が右から左へと流れていきました、後で調べました

rollmanさんがDを実装し通したあと、フェリンさんがEの考察を終わらせ残り15分で実装しようとされていましたがタイムアップ

コンテスト後はフェリンさんに「Aはこうするといいと思いますよ」と教わったり、ローリングハッシュについて調べたりしていました

あとset_intersection、set_union初めて知りました...

 

感想

皆さんレベル高すぎる、もう今ははやく精進したい欲で満ち溢れています

タイピング速度、考察の速さ、何もかもが尊敬でした(語彙力)

レートがめちゃくちゃ高い方々の手元を見ることができる機会は早々ないと思うので、東京からわざわざ一人ぼっちで来たかいがあったと強く思っています。競プロ初心者のぼくでも参加できるようにスムーズかつ柔軟に対応してくださった運営の方々には感謝の気持ちでいっぱいです。今後の精進の指針にもなったし、コミュ障なりにチームの方々と交流できてとても楽しかったです。

唯一の後悔は、懇親会に参加しなかったことです。(やるべき作業が溜まっていたため...やむをえず...)

 

来年はレートをばちこり上げてまた参加したいです!!!!!!

 

さいごに

 

 にぼ二郎、最高。