heno239’s blog

まとめたいことをまとめる

ICPC2021国内予選 参加記

  • はじめに

皆さんこんにちは、heno239です。

1年に1回の大学対抗プログラミングコンテスト、ICPCにチームHeno Worldで参加しました。

チームメンバーは moririn2528君と yamunaku君で、去年と同じメンバーでの参加になります。

ICPCへの参加は、今年World Finalまで進出した場合は今回がラスト、そうでない場合は来年がラストです。

どちらにせよあと2回以下しか参加できなかったので、優勝目指して頑張っていました。

  • コンテスト前

コンテストにはオンラインで参加しました。

当日の朝にリハーサルを触ったら、手元の環境が突然死していたことが発覚したので、慌てて修復しました。

昼にカツ(カレー(うどん))を食べ、コンテスト前にお菓子を用意して、用意周到でいざコンテストへ。

  • コンテスト中の動き

A,Bをチームメイトの2人に任せ、C問題を見る

C問題を見て、「構文解析して全方位木DPでできるけど、本当にC問題にそんなもの置かれるのか・・・？誤読してそう」とかなり悩んだ末、結局それを書くことに

僕がC問題を通すころにはA,B,D,Eが通っていました(草)(チームメイトが強い)

 

F問題、G問題、H問題を見て、

F:考えればできそう

G:時間かければ絶対できる

H:触りたくないかな・・・

となり、

  1. おそらくどこかしらのチームが7完するだろう
  2. 自分ひとりでFG両方を解くのは無理だろう

と読んで、チームメイトがFを通してくれることに賭けて自分はGに行く。

 

終了30分前ぐらいにFもGもコードが完成するも、両方WAがとれず、そのままコンテストが終了。

 

  • コンテスト後

結果、順位は4位になりました。

 

Gは結局コンテスト終了1時間後ぐらいに通る形になりました(手元の、小さいケースを全探索する解法と答えが一致しているから多分合ってるはず・・・)

結果論にはなりますが、結局7完するチームは現れなかったので、Gに行く必要はなかったですね。

結局Gに2時間以上使って通せなかったのがとても悔しいです。

 

  • 今後の抱負

1位をとれなかったとはいえ、国内予選を通過できたことには変わりないので、(本番自分が全然活躍できなかったこともあって)チームメイトに感謝しています。

 

次のアジア大会はオンラインになるかオフラインになるか分からないですが、どちらにせよリベンジで優勝とれるように頑張りたいです。

 

  • 応援してくださった方々へ

応援ありがとうございました。期待に沿えない結果になってしまい、申し訳なさと悲しさを感じています。

応援のおかげで次回のアジア大会へのモチベが高まっているのを感じているので、もしよかったらこれからも応援してもらえると嬉しいです！

 

  • おまけ

WAになって踊ろう

💃💃💃💃💃💃💃

 

 

KUPC2021参加記 運営視点

  • はじめに

10月31日にAtCoder上にて

京都大学プログラミングコンテスト 2021

