HIR180's diary

ICPC World Finals 2022 を集大成に

ICPC World Finals Dhaka 参加記

気付いたら帰国してから丸一週間が経ってしまいました (そ、そんな...)

当日まで
  • 普通に病院実習 (今回は形成外科) に丸被りで困ってしまったのですが、当科の先生方にご配慮頂き、まず参加できることになりました (8月くらい)
  • 一方、9月頃まで競プロの練習が圧倒的に不足しており、力が落ちすぎてヤバいということに気付き、HELP!に (どうして...) (マッチングが悪いよ~)
  • 9月末から週2+ペースでチーム練が始まり、徐々に勘を取り戻しつつチーム性能を向上させていき、直前には大分仕上がった気分に。
  • 基本的な立ち回りはmaroon: 何でもやる、幾何担当 / yutaka: 考察難や数学系など担当 / hir: 面倒枠、写経担当 という感じに落ち着きました。
Day1 (11/6)

前日なかなか荷造りが終わらず、2時間睡眠で成田空港へ。

 

abemaで全日本大学駅伝を見ながら眠気覚まししてました。駒澤強すぎてウケますね~

この時点でbatonさんと会い、少し雑談しました。batonさんは貴重なOI時代からの同期なので、急遽東工大のWF参加が決まって会うことができ、嬉しいね。

過年度のWFの過去問を眺めたり、ライブラリの位置を覚えたり、寝たりしながら飛行機を乗り継ぎ、夜中にダッカ着。

バングラデシュ、道路に信号がなく、車線もあまり意味を成しておらず、また教習所の教官が見たら気絶しそうなレベルの車間距離で全てが動いており、更に各々の車が挨拶代わりにクラクションを鳴らすので本当に凄いことになっていました (tatyamさんのツイートをお借りしています)

 

ホテルに日付変わってから到着。抗原検査して、色々準備してから寝ました。

Day2 (11/7)

この日はteam registrationがあり、本番使うTRD (A4 25ページのライブラリ) と辞書などを提出しました。その他は、前日の大移動の疲れが全然取れておらず、ずっと座って寝てた記憶しか残っていません...

 

WF、色々予定が詰まっていて意外と忙しないなという印象になったが、実は後の日はスカスカでした。

↑これ寝てて見逃しており、かなしい

Day3 (11/8)

この日はicpc challengeがあったんですが、諸事情あって会場に遅れて着き、既に始まっていたので参加せず、勝手にリハーサルもどきをやっていました。

workstation

その後opening ceremonyがあり、この日はこれで終了。

帰りは信じられないほどの渋滞に巻き込まれながらホテルに戻り、夕飯。

おいしい

この後の検査が本番への参加可否を決めるやつで、本当にビビっていて結果が出るまで寝つけなかったが、無事に陰性となり、安心。

 

Day4 (11/9)

この日はリハーサルでした。

ターミナルから提出できるの便利~ とか 普通に問題面倒なの多くて草 とか言いながら一通り解き終え、その後は自分は使う可能性が高そうなライブラリの写経をしました。

 

写経にまつわる裏話として、"粘着物を使ってモニターにライブラリの紙を貼り付ければ、視線移動が減り写経が高速化出来る" という気付きと、東工大チームから教えて頂いた "ランチボックスにあるポテチの缶の側面に剥がしやすいシールが貼ってある" という気付きを組み合わせることで圧倒的に効率が良くなり、もう完全に草でした (物が足りないと創意工夫が捗って、面白いですね)

 

夕飯を18時に食べ、部屋に帰り、引き続き写経練習としてmodint + ntt を何回か書いて満足して寝ました。寝たとはいいつつ何度か中途覚醒はしました。

 

Day5 (11/10)

いよいよ待ちに待った本番。

6時半に目が醒め、少しベッドでスマホを弄ってから起きました。

この時点で出発は8:25だと思っていたので、その後シャワーを浴び、のんびり朝食会場に行くと、急ぐように伝えられ、かなり???という気持ちになっていたのですが、
よくスケジュールを見ると8:10が最終便と書かれており、勘違いしてたなと思いきや、なんと当日7:40に変更になっていたとのこと。どういうことやねん。

 

 

バスの中では問題文が長くて実装も怠いが別に難しくはない、しかしあまり解かれないタイプの問題 (WF'15 MのWindow Managerという問題からWindowをManageする枠 とずっと呼んでいました) を確実に一撃で殺す機運を高めながら、ライブラリの位置を最終確認し、お気に入りのプレイリストを聴きながら気分を高めていました。

 

会場に移動し、色々雑談し待っていると、突然時計が残り5分から1分に進められ、焦る。リハーサルでもこれやってたし来年は心の準備をした方が良さそう。

 

(ここからコンテスト)

問題: https://icpc.global/worldfinals/problems/icpc2021.pdf

いつも通り大きく3分割して、順番にmaroon/hir/yutakaで読んでいく。

パッと見、E: よくわからんけど難しそうだし、多分自分の問題じゃない F: 笑 G: 典型だろうけど最初じゃないな~ と言う感じで、ようやくHが簡単枠。

Hは簡単枠というか既出 (?笑) (F - Bracket Sequencing) だが、少し自信がないので確認を取って、実装。このレベルの問題ですら初めてのオンサイトWFの1問目で書くと少し混乱するし提出する時心臓バクバクでびっくりした。通ってガッツポーズ (草)

次にGを読み、まあ典型なんだけどすぐ解き方が思い出せない (カス) が、とりあえず昨日まで散々練習したmodint+ntt写経の出番はありそうだなと思う。ただ序盤ではなさそう。Eは放置、Fはmaroon行き。

そうこうしている内に、Cの解法を受け取って実装することになり、簡単だけどオーバーフローとかコーナーケースが少し怖い感じだったので、落ち着いて詰めて、Jの後に通す。ここで実装やるだけ枠としてLを受け取り、少し迷走するもまあ出来るなという気持ちになる。その後にAを見て、最大の方がいまいち良く分からないな~って思っているとFが通り、Gも例の写経をすればいけると言われたので、Lより先にやることに。

↑のテクニックを駆使 & 練習の成果が出て写経は上手く行き、その後はmaroonが実は制約にミスがあったことなど無関係にすんなりACしてくれて、後から振り返るとここまではかなりいいムーブだった感じがする。(この時点では1位だった) (FAを確信したらカメラに向かってポーズを取ろうという話をしていたので、是非アーカイブを見てください)

ここから自分はAの方針を貰って、実装し通し、またBの後にLを詰めて書いた。少し実装と認識にズレがあり1ペナ吐いてしまい悔しかったが、assertに引っかかったお陰で原因はすんなり見つかり良かった。

この時点でDEIKが残っていて、Dの実装に着手していた一方で、自分はEを一応読んで考えたり、Iの手伝いをしたりして、Iが通った後はWAしてたDのデバッグ、またKもWAした後はKのデバッグをしようとしていたが、上手くいかずそのまま終了。

 

凍結後の順位表

終了直後はD, Kをどちらも落としてしまって落胆しており、また下手したら金すら怪しい?と思ったがそれは後から冷静に↑を見て多分大丈夫であることは気づきました。

その後の会話でPekingが10完、Zurichが9完したことを本人たちから聞き、自分たちのペナは圧倒的に少ない (MIT除く) ので、Seoul NUが10完するかどうかで3/4位が決まる、というのが唯一の本質ポイントであることを理解。

会場を出た後は別の部屋で食事を取りながら東工や京大とコンテストの感想を軽く喋ったり、写真を撮られたり、引き続きDKのデバッグをしたりしてました。

 

 

閉会式は、本当に各種スピーチの類が多くて長くてうんざりし始めたところでyes/noがようやく始まり、しかしyes/noもワクワクするのは最後の1~2割とかなので割と虚無で、そこまでは近くのLatin Americaのチームたちがハイテンションで楽しんでいるのを見て楽しんでいました。

 

銅・銀あたりでは、HSEが冷えてて予想大外れだったのと、Carnegie Mellon U, École Normale Supérieure de Paris とか ICPCメダル界隈では珍しい学校が出てきて面白かった。DEK以外の9問は全部人間向けだと思ったが、実装がそこそこある問題が多く5時間で全て揃えられれば銀が取れる、という結果になっており、実装練習は大事...

 

さて、争点のSeoulの完数は9で、Asia Pacific Championを死守し日本勢最高順位にも並び、とりあえず本当の最低限はクリアできたかなと個人的には少し安心しました。

 

 

MITはKも当然通しており、圧倒的すぎた。slime matthew jerry orz

ただ11完して並び立つことは当然出来るチームだったと思うので、圧勝させてしまったことに少し後悔はあります。

終結

閉会式はWorld Championが表彰されるとすんなり終わり、また夕食の会場に戻っていきましたが、気分が落ち込んでいてあまり交流のモチベが湧かず、割とすぐホテルに帰りました。(狭義WFはこれで終了です)

 

ホテルに帰った後は、スーツケースに全てを押し込み、ゆっくり寝ました。

 

Day6 (11/11)

ホテルでの最後の食事に行き、荷造りし、チェックアウト。

その直後に9年前に知り合ったバングラデシュの友人と直接会う機会があり、貴重な経験が出来ました (バングラデシュのお土産をたくさん頂きました) (日本にも来て欲しいね)

 

その後はチーム+コーチ 4人でバスの時間までの時間潰しとして、周囲を散策しました↓

ショッピングモール

 

各フロアに小さい店舗が密集してる感じで、基本衣類とか電子機器とかが売られていますが、宝石とか金のアクセサリー?的な店ばっかりのフロアがあり海外を感じました↓

VENUS DIAMOND COLLECTION (カラフル)

車と人の距離が近いアットホームな職場です!

ケーブルの絡まり方えぐない?

おいしいダッカ

この後夕方に空港へバスで移動し、飛行機まで約6時間ほど暇を持て余していたので、henoさんに現地通貨を頂いてスーツケースを縛るテープを買ったり、売店を散策したり、夕飯を食べたりしました。

コンテストまでは集中したかった&コロナのこともあり、またコンテスト直後は落胆していたので、この時間に初めてまともに海外チームと交流できた気がします。

23:55の便でシンガポールへ。

Day7 (11/12)

シンガポールへの便であまり寝られなかったので、空港のソファーで大爆睡し、トランジット8時間を消し飛ばしました。その後お土産を買って、日本への便の中ではあまり眠くなかったが、なんとか寝て暇を潰し、ついに帰国。

飛行機自体の遅延 + 荷物回収に時間がかかり、終電バトルが開幕して慌ただしく解散。

羽田からだったので自分は割とすぐ家に着き、WFは完全に終わりました。

まとめ

最後に、今回参加して感じた、ICPC WFでのtipsを (来年の自分のためにも) まとめておきます: 

  • 寒さ: 特に1年中暑い国では、逆に室内はクソ寒いことが多く、体が冷えると当然指先がかじかんでタイピングに支障をきたします。そこで、防寒対策が必要なのですが、コンテスト当日は支給されたTシャツを外側に身に着けることを強制されるので、薄手の長袖の服を用意するのが良いです。

  • 声かけ: 本番、特に最終盤はテンパりすぎていつも出来ることが出来なくなります。REが取れないならassertを全部消したか? とか 幾何でハマっているならepsを変えたか?とか (今回のDはepsを1e-9から1e-10にしたらACしたと後から聞きました) 、そういう典型的な声かけ集をチーム練の時からまとめて、直前に確認するとかしておけば、と個人的に思いました。

  • ライブラリ写経: 上記の通り、シールを探す旅に出て、見つかれば、勝ちます。(かなりしょうもない話だと思うんですが、こういう工夫がメンタル面でプラスに働き、実際に写経も捗ったので、やらない手はないです)

  • 荷物: 鞄やスーツケースの容量をかなり開けておかないと、大量に配られる各種お土産が入らない (いくつか向こうに置いてきました) だけでなく、表彰式で大量に重くかさばるプレートを貰ったり、ICPC challengeでPCを貰ったり、それこそWorld Championのトロフィーを貰ったりした時にとても困ることになるので、コンテストとは無関係ですが、注意しましょう。

  • その他: ある程度交流を楽しみたいなら英語をやっておくべき。 (自戒) あとどこの大学にどんな人がいるかを下調べしておくと観察が捗るので、おすすめです。

 

次回のエジプトのWFには再び UT a.k.a Isで臨みますが、その時には自分は研修医になっている (なっていてくれ) し、他2人も本業のウェイトが増していくと思うので、どの程度練習が積めるか不明ですが、悔いなく終われるようにはしたいなと思っています。また、次回はコンテストだけでなく、年に一度のお祭りということで、楽しむ気持ちも持ち合わせて行くつもりです。

とりあえず初手として、向こうで師匠とhenoさんにCFに復帰すると宣言したので、無理なく出られるdiv1には参加していくつもりです。

 

本当の最後に、今回のチームは間違いなく世界一になれるポテンシャルがあったと信じていて、結果としては届きませんでしたが、一番アツいポジションでWorld Championという大きな夢を見せてくれたチームメイト2人に感謝してもしきれないです。

また、2020年秋ごろから2年間、___ KING ___を応援して頂いた皆様、ありがとうございました。

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 高垣楓さん誕生日おめでとうございます!