競技プログラミング
ICPC2020参加記
公開日:
2022/05/25
ICPC2020参加記

ICPC2020アジア地区予選にチーム名Planet Samarnで参加し,19位でした.

ICPCとは

新歓用記事ということで簡単なICPCの説明を.

International Collegiate Programming Contestの略で,大学対抗の国際的なプログラミングコンテストのことです.形式はAtCoderに近く,短めの問題を何個も解いて解けた問題の数・時間を競います.

AtCoderとの違いは

  • 3人1組のチーム戦
  • 例年は使えるPC1台で実装と考察を交代しながら問題を解く
  • 今年はコロナの関係で1人1台PC使用可能
  • ペナルティは各問題の累積
  • 実装が重い問題が多い
  • 本選は問題文が英語

って感じかな.年1回のイベントということで,野球でいうところの甲子園みたいな存在となっています.

ICPC布教

この記事の目的はICPCはたのしいぞ〜来年出ようぜ〜って話です.そのためにICPCの面白いところを語ります.

ICPCはAtCoderと違いチーム戦なので,バグらせた時に他の人と一緒にデバッグすることができます.いわゆるペア・プログラミングってやつです.その分他の人が読めるコードを書く必要があり,キレイなコードを書く必要があります.これはけっこう大事です.ペア・プログラミング,普段やることがあんまり無いですが普通に面白いです.

あとはありきたりな話ですが,アルゴリズムやデータ構造の知識やコーディング力が身につくことですかね.

こういう能力が身につきます〜って布教するのもいいのですが,純粋に切磋琢磨練習して大会に挑む!チームワークや個人の力で高みを目指す!ってのはスポーツと近いものがあって楽しいです.しかも,運動神経が無くてもどうにかなります.最高ですね!青春です.

ICPC2020備忘録

駄文です.読む価値は多分無いです.

チームメイトの紹介

  • pngn
    • この記事を書いている人
    • 最近basebreadにハマってる
  • ハニワくん
    • 誰も読めないコードをよく書いてる
    • 貪欲法を通すのが上手い
  • hanaさん
    • 英語が強い(というか他のメンバが英弱)
    • 簡単な問題を安定して通してるイメージ

コンテスト前

深夜テンションでICPC紹介文を書いたらちょっとだけ浮きました.

黒歴史になりそう

打ち合わせでA問題をhanaさん,B問題をハニワくんが解いて僕はC以降の問題を適当に解く作戦にしました.

コンテスト前日

早寝した

コンテスト中

開始と同時にC問題を開く.問題文の英語が理解出来ない.高校時代ちゃんと英語勉強しなかった事を後悔してD問題に移る.他の2人が実装重い〜って言ってた

D問題,3色を満たす周囲の長さ最小の長方形を求める問題.問題はシンプルだけど方針がすぐ立たない.困ったのでE問題に移る.

E問題,多角形の辺の長さが与えられるので外接する円の最大を求める問題.半径を決めると中心角が一意に定まるので和が2πかを判定すればいいや〜にぶたん!って書いたらサンプルが通らなかった.

円の中心が内部に無い時は一番長い辺の中心角と他が一致した場合を忘れていましたおよよ.その後にぶたんの上限の値を小さくしすぎてWAをいただく

気づいたらAとBとJが通っていた.人が解いているGにいく.(連結成分数)-1<=(引ける線の数)が必要条件だなーって思った.連結数はどの非連結なものを結んでも-1に変わらないし,多分十分条件だなーって思ったので実装した(完璧な証明はしてないですごめんなさい).多分再帰的に帰納法で考えると証明できそう.非連結な数はUnion Findで両側から調べればOK

ハニワくんがHを解いていたのでIに行く.DPだなって思ってから添え字をバグらせてかなり辛かった.2n個要素の配列を用意しなきゃいけないのにn個の要素しか確保していなくてでRE出しまくった.というか,そのバグを修正したと思っていたのに1箇所直って無くて,しかもREじゃなくて何故かWAになったので気付くのに時間がかかった.反省

結果

ABEGIJの6完19位でした!

20位以内に入ることが目標だったので達成できてよかったです.

しかし,H問題は解きたかったし,時間があればもしかしたらC問題も通せたかもしれないと考えるとバグらせていた時間が悔やまれますね.チーム戦略としてもう少し分担を上手く出来たら良かったなと思いました.それと圧倒的に英語力が足りてないので勉強しないといけないなと思いました.上位陣と比較すると,実装の速度がかなり遅いことを痛感したので精進しないと...来年までに橙コーダーになって橙安定させることを目標にします.

いかがでしたか?

言ってみたかっただけです.おしまい

loading...