heno239’s blog

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

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:されていません

ICPC2020 模擬地区 感想

  • コンテスト前

11時に起きて、昼食にカツカレーうどん(大盛)を食べました。おいしかったです。

 

13時からコンテストが始まるので、それに備えてログインを試みたり、競技ルールを読んだり、チョコレートに手が伸びそうになったり、水を飲むとみせかけて飲まなかったり、暖房を付けないとみせかけて付けたりしていました。

 

  • コンテスト中

難易度順不同の気持ちだったので、僕が前から、チームメイトが後ろから読みました。

(実際は去年と同じくABが簡単でそれ以外が順不同なので、ムーブとしては大間違い。)

以下、自分の関わった問題を時系列順にあげます。

 

 

  • A問題

シミュレーションする。うっかり一か所だけDとLを書き間違えて1WA。注意力3万。

  • B問題

中央値を見つけていけばよく、priority_queueを使ってO(N^2logN)で実装。定数倍軽いしTLEは大丈夫かなと思ったら大丈夫だった。

  • E問題

この前Div1で似たようなのあった気がする。各マスのとれる値の範囲をベルマンフォードを使って計算。負の時刻を操ることで2WAを生み出す(大反省)。

  • C問題

値が小さい順にまとめてDP。勘違いしまくってサンプルを合わせるまでに1年ぐらいかかり、サンプルが合ったので提出するとまさかのWA。そのあと

4

1 1 2 2

で落ちることを発見し、なんとか修正してAC。コンテスト中で一番悔しさの残る問題だった。ちなみに計算量はO(N^4)。

  • F問題

sortしてCHTしてくださいと書かれてあるので、見た目の割に結構実装重いなと感じつつも、一発AC。WAが出なくてよかった。

  • G問題

チームメイトが定数倍TLEで苦しんでいたので、「map<pair<int,ll>,ll>をやめてvector<map<ll,ll>>にするといいよ」と言ったらのちに通ってた。ナイス。

  • I問題

連立方程式を解いてくださいと問題文に書いているのでその通りにする。CFからコード引っ張ろうと思ったらタイミング悪くCFが落ちてて悲しかった。というか行列ライブラリ作ったはずなのに消えてるんだけど、誰か盗んだ？

 

「S自身はいつもSに到達可能」を読んでいなくて1WAしたが、そこ以外はすんなり。

  • 次

チームメイト2人がそれぞれHとJを考えているらしいので、DとKを並列考察。

成果が得られず、その時点でQWE_QWEが通していたHを奪いに行くことに。

  • H問題

rの値が小さいので全探索すると、すんなり通ってよかった。

  • K問題

落ち着いて考えなおすと複素数になって、解けるようになった。

X=Y=0のケースで1WA。ひどいよ～

  • J問題

Dが解けそうになかったのでチームメイトが考えていたJを奪いに。

少し考えるとpath add zero countになったので、HLD+遅延セグ木でO(Q(logQ)^2)でAC。

見返したところ実装時間が24分で、思ったより早かったと自己満足。

 

  • コンテスト後

今日AGCあるってまじ？

 

  • まとめ

自分はもっと高難易度を攻めて、序中盤はもっとチームメイトに頼った方がいいなと反省しました。

 

今回の結果は大学別2位なのでおそらくWF進出圏内。本番でもこれぐらいのパフォーマンスが出したいところです。

 

  • おまけ

【こんなICPCの大会は嫌だ】KINGが1位の間コンテスト会場でKING

https://www.youtube.com/watch?v=cm-l2h6GB8Q が流れ続ける

ICPC2020 国内予選参加記

  • 参加までの流れ

今年で3年目のICPCに今年も挑戦。

 

去年のチームメンバーであったtempuraさんは社会人になり組めなくなったので、新しいメンバーとしてmoririn君をスカウト。

 

その結果、3人とも橙以上の学内topチームになり、絶対に負けられない戦いに...(学内のICPC参加権利を持つ橙以上の人は現在5人のはず)

 

意気込み↓

 

 

  • コンテスト開始

5分ぐらいログインできなくて焦る。電話をするとつながらないので、全国的にログインできないんだなあと推測して少し安心する。

 

と思ったら突然ログインできるようになり、そのままコンテストが始まったのでびっくりする。

 

  • コンテスト序盤

ABをyamunaku & moririn にまかせて、Cを読む。

ABを一瞬で通してくれたので、一安心。CもO((約数の個数)^2)をすると3分ぐらいで実行が終わってくれたので、そのままAC。

 

という風にかなり良い感じの滑り出しを決めた。(ICPC2019国内予選、ICPC2019ベトナム大会、ICPC2020模擬国内ではかなりのスロースタートだったので、珍しく良い感じ)

 

  • コンテスト中盤その1

Dにyamunaku&moririn, Eを自分が担当する。

 

Dの考察が早々に終わったみたいで、構文解析を誰が書くかで少し迷ったが、Eに一番強いのが自分だと思ったので、yamunakuにDの実装を託した。

 

ここから、

yamunaku:Dの実装

heno:Eの考察

moririn:Fの考察

の3並列が始まる。

 

※試合後にこの話をしたらある人に「DEF3並列は攻めてるなあ」と言われてしまった

 

  • コンテスト中盤その2

  • Eの話

とりあえず連結成分ごとにわけると、サイズが30*60に見える。

よーーーーーーーーーーーーーーーーーーーーーーーーーくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよくよく凝視すると(この間5分~10分)、15*60になることに気付く。

あとはbit DPを実装するだけ(かなり重かった)。計算量はO(2^(N/4)*N*M)

 

  • Eが通った後の話

Dの様子を聞いたら「書き終わってデバッグ中」とのことだったので、yamunaku君に託したままFを手伝いにいく。moririn君からFの考察を聞くと既に考察が終わっていたので、実装する。(これも結構実装重かった...)

 

結局Dは早々に通り、Fは30分後ぐらいに通った。この時点で国内予選通過を確信する。(6完時点で暫定１位だった。)

 

  • コンテスト終盤

GとHを見ると、GがフローっぽくてHが幾何。Gが解ける問題に見えたので3人ともGを見る。

色々考えた結果O(N^3M^3log(NM)^2)とかいう多項式(笑)の解法を実装したが、バグを取り切った時点で残り時間が数分しかなく、実行続けたままコンテストは終わりを迎えてしまう________

 

  • コンテスト後

10分ぐらい実行させると実行が終わったので、「あと20分あればなあ」と負け惜しみをする。

 

遠吠え↓

 

 

 

  • 反省点

Gがコンテスト中に通せなかったのは実力不足(フローへの理解&慣れ不足)であり、悔しい。

大阪にいたため京都で行われた打ち上げに参加できなかった。前日から京都入りしておくべきだった。

 

  • アジアに向けての意気込み

国内予選と同様、2位を取れるように頑張りたい。

 

 

 

 

 

 

 

 

 

 

 

 

  • おまけ

最後はGに張り付いていて1時間ほど順位表を見ていなかったため、コンテスト終了直前は「KINGと自チームを除いて、7完チームが2チームぐらい、6完チームが少なくとも10チームはいるんだろうな」と思っていた。終了後の順位表を見てかなりびっくりした。

ICPC 模擬国内予選 2020 参加記

  • 参加までの流れ

去年もおととしも参加したので、今年も参加しようということに

チームメイトはyamunaku君とmoririn2528君(二人とも学内でトップレベルの強さがある)

 

  • コンテスト0分時点(開始)

yamunaku&moririn:序盤を分担してとりかかっていた

heno:模擬国内の存在に気付かず悠々と昼食をとっていた　←は？

 

  • コンテスト30分時点

yamunaku&moririn:AとBをACする

heno:slackのDMを確認すると二人がなぜか自分を含むDMで通話してることに気付く

 

  • コンテスト35分時点

yamunaku&moririn:考察 or 実装を続ける

heno:謎の通話に焦ってtwitterを見ていると模擬国内が現在進行形であることに気付き、慌てて準備する。水をこぼす。

 

  • コンテスト40分時点

ここでついにhenoが通話に合流する。二人ともすごく温厚なのでほとんど怒られなかった。CDを平行してやってるらしいのでEを見に行く。

 

  • コンテスト1時間~1時間半時点

EのO(NMlogM)解を書くが、実行に無限時間かかる。(この間にDが通る。)定数倍高速化しても無限時間かかったので、ちゃんと考えてO(NM)に落とし、無事AC。ここのタイムロスはもったいなかった(後悔ポイント1)。

チームメイトの二人が平行していたCDのうちDが通る。CからHELPが出るが、他の二人はそれを無視してFとHに行ってしまう。(後悔ポイント2、あのCは結構はまるときつそうな見た目なので複数人ではやめに見るべきだった)

 

  • コンテスト開始2時間時点

Fは実装するだけの問題。展開図からどうやってサイコロを作ろうかという部分に一番悩んでいたが、yamunakuから「展開図の上でサイコロを転がしながら印字していけばよさそう」という賢い作戦を教えてもらい、実装がかなり楽になった。

奇跡的に1回目のデバッグでサンプルが通り、提出したらそのまま通ってしまった。筋肉は裏切らない。

 

  • コンテスト開始2時間時点~3時間時点(終了)

チームメイトがHを通しててすごい。自分はその間Cの手助けに入り、無事通す。

その後Gの実装にとりかかっていたが、実装しきれずに終了。悔しい。

 

  • 結果

7完で5位。予選通過確実。

 

  • 反省点

遅刻しない

logに甘えない(E問題)

HELPが出ていたらはやめにその人を(その問題から)解放するべき

 

  • 国内予選に向けて

万全のコンディションで迎えれば99.999%通過すると思うので、当日に向けて万全のコンディションを整えていきたい。