HIR180's diary

ICPC World Final 2020 を目標に競技プログラミングをしています

ICPC 国内予選 2021 参加記

チーム UT a.k.a Is (yutaka1999, yokozuna57, HIR180) で参加して、優勝しました。

f:id:Hiro180:20211106145401p:plain

 

ICPCは完全に引退したつもりでいましたがWF2020の特例措置で生き返ったので、個人としては5回目 (正真正銘のラスト) 、チームとしては3回目 (2018, 2019, 2021) の出場となりました。

 

大まかな戦術としては、今年は他チームが強いことが分かっていたので、去年みたいにエンタメ要素はなしで普通に前からやることにしました。

 

当日

6:30に起床 (え?) 、大学行ってから家に戻り、昼食&昼寝した。

直前まで打ち合わせしてなかったのでD以降の割り振りはad hocに決めることとし、コンテスト開始。

 

A-yokozuna, B-HIR, C-yutakaで始めたが、Cにこの世の終わりみたいな図が書いてあるのを見てB, Cをswap。

 

Cは解法自体はぱっと出るが、全方位木DPに苦手意識がありCでこんな問題出るか??と疑念を抱いて少し考え直す。が冷静にそこまで大変じゃないので黙って実装することにする。

通常の木DPまで書いた段階で2乗解を回し始めたが全然終わらず、結局全方位書いて通した。かなり手間取ったけどペナ吐かなくて良かった。

 

この時点でもうABDが終わっていて、Eももう師匠が実装に入っているとのことだったので、yokozunaに合流してFを考える。

その後すぐyokozunaが解法を思いつき、僕が実装した。かなり手間取り、また強連結にするパートで少し怪しい部分があったが、国内だし実行出来れば正義!wって言ってassertてんこ盛りにしてゴリ押し実装したら無事一発で通った。OK。

 

その後はHを見て、反転してn=4の場合が解ければ解けるね~という話をしたが当然間に合わないので諦め、Gと格闘してる師匠を応援してコンテスト終了。

 

感想

G,Hを振り返ると7完するのは相当調子良くないと無理そうでしたが、結局6完速度勝負で勝てたので良かったと思います。4年弱前の結成時からチーム性能の圧倒的な向上を感じました。

個人としてはC, Fどちらも実装でかなりタイムロスしたので、実装練習しないとダメだなと思いますが、とりあえず去年のDみたいに炎上はしなかったのでよしとします。

横浜は勿論優勝してWFの権利を勝ち取るのもそうですが、久々にオンサイトでコンテストやりたい気持ちが強いのでなんとか現地開催されるよう祈っています。

 

ここまで読んでいただきありがとうございました。

 

ICPC アジア地区予選 横浜大会 2020 参加記

チーム___ KING ___ (yutaka1999, maroonrk, HIR180) で参加して、国内予選に続き優勝しました。

f:id:Hiro180:20210318152343p:plain

順位表

国内予選の時はmaroonを幾何だけに充てることになりましたが、アジア地区では普通に3並列でバリバリ解いていくことにしました。

1ヶ月くらい前からcodeforcesのgymなどで練習を数回やりました。

模擬地区は特に問題なく2.5時間で全完できたので良かったですが、本番は激ムズ (ex. 去年のセット) だと思っていたので、当日は結構冷や冷やしていました。

 

本番

A: HIR, B: maroon, C以降読み: yutaka で始めました。

Aは少し手間取ったと思いましたが、FAが取れて良かったです。

Bもすぐ通り、E: maroon、G: HIR、H: yutaka で30分過ぎに5完まで行きました。

その後、師匠がJK、僕がIを通し、それぞれD, Cに着手しだしたころに、

maroonが自信満々な感じでFに3乗解を投げると言ったので、皆でjudgeを眺め、かなり時間が掛かったものの通ったので、してやったりという感じで盛り上がりました。