が開催されました。(https://atcoder.jp/contests/kupc2021 )

私は一昨年、去年に引き続き運営側として参加し、コンテストの準備をしました。

今回は今までの中でも自分が一番関わったコンテストになりました。

 

  • 運営について

3月下旬から問題の選定をはじめ、7月末には問題案が決まり、8~10月で問題の準備をしました。

問題の選定は私が主導して行いました。メンバーの皆さんが次々と問題を投げてくださったので、あまり問題案不足に悩むことなく、問題の選定を終えることができました。

 

コンテスト開催にあたって、AtCoder様にはたくさんご協力をいただきました。ここに多大なる感謝を申し上げます。

 

  • 問題について

 

  • A問題

はじめは T の倍数の撤去という制約がなく、各 i について[S_i,T_i]に設置されるので、"1度だけ"京都大学を訪れ、見れる立て看板の数を最大化してください、という問題でした。

atcoder.jp

↑上位互換です。本当にありがとうございました。

 

次案として「全ての看板を見ないといけないが、そのときに訪れる必要のある回数の最小値」となりました。(要するに、いまのA問題から"Tの倍数"という部分を抜いただけ。)

 

ただこれだとA問題にしては難しすぎるという話になり、最終的に"Tの倍数"という条件が付きました。

 

  • B問題

去年のKUPCの没案だったりします。みんな大好きパズルです。

想定解は2通りあり、解説に両方載せています。

 

  • C問題

僕はあんまり関わってません。はじめB問題に置かれていましたが、かなり難しいということが判明して後ろに飛ばされました。

準備側の気分次第でDにもEにも飛ぶんだぞってことで

 

  • D問題

僕はあんまり関わってません。みんな大好きゲームです。

 

  • E問題

これも去年のKUPCの没案から。まともな問題でも、「似たようなジャンルの問題がたくさんある」という理由で結構没になるんですよね・・・

出力形式については完全に忘れてました。ごめんなさい。

 

  • F問題

僕がはじめに出す予定だった問題が没になり、代わりに入れられました。

結構好きな問題です。

準備してくれた人がナップサック近似アルゴリズムを倒すのに苦心していました。(その余波でテストケースがたくさんあります。)

 

  • G問題

好きな問題です。面白いと思います。原案見て1秒で採用でした。

 

  • H問題

答えが有理数になるのが面白いと思います。これも原案を解いてすぐに採用しました。

 

  • I問題

原案は全然違う形だったのを、僕がこの形にしました。結構教育的な問題にもなったんじゃないかなと思います。

 

  • J問題

原案はN<=2000だったのをN<=200000にしました。

好きな問題です。面白いと思います。是非証明も併せて考えてみてください。

 

  • K問題

3月に僕が投げた原案そのままです。

枝刈り全探索を落とすためにテストケースを頑張って作りました。

でも一部通ってるっぽくて悲しいです。

 

  • L問題

面白いと思います。

想定解もテスター解も数回WAになりました。

このセットで最も難しいと思います。

 

  • M問題

はじめN<=10^5で提案されていた問題を、N<=10^18に改造しました。

去年のM問題に引き続き、想定以外の解法でたくさん解かれてしまいました。

想定解では、「i 文字目は文字C_iでないといけない」という条件を10000個ほど追加しても解けます。

↑が思いついたのがコンテスト開始直前とかだったので、準備が間に合いませんでした。

 

また、10/30に

https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2789

(ICPC模擬地区予選2016J問題)

に出会い、解説を読んだらかなり本質的なことが書かれていました。

 

  • 没になった問題

F問題の説明にもありますが、問題が1つ準備してから没になりました。

これからもあんまり出題できそうにないのでここで公開します。

長さNの順列が与えられます。
あなたは各要素について、-2<=x<=2を満たすxをえらび、その要素に値をx足します。
こうしてできあがる数列は5^N通りありますが、そのうちの転倒数の最小値と最大値をそれぞれ求めてください。
 
制約:1<=N<=10^5

別のコンテストサイトで0<=x<=1版が出たので没になりました。

 

  • 最後に

来年も是非開催できたらいいなと思っています。

あらためて、コンテストの運営を一緒に行ってくださった皆様、コンテストの準備に多大なるご協力をしてくださったAtCoder社様、そしてコンテストに参加してくださった皆様、本当にありがとうございました！！

ICPC2021 模擬国内予選参加記

  • はじめに

皆さんこんにちは。深夜にyoutubeでラーメンのshort動画が流れてきては悶絶しているheno239です。

 

今回はICPC2021 模擬国内予選(https://jag-icpc.org/?2021%2FPractice%2F%E6%A8%A1%E6%93%AC%E5%9B%BD%E5%86%85%E4%BA%88%E9%81%B8%2F%E6%A1%88%E5%86%85 )に参加しました。

 

チームメンバーは yamunaku君 と moririn2528君 で、去年と全く同じメンバーでの参加になります。

 

  • リハーサル

ハサリールは当日の朝に「ハリサール忘れてた！」と気付いて参加しました。

リルサハーの問題を見たところ、例年のルサーリハ通り前3問が簡単、後ろ1問が不可能(エスパー枠)となっていたので、とりあえずサーハルリの3問目を解いたあと、ハハハハーの4問目でWAを出しました。

他のルルルルル参加者には4問目を解いていたチームもあり、驚きました。

 

  • コンテスト直前

特になし(じゃあなんでこの項目を作ったんだよ)

 

  • コンテスト中の動き

  1. A問題を(どっちだっけ？)、B問題を(どっちだっけ？)、C問題を僕が見る
  2. それぞれが普通に解けたと主張し、それぞれがそれぞれを通す。
  3. 僕とyamunaku君がEとFを見て、moririn君にDを見てもらうことに
  4. E問題がたまたますぐに解法が分かったので、yamunaku君にF問題を見てもらう
  5. Eが通り、G問題を見ると、見るからに面倒な問題だと気付き、気合いを入れる
  6. G問題を実装中にD,Fが通り、2人にH問題を見てもらう
  7. G問題を提出しWAを出すも、ここでyamunaku、覚醒！彼のお手製テストケースが一撃で僕のソースコードを破壊し、見事にバグが取り除かれACに
  8. H問題に取り組み始める。計算を間違えて意味不明なことになったが、チームメイト2人のおかげで意味が分かる問題になり、無事に解けてAC

 

  • 結果

優勝しました✌

f:id:heno239:20211027040128p:plain

 

  • 国内予選本番に向けて

優勝できるようにがんばります

 

  • おまけ

特になし(じゃあなんでこの項目を作ったんだよ)

Topcoder SRM ジャッジが壊れている問題集

随時更新します。私自身が確認しているものには✅マークをつけます。

 

SRM621:M(不当TLE) by Rubikun

SRM624:M(不当TLE) by Rubikun

SRM626:M(不当TLE) by Rubikun

✅SRM640:H(不当TLE)

✅SRM641:E(不当TLE)

✅SRM647:H(不当TLE)

✅SRM648:部屋に入れない

SRM652:M(不当TLE) by Rubikun

✅SRM654:M,H(不当TLE)

SRM665:E,M,H(なんか全部壊れているらしい)

 

 

情報提供いつでもお待ちしております。

twitter(https://twitter.com/heno_code )のDMを開放しておりますので、気軽に教えてください🙇‍♂️

ICPC 2020 Asia Yokohama Regional Contest 参加記

  • 前書き

ICPC 2020 Asia Yokohama Regional Contest にチーム「Heno World」で参加しました。チームメンバーは

heno239

yamunaku

moririn2528

です。

 

ICPCの大会には3年目の出場で、yamunaku君とは3年連続同じチーム、moririn君とは今回が初めてのチームです。チーム作成時点で、学内でもtop3に近いメンバーでチームを組めたと感じており、意気揚々と今回の大会に臨みました。

 

  • コンテスト前

  • チーム紹介ドキュメント

チーム紹介ドキュメントを期限の日ちょうどに送りました。

 

チーム紹介ドキュメントの説明には、60行75列のグリッドを出力するとACできると書いてあったので、ACを60*75/2-4個とWAを4個書いて提出しました。

 

 

WAが紛れているのにもかかわらず受理されたので、テストケースがあまり強くないと思います。

 

  • 顔写真

顔写真を期限の日ちょうどに送りました。ICPCらしく腕組みをした写真を送りました。(WFの参加チームがよくチーム紹介映像で腕組みをしています。)

 

提出していない人がいらすとやになっていて面白かったです。

 

  • お菓子

コンテスト前のある日、ICPCからICPC BOX(と勝手に呼んでいる)が送られてきました。中にはコンテストの概要が書かれた冊子やICPC Tシャツ、スポンサーのあれこれと、さらにお菓子袋が入っていました。

 

せっかくだしお菓子はICPC当日に食べようと思って全部残していたんですが、中身の影響を受けて同じものをコンビニで買って食べたりしていたので、そんなに意味のある決意ではなかったのかもしれません。

 

  • コンテスト当日の朝

コンテストの開始時間は、9時でした。9時は9時でも朝の9時ってなーんだ？→午前9時です。普段夜9時にAtCoderのコンテストに出ている身としては、感覚が大きくずれるので調整が難しかったです。

 

前日からの作戦として「夜23時に寝て朝7時に起きればまあ普通にいいんじゃないか作戦」を掲げていたのですが、やはり大会前の緊張もあり、(夜は23時に眠れたものの)朝は5時に起きてしまいました。

 

起床したあと、悲劇が僕を待っていました。

 仕方がないのでAOJ-ICPCの問題を解いていました。

 

その後、チームメイトが無事起きていることも確認でき、安心してコンテストに臨みました。

 

  • コンテスト中

序盤の作戦として、A問題とB問題をチームメイトの2人に任せて、henoは数え上げに特攻するという作戦をとりました。作戦の意図として、数え上げの早解きにはそれなりに自信があるので、

「難しめの数え上げを早めに解ければそれを見た他のチームが(早めに解かれてるし簡単そう)と思って挑み、時間を浪費してくれないかな」

という意図がありました。実際どれくらい意図が通じたのかは分かっていないです。

 

そんなこんなでA,B,I(FA)が通りました。この時点で順位表がG,H,Jが通っていたので、3人でそれぞれの問題に挑みました。自分はH問題にいき、少しだけ悩みましたが、無事に通すことができました。

 

自分がH問題で少し悩んでいる間にチームメイトがG,Jを通してくれていたので、Cに1人、Eに2人いきました。Eを僕とmoririn君で読んでいたんですが、moririn君から解法のアイデアを貰ったので、自分がそれを実装することにして、moririn君にK問題を任せる形になりました。

 

Eの誤差で苦しんでいる間にCとKが通っており、さらにEもyamunaku君の手助けをもらって通りました。すごくチームメイトが心強かったです。残すはD問題とF問題で、D問題はかなり難しそうに見えたので、F問題にいきました。

 

紆余曲折あってF問題を通しました。N<=2000でTL10sならO(N^3)が通ってしまうんですね～

 

最後に残ったD問題で、O(N(logN)^2)の解法を書いたものの、サンプルが合わないままコンテスト終了時間となりました。全完がかかっていたので、悔しかったです。

 

 ↑この人、O(N(logN)^3)とか言ってますが、O(N(logN)^2)です。記憶が正しければ、二分探索していないのに二分探索分のlogを生み出しています。

 

  • コンテスト後

コンテストが終わったので、オンサイト(オンサイトではない)イベント特有の"""渾身の懇親"""をします。

 この懇親会場、なんとバーチャルな空間に自分のアバターを投影して、歩き回ったりして動くことで近くにいる人とだけ話せるという、オンサイトの懇親会場を再現するかのような会場となっていました。人々はこの会場をgatherと呼んでいました。

 

14時にコンテストが終わってすぐにgatherに入場できるようになったので、昼食RTA

をしつつ、gatherに入りました。

 

その後、問題の解説やスポンサーの方のお話などがあったのちに、「これを見に来たといっても過言ではない」「ICPCで最も偉大なイベント」「あまりの盛り上がりに地震が引き起こされる」「全米がスーパーハイテンションになった」等と評されている*1、\\\\\\「「「YES/NO」」」////// が始まりました。

YES/NOでは、公式認定YES/NOおじさんが司会をして、まだ結果が明かされていない提出の結果をハイテンションで1つずつ明かしていくことになります。

 

YES/NOではやはり盛り上がって、gather内で興奮した人々が会場を走り回り、各所で追突して救急車が呼ばれる事態となっていました*2。

 

YES/NOが終わり、順位の発表がありました。

 うれしい

 

順位の発表後は20時頃までgatherに残り、懇親を続けていました。

 

  • 余談ですが

gatherでは現実の肉体とgather内のアバターで痛覚が共有されている*3ので、gather内で歩き回った結果、

 となりました。

 

 

  • まとめ

結果として、今回のICPC 2020 Asia Yokohama Regional Contestは2位で終わることができました。事前の目標として、「1位のKINGには絶対勝てないので2位を狙おう」と思っていたので、無事にそれが達成できてかなりうれしいです。

f:id:heno239:20210318175228p:plain

World Finalへの2回目の出場権を手に入れてしまったので、辞退しない限りはICPCアジア大会はこれで引退です。

未来の2回のWFに向けて、より一層強くなり、最終的にはメダルを取りたいと思っています。頑張ります！

 

 

 

  • おまけ

2021年3月18日の未明。彼は悪夢を見ていた。彼は夢の中でICPC 2020 Asia Yokohama Regional Contest に参加していた。

彼はE問題に提出した。WA。もう1回提出。WA。

彼はもがいたが、結局E問題を通すことができなかった。この世の全ての誤差を恨みながら、彼は夢の世界を去っていった___

*1:評されていません

*2:なっていません

*3:されていません