heno239’s blog

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

ICPC 2021 Asia Yokohama Regional 参加記

  • まえがき

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

今回は 

ICPC 2021 Asia Yokohama Regional

にチーム「Heno World」で参加しました。

チームメンバーはheno239・yamunaku・moririn2528の3人で、去年とチーム名もメンバーも同じです。

わざわざ集まるのが面倒だった昨今の情勢を鑑みて、3人とも別の部屋からオンラインで出場することになりました。

 

  • 1日目(コンテスト前日)

この日は13:00からコンテストの参加受付がありました。

13時前にチームメンバーが全員集まったので安心感がありました。(色々あって受付は13:30ぐらいになりました)

13:50ぐらいから開会式があり、開会しました。

 

14:10から、本番と同じ環境を用いたpractice contestがありました。

コンテスト時間は2時間で、問題は去年の問題がそのまま使われていました。

去年の僕がE,F,H,I問題を実装していたので、practiceではそれ以外のA,B,C,D,G,J,KのうちA,B,C,J,Kを腕慣らしで通しました。1年経ってたのに全部解法を覚えていて、やっぱり印象に強く残るコンテストなんだなあと実感しました。

 

また、practice contestでは「assertがちゃんとRE返してくれるか」や「無限ループするとREになるか」や「bitsetの_first_bitが使えるか」や「美味しいカレーの作り方を書いたらACになるか」*1等、様々なことを確認しました。

 

practice contestが終わったあと、軽い質問時間がありました。

そこで「submissionした後にどのソースコードを提出したかを確認する方法はありますか?」という質問がありました。(submitはローカルファイルを選んで提出する形だったので、誤提出が起きやすかった、という事情がありました)

この質問に対する回答が「あると思うんだけど現状ない」みたいな感じで、結局翌日に「ある」になりました。

(去年は結局なかった(し、誰も指摘しなかった)ので、変わったのすごい)

 

参考資料(?)↓

 

質問時間が終わるとその日のプログラムは終わりで、あとは「ちゃんと早く寝る」だけになりました。

コンテストに向けて3日前ぐらいから23時寝7時起きみたいな生活をしていたので、その日も無事21時に寝ることができました。

 

  • 2日目(コンテスト当日)

朝3時に起きて、その後眠れませんでした。今もまだ眠れていないので1週間ずっと徹夜しています。

8時頃にはチームメンバー全員の起床が確認でき、いよいよ本番を待つこととなりました。

 

そして9:10からコンテストは始まりました。

 

  • コンテスト中

  1. チームメイト2人にAとBを任せて*2、自分はC以降の問題文を読む。
  2. まずKを読み、「時間をかければ解けるけどすぐには解けなさそう、順位表で他のチーム解かれてたらやろうかな」と思いパス
  3. やっぱり去年と同様にmod 998244353みたいなことが書いてある問題からやろうと思いなおし、問題文を"mod"があるかどうかで枝刈り探索していくと、G問題「mod 10^9+7」に到達。
  4. 問題を読むと一瞬で解法が浮かんだので実装するも、WA。(それなりに実装量もあるので実装ミスかな)と思い、小さいケースを手で作って試していると、考察ミスが発覚(自分の子が親で自分の親が子になるやつ)。修正してAC(FA)
  5. チームメイトの様子を見ているとAがACされ、BでWAが出て苦戦している様子。Bを手伝いに行き実装すると、自分もWAが出て頭を抱える。結局3人とも誤読していることを発見し、修正してAC
  6. この時点で開始1時間ほどで、順位表を見るとJが通されている。そこで自分がJに行き、チームメイトに他の問題を探ってもらう形に。
  7. Jで「overflow事故」「場合分け書き忘れ」「提出ファイル間違える」「ジャッジミス」の4連コンボが決まり、4ペナ出しつつなんとかAC。今になって思うと、早く解かなきゃ、とかなり焦っていた気がする(特に提出ファイル間違いについては・・・)
  8. Jで苦しんでいる間にC問題とD問題をチームメイトがそれぞれやってくれていたので、他の問題を見る。各問題の所感は、E問題:存在を忘れてた、F問題:ちょっと考えたけど分からない、そもそもTL:30sがやばすぎるので近寄りたくない、H問題:誤差の制約をどう使うか分からない、I問題:頑張れば解けそう、K問題:頑張れば解けそう、といった感じ。
  9. 上記の中からK問題を選び、突撃。この間にDはACされ、CはWAが出る。C問題のWAの原因特定も手伝いつつK問題を考える形に。
  10. 結局K問題に進展はなく、C問題は僕なしで通る。チームメイトありがとう・・・
  11. 3人そろったところで問題を見直し、自分もK問題の考察からI問題の考察に移行する。
  12. チームメイトとグラフのお絵描きをしながらI問題の考察をし、かなり順調にいって考察が完成する。そのまま実装し、AC(FA)を勝ち取る。この時点で7完がHeno Worldのみとなり、単独一位に浮上する。(そしてこの時点でほぼ2位に入るだろうと思っていた。)
  13. 相変わらずE問題の存在は忘れているしF問題はTL:30s,H問題は誤差で近づきたくないので、K問題に突撃。そのまま適当な嘘をいくつか投げて撃沈。(実はコンテスト後に誤読が発覚)。

そしてコンテストが終わりました。順位表は終了1時間前の状態のまま凍結されており、その時点ではUT a.k.a. Isには確実に負け、tonosamaやTLE_workには2問通されていると負ける、他のチームには大体勝ち、という状況でした。

 

特にtonosamaが怖かったので、ドキドキしながらYesNo(順位表開示イベント)を迎えました。

 

  • コンテスト後

まず問題の解説とスポンサー企業の紹介がありました。

問題の解説では、ヤバいと思って避けたF問題が実は解法から見ると普通の問題だったり、H問題の解説に驚いたり、K問題の解法になるほどと思ったりしたり、E問題の解法にうわあとなったりしました。特にF問題についてはACが出なかったことが驚くべきものでした(TLが30sというだけで全チームが避けた結果、こうなっているのだろうと思います。)

 

その後いよいよYesNoがありました。

YesNoの結果2位が確定し、例年通りであればほぼ確実にWorld Finalへの参加が決まりました。とても嬉しかったのを覚えています。

f:id:heno239:20220323192456p:plain

 

表彰式ではインタビューみたいなものがあったのですが、コメント内容はちゃんと準備したのに名乗るのを忘れてしまいました。その後に1位のUT a.k.a. Isの方々か素晴らしいインタビューをしていったので、社会性の違いを見せつけられる結果となってしまいました*3

 

その後、gatherにてオンライン懇親会が行われており、渾身の懇親をしました。20:00ぐらいに眠気に勝てなくなり、そこで僕のICPC 2021 Asia Yokohama Regionalは幕を閉じることとなりました。

  • あとがき

結果として2位をとり、おそらくWorld Finalへ行きます。

これでWorld Finalは3回目であり、World Finalの参加回数の上限規定に引っかかるため、来年はICPCに出られません。

結局、ICPC Asia Yokohama Regionalは3度参加し、そのうち2回がオンラインになってしまいました。ここ2年横浜の現地で他のチームの方々と交流できなかったのがとても心残りです。

World Finalも、

World Final 2019:オンラインで既に開催された

World Final 2020:今年11月に開催が予定されていて、どうなるか(オンラインになるかとか)が分からない

World Final 2021(今回の):どうなるか何も分からない

という感じで、かなり不明瞭な感じになっています。

 

2位をとった安堵の先にも後にも不安だらけですが、World Finalでも結果を残せるように頑張っていきたいです。

ICPC運営の皆さん、他のチームの皆さん、また特にチームメイトの2人へ、ありがとうございました。

 

  • おまけ

うまい棒ではずれを引いたので今回はおまけはありません。

*1:なりませんでした

*2:コンテストはA,B問題が簡単な2問と公表されており、それ以外の問題は難易度がランダムだった

*3:Give me sociability

AOJ 2597 Color the Map Extreme

  • まえがき

解説PDFが閲覧できなくなっていたのと、ネットに自分の解法が落ちてなさそうだったので書きました。

 

  • 問題概要

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

 

  • 解法

とりあえずグラフを作る。4色定理があるので答えは4以下。

 

答えが1かどうか→グラフに辺があるかどうか

答えが2かどうか→グラフが二部グラフかどうか

 

なので、答えが3かどうかを調べる。

 

まず、色1,2,3があったときに、色3となる頂点が全て決まっている場合、これは残りの頂点を2色で塗る問題に帰着される。

 

そこで問題となるのが色3となる頂点の決め方に2^N通りあること。少し考えると、色3となる頂点の集合は極大独立集合であると仮定してよい。

 

ところでグラフの極大独立集合は O(1.618^N) で列挙できる。

具体的には、頂点を1から順に見ていったときに、次数0の頂点は独立集合に加えるしかないし、次数1以上の頂点はそれを独立集合に加えると頂点N-2以下のグラフとなるので、計算量がフィボナッチ数で抑えられる。

 

したがってO(N^2*1.618^N)でこの問題は解くことができる。

このままだと少し遅いので、お好みの枝刈りをどうぞ

(私の場合は、答えが3かどうかの判定の直前に次数2以下の頂点を順次削除しました。)

 

  • 実装

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=6161908#1

AOJ 1340 Directional Resemblance

  • まえがき

初見でかなり混乱したので書きました

そんなに厳密な説明じゃないです(覚え書き程度です)

 

  • 問題内容

N個の3次元ベクトルが与えられる。

これらのベクトルは全てx軸方向、y軸方向、z軸方向に正である。

ベクトルのうち2つをとったとき、なす角の最小値と、最小値になるようなindexのpairを求めよ。

 

  • 解法

問題を言い換えます。

 

まず、各ベクトルを、「原点を中心とする半径1の球の表面」に射影します。

(前述でベクトルv_iを点p_iに射影したとします。)

そうすると、2つのベクトルv_i,v_jのなす角の大きさは、点p_i,点p_jを最短距離で結ぶ球の弧の長さと比例します。さらにこの値は、点p_iと点p_jのユークリッド距離に比例します(最重要)。

 

結局、「球面上にN個の点が与えられるので、ユークリッド距離が最短の2点を求める」問題に言い換えられました。

 

あとは、最近点対(参照: https://compro.tsutaj.com//archive/190207_divcon.pdf )と同様にやります。具体的には、(z軸のことを忘れて)上のスライドのp37のように各点についてスリットを考え、この点とスリット内にある点それぞれについて、(z軸のことを思い出して)3次元空間上の距離を求めます。

「x,yの値が近いがzの値が違う点がめちゃくちゃある」みたいなときに計算量が崩壊しそうですが、「点が球面上にある」という条件が効いて(?)十分高速に動きました。

 

  • 実装

https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=6148187#1

 

  • おわりに

なにかあれば↓にお願いします。

twitter.com

Educational Codeforces Round 15 F. T-Shirts

  • まえがき

解説が無かったので、正解につながるキーワードを書いておきます。

(解説と呼べるほど丁寧には書いてありません)

  • 問題概要

https://codeforces.com/contest/702/problem/F

問題を言い換えると、結局長さnの数列aがあって、クエリxに対して

int cnt=0;

for(int i=0;i<n;i++){

  if(x>=a[i])x-=a[i],cnt++;

}

return cnt;

をする問題。

  • キーワード

この問題を解くにあたってのキーワードは、「xの値を高速にx/2未満にする」です。

 

  • 解法の概要

いま、数列中での現在地iと現在のクエリの値xがあります。

2^k<=x<2^(k+1)を満たす整数kを用意します。

ここから、O(logN)でiの値を進めてxの値を2^k未満にします。

このとき、次の2パターンがあります。

  1. aの値が2^k以上のものを1つ以上とる
  2. aの値が2^k未満のものだけでxの値が2^k未満になる。

一旦1.のパターンがおこり得ないとすると、2.のパターンはあらかじめ各0<=k<20に対して値が2^k未満のものだけの数列を作っておくと、累積和を良い感じに二分探索することで、iをどこまで進めるとxが2^k未満になるか分かります。

逆に2.のパターンがおこり得ないとすると、1.のパターンはこれもあらかじめ各0<=k<20に対してb_i=(2^k<=a_iかつa_i<2^(k+1)のときは0<=j<iでa_j<2^kを満たすものの総和+a_i、そうでない時は2^100)という数列を用意しておくと、「整数le,supに対し、j>=leかつb_j<=supを満たすjの最小値」を求める話になります。

 

そこで、2つのパターンのうち行き先が近い方に行くことで、iの値を進めてかつxの値を2^k未満にすることができます。

 

  • 計算量

Aを数列aの最大値として、O(NlogA+QlogNlogA)

  • 関連問題

Codeforces Global Round 14 I. Phoenix and Diamonds

https://codeforces.com/contest/1515/problem/I

この問題に個数と個数の変更クエリがついて複雑になった問題。

逆にいえば複雑になっただけなので、ほとんど同じ解法でものすごく頑張ると解けます。

  • あとがき

かなり雑に書いたので、何かあれば 

https://twitter.com/heno_code

まで気軽にご連絡ください。

 

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

 

  • 国内予選本番に向けて

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

 

  • おまけ

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