この後は、僕は右手法を勘違いしていてmaroonに助けを求めたり、バグったりしましたが何とかCを通し、師匠とmaroonのD速度バトルを応援していました。

バトルはmaroonの勝利ということで、3時間過ぎでコンテストが終わりました。

f:id:Hiro180:20210318154546p:plain

domjudgeのアカウントを無効化されるというレアイベントが発生しました

終わった後は恒例の反省会をし、それでも暇だったんですが、雑談したり、寝たりして時間を潰しました。

 

表彰式は他の上位チームの人々の話を生の声で聞けて面白かったです。

懇親はあまり渾身ではなかった (このネタ何回目?) ですが、gather townのシステムは面白くてすげ~ってなってました。

 

感想

実は競技プログラミングで金メダルを貰うのが初めてなので密かに喜んでいます。

あと全体FAも狙っていたので何とか取れて嬉しかったです。基本的には序盤力を発揮するのが大事な仕事だと思っているので、今後も宇宙人たちをサポートする人間枠として頑張っていきます。

ICPCは (いつやるか未定ですが) World Final 2020, 2021を残してもう参加することは出来なくなってしまいましたが、今後は何らかの形でお手伝いが出来たら良いな、と思っています。

 

最後に、今回は大変な社会情勢の中新しい形式の大会を準備されるということで、多くの障壁があったと思いますが、このような素晴らしい機会を提供頂き本当に感謝しています。

個人的に、ICPCは大学以降競技プログラミングを続ける一番大きなモチベーションとなっていたので、現役生活の最後にWorld Finalで好成績を残すことを通じて、多くの方に競技プログラミングの魅力、楽しさをお伝え出来たら良いな、と思っています。

今後も他のことと平行しつつ頑張っていきますので、是非World Finalに出場する際には応援よろしくお願いします。

ICPC 国内予選 2020 参加記

チーム___ KING ___ (yutaka1999, maroonrk, HIR180) で参加して、優勝しました。

f:id:Hiro180:20201107003558p:plain

全完! (3年ぶり2回目)

 

メンバー紹介 (国内予選2020ver)

yutaka... メインコーダー。基本的に何でもできる。

maroon... 何でもできるが、現状唯一の幾何担当なので、後ろに露骨に時間がかかりそうな問題 (主に幾何) があった場合、まずそれを倒す。 

HIR... 他2人を補う形で、主に面倒な問題を担当する。

 

やっぱり全完を目指したいという共通の意思があったのでこのような分割になり、

実際に模擬国内でmaroon幾何ワンポイントがハマって全完できたので本番もこの形になりました。

(僕はと言うとサイコロで炎上してチームメイトを冷や冷やさせていました -19980412点)

 

 

本番

皆自宅から参加。

最初見てHIR: A, yutaka: B, maroon:Hからスタートする。

次に僕がCを解き、

Dが構文解析の見た目をしているので、師匠のEと交換して取り組む。

Dの中身は普通の問題だったが、計算量見積もりが甘すぎて実行に無限時間掛かるコードになってしまったので、とりあえず合っていると信じて既にEFを終えた師匠とGを考える。

Dを何とか通し、程なくGの方針が立ち、2人でフローのグラフ作りと、辞書順最大のための微調整を分担することにする。

割と時間がかかってしまったが、コンパイルが通った後はすんなりACできてほっとする。

最後に、maroonがひたすらHと格闘しているのを応援してたが、残り8分辺りで突然1個目のケースが通った、と言ったのでかなり盛り上がる。

それから間もなくして、全部の問題が緑に光って勝利を確信。やったぜ。

f:id:Hiro180:20201107005310p:plain

これすき

最後に一通り問題を振り返って、国内予選は終わりました。

 

 

感想

個人的なパフォーマンスは良くなかった (HELP!!) のでチームメイトにひたすら感謝です...。

来年3月の横浜までにまたコンディション作って頑張りたい。予定では6月にUT a.k.a Isで臨むWFもあるしね。

ここまで読んで頂き、ありがとうございました。

 

 

 

 

追記

進級が掛かったCBTが2週間後に迫ってるので熱烈QB精進しないとヤバくて困っています 誰か助けてください

TopCoder Algorithm Target になりました

この前のTCO 2020 Round4のレート更新でTopCoder Algorithm Targetになりました

 

f:id:Hiro180:20200915202949p:plain

このマークが自分の名前の左にある事への違和感が凄い...

 

f:id:Hiro180:20200915195824p:plain

灰からTargetになるのは結構珍しい気がする?

 

f:id:Hiro180:20200915200121j:plain

ランキング17位 (TCO2020 R4直後)

 

2012年9月に競技プログラミングを始めたときから最終的に到達できたらいいな、くらいの気持ちでTargetになりたいという思いを持っていましたが、本当に達成できるとは思いませんでした。

僕が競技プログラミングに触れ始めたころはCFは頻繁に遅延 & 鯖落ちする黎明期のサイトで、(直近のラウンドが#670ですが、僕が初参加したのは#139) AtCoderにはそもそもレーティング制度がなく、SRM一強の時代でした。 (今では考えられないですね....)

当時は (JOIも目標にしていましたが、) SRMで赤くなることを目指して頑張っていました。2014年6月に最初に赤くなって、このまま順調に上がっていくかな?と夢を見ていましたが、実際は受験勉強のブランク等々で滅茶苦茶なことになっています (↑のグラフ参照.)

大学に入って、夏まではバイトや部活を頑張っていましたが、もう一度競プロに打ち込みたいと思って秋からはかなり集中して精進する日々を過ごしました (↑のグラフを見ても2017-18の上り幅が凄い)
最近ではICPC WFが延期になってしまい、また上位との壁を感じることが多く、大学も忙しくなってきてしまったので昔ほど時間を取れなくなりましたが、その中でなんとか這い上がって目標を達成できたのはとても幸福なことでした。

スピード + 確実性の比重が重いSRMが比較的得意と自己評価していますが、実際最近はある程度自信を持って出したものはほぼ通っていたので、(R4の既出も含め) かなり上ブレしてる感じです。今後は落ちることも当然あると思いますが、落ちても戻ってこられるようにもう少し地力を上げていきたいです。(あと1年?くらいロスタイムがあるので、まだ伸びると信じています)

 

最後に、後日オンラインでTCO Finalに参加するので、出ただけで終わらないように、見せ場が作れるようになんとか食らいついていきたいです。

TopCoder Open Round 4

試験に追われていたら2日も経ってしまいました。

TCOのprefinalのラウンドはサボったり出られなかったりで2年ぶり2回目です

 

Easy

少し考える、幅を決めて端から埋めていく感じでいいんじゃない (思考停止)

書いてサンプルを通して出す、ここで冷静になって8 8 6 54とかで落ちることに気づく (なんで?)

右上から左下への折れ線で区切れるような形にはなることが示せるので、素直にDPして復元する (が滅茶苦茶バグる)

 

Hard

基本前から解いていくんですが、出遅れた & 解いてる人が多い & 高い点の人が多いのを見てHard開けを決意

この形の遷移見たことあるな... と気づいて

https://codeforces.com/contest/325/problem/E を思い出して、通す (既出判定大丈夫ですか?) (とはいえ7年前のCF・3年前のPetrozavodskで既出と言われても気づけるtesterは多くなさそう....) (この回は実際に参加してたので覚えてた)

 

Med

これ通せば通過ワンチャンあるなと思って開くと、割とすぐ方針が見えたので頑張って実装する (桁数と違う場所と桁の値を決め打てばとても単純な桁DPになる)

ぎりぎりでサンプル全部通ってガッツポーズする、出す

 

Challenge

特に考えてなかったので全然落とせない、落とせそうなのを写経するも全部通って悲しかった

 

 

全部通ってooo +0/-0 3位、TCO Final進出2888 -> 3008 (+120) でTopCoder Algorithm Target になりました。

f:id:Hiro180:20200908225416p:plain

ICPC延期になってしまったのと大学の試験がやばいのでモチベが上がらなかったけど、思いがけない形で長年の夢が叶ったので何だか不思議な気持ちです。

とりあえずTCO Finalと来週のFHC R3に向けてまた頑張ります。

 

(ポエム編に続く)

 

 

東京海上日動 プログラミングコンテスト2020

https://atcoder.jp/contests/tokiomarine2020

↑tokyoじゃなくてtokioなんですね

 

A

B

注意力が本質かな~やっぱ

C

0, 0 \cdots, 0から始めて何が起きるかに思いを馳せると思考要素が無いことに気づくことができる

D

木上のナップサック問題とかあったな~と思い出しながら考える、がとてもじゃないがdp的な方針では解けない

普通に半分全列挙だな~という気持ちになるが、ソートいるし困るな~

冷静になると上半分の候補は少ないから、そこだけ計算結果を持ってやればいいのでは?と気づく 2^A未満を前計算するなら雑に見積もってO(4^A \log + Q N \log / 2^A)

A=10で組んでテストすると普通に間に合いそうなので出すと通る

E

適切な前処理をすればS=0, T=2^k-1の問題になることはすぐわかる

この見た目で包除しないわけないので、どうやるかを考えると、bitごとに全部等しい / そうではない に分けるのが筋が良さそうとわかる

包除の計算で何が必要かと言うと、b_1,\cdots,b_k 番目のbitに注目してそれがc_1,\cdots,c_kになるような個数を求め、適切な場合の数を掛ければよい

b, cを全部試すと3^{18}がついて終わるが、少し考えるとbを決め打ってそのbitだけ抜き出した値ごとに分類すれば十分高速に解ける

F

対称性を使って左の辺から1点、上下の辺から1点ずつ取るパターンに帰着する

色々考えると、上下の点を結ぶ辺の傾きが同じであれば、内部の点の個数は右に行くほど増加することがわかる。

(理由: 1動かすと面積は\dfrac{H}{2}増えるので、ピックの定理より周上の点がHより多く増えなければ減少することはないが、そうはなりません

(もしそんなことがあったら、直感的に嫌な気分になります。))

ここからは、コードテスト上で熱烈枝狩り+定数倍改善で頑張る。何が最大ケースかわかりにくいが、この方針だと1000 100000 100000とかが遅かった。

 

なんか久しぶりに順調に問題が解けて満足したので競プロ最高~~の気持ちになれて良かったです

 

p.s. https://atcoder.jp/contests/tokiomarine2020/submissions/14247904 高垣楓さん誕生日おめでとうございます!

NOMURA プログラミングコンテスト 2020

https://atcoder.jp/contests/nomura2020

5月の個人コンテストはこれが最初で最後となりました (?????)

 

A,B

C

アップダウンとボトムアップを組み合わせるとそれっぽい貪欲になることはわかる

「正しそうだけど示すのむずいな~」と「600点ってこんなに単純でいいの??」の間で揺れて時間が経ってしまう

F

書き換えは1か所だと思っていたので 違う箇所が1つ以下 or 2つの0/1が頭にくる or 違う箇所が2つで0/1 1/0 という条件になり、全く解けない

よく読むと回数は任意なので、1/0があったらそれ以降は等しい だけに言い換えられる

等しくなる部分を圧縮しながらDPすれば良くて、式を整理すると2乗

D

いろいろ試すとループの個数に着目すると解けることが分かる むずいね

(連結成分に注目したり木の数え上げに帰着しようとしたりしませんか?僕はしました)

感想

日本人7位、DF数え上げなのに滅茶苦茶手間取ってしまって辛かったが、問題は面白かったです

6月はちょっとずつ練習してこのブログも更新していきたいと思います