ICPC2020 国内予選 参加記
ICPC2020国内予選にSimojappyで参加してきました.
コンテスト前
模擬国内で12位だったので、ワンちゃんあるかなーって思ってた
前日は作戦会議という名のだべり会をしていた
当日直前はあんまりやることがなくラムネを食べたりtouristになったりして暇をつぶす
・バグらせる、バグらせそう、よくわからない、なんもわからない 等はとりあえず声に出して伝える(聞くかどうかは別)
・序盤でだれか一人が全問題を読む (実装ゲーや幾何構文解析があるかを見る)
・提出を間違えない、提出するよーって言ったとき他の人が覚えてたら注意する
・例年の感じ5完じゃ無理なので、4完時点で一問に全員集まるのは抑えて分散したいね
・構文解析がDかEにあったらもじゃはそれに初手で凸
みたいなことを話した
コンテスト開始
ログインすると、なんか無理 と言われる.
担当官に電話をするがつながらない (メールは模擬国内用と書かれていて本番に使っていいのかわからなかった)
ネットにつなげないので周りのチームも同じ状況か分からないし、この状態が30分とか続いたらどうしようかなーって考えてたらつながる.
模擬国内のページに.
順位表を見るとみんな同じ状況っぽいので、待つ
ヌルっと始まる.
コンテスト開始！
Aを見る.もじゃがDにいく
Aを解く。
出来たA01_output.txtとinputデータを死ぬほど見比べて目視でも間違ってなさそうなので提出
出来たA02_output.txtとinputデータを死ぬほど見比べて目視でも間違ってなさそうなので提出
AをAC BはsimがACしてくれる.
Dは構文解析以外のパートが難しい という話を聞きながらCを見る. simにE以降に目を通してもらう
CはN( <= 10^15)の約数の数ってどのくらいだっけ・・・となる
いつもなら高度合成数で調べてはい。をするのであんまり考えたことなく 約数全探索でいけるか考える
simが合流してくれて,A,B,Cのうち一番小さいのは N ^(1/3)以下なのでそれを全探索すればと言われて確かにーとなる
mojaがDで沼ってるらしいのでmojaにCの実装をしてもらい、じゅがDをsimがEを見る.
Dは制約を見て N! を 2^N にするやつだーとなる
大小のやつが20個くらいなのでそれに関して全探索すればいいかな
それトポソの数え上げだからさらにO(2^K)かかるよと言われ、確かになぁ となる
ならなんも分からん・・・
mojaがCを通してくれる. simがE解けそうといったのでmojaがEに合流して、確かに解けそうとなったらしく,mojaがEを実装する
simもDに合流してもらう
分からん・・・・・・・・・
mojaがEを通す.
この時点でDに3人で粘着してもワンチャンが芽生えないので、mojaがDで juppy simがFを見る
部分永続UnionFindで愚直にやるとN,M=10^5のO( NM α(N) logN )でテストケース50個なので厳しいかなとなる (振り返るとそれで通してる人がかなりいたのでそれも考えるべきだった)
UFのsizeを見るのをNM回やるのが明らかにやばいので、各階層での辺の端だけを見るようにすれば M回でいけるーとなる
simが実装している間、細かい罠がいくつか思い当たり言いながら修正してもらう
バグりまくってコンテストが終わる
結果は38位ABCE4完でおわりました。。。。。
Dは <>じゃなくて最後のアルファベットに対しての大小で全探索すればいいらしい。なるほどー
かなりの数のチームが通してるDに3人取り掛かって、時間を取られまくって、結局解けなかったのが痛すぎた.
本番で一番したくない沼り方だったし、個人的には最近やってるコドフォの問題っぽい感じなので 絶対通すべきだった.
ICPCは来年が最後なので,なんとかして国内予選通ってアジア旅行したい。
競プロキャンプ2020 参加記
こんにちは。じゅっぴーです。
競プロキャンプ2020参加記の参加記というかメモ。
前日
前日に京都につく.
ホテルに荷物おいて,夜飯を食べに行く
生湯葉と日本酒おいしかったーって散歩していると、「わらび餅は飲み物です」って急に断言されて怖くなったので部屋に戻って寝る
初日出発
集合場所は京都と大久保で選べる感じだった.
どうせなら聞いたことない大久保ってところにして散策するか～って思ってたらみんな京都でおひるごはんワイワイしてて涙が止まらなかった.
大久保歩き回ってたら銭湯があったので ﾖｯｼｬｧ٩(・ω・)วlet's go! しようと思ったが昼飯まだなのと案外時間がギリギリだったのでまたの機会に
酒粕の風味が思っていた数倍強くておいしかった .好みが分かれそうな味.
京都、メシ、おいしい
初日レク
集合場所に行くと,なにやら見覚えのあるデザインの名札をぶら下げているグループがいた.
競プロerだった.
みんな集まったら、レク会場に٩(・ω・)วlet's go! する.
レク会場まではもじゃとまつかわさんとfiordさんとスギノキさんと歩く.
レク会場でレクをする.
落語を聞いて笑って、おいしい阿闍梨餅を食べて楽しくなる.
レク会場で全体的に打ち解けた雰囲気になって,初めての方とも喋れるようになった.
初日BBQ&就寝
レク会場から駅まではすとまとと社会人競プロerすげーって話をして、
駅からBBQのところまではおうどん君ときち君ともじゃとタクシーに乗った.
おうどん君、高校生でVRに興味があって実機に触ったことがあるらしいし,ちゃんと色々情報のアンテナを張っていて素晴らしい となる.
BBQ会場は、、ユーフォの聖地だった.(´ ✪ω✪` )ｽｺﾞｲ!!!
着いたときは雨だったけど,止んでくれたので
みらーじゅとにぼしと火起こしをして,肉うめぇええええって言いながら, まさぁぁさんとかいずらいとさんとかと初めてお話しした.
じゅぴろともこの時初会合して,かわらさんと一緒にお酒を飲んだ
方付けしたあと,まさぁぁさんが持ってくれたコヨーテというゲームで遊んだ.
そのあとはみらーじゅのVALOのオーメンの声真似とかを聞いて,にぼしとゲラゲラしていた
2日目
朝に卵焼きと米を食べて,Atcoderじゃんけんに負けてもじゃに名札を取られて,宇治でおいしいお弁当にありつく
お昼ご飯中はいずらいとさんの髪の毛サラサラですげぇええとなっていた.
平等院鳳凰堂に行ったあと,たつやんさんにおいしいお茶屋さんに連れていっていただいて,帰りの電車ではｲﾅ月さんと一人暮らしの話とかをした.
おわり
おいしいしか言ってねぇ......
競プロキャンプ、全体でゆるゆる会話しやすい雰囲気が作られていて,とても良いイベントだった.
幹事の方や話してくれた方, ありがとうございました！
次もぜひ行きたい！！
ACPC2020 day3 参加記
お風呂入ってたらギリギリになってた
A moja B sim C juppyで見る.
Cはday1で沼ったからあんまりいい思い出なかったけど,今回は素直なDPだった.
一応TL怖いし早いdp書いたら 4.09sで草となったがまぁAC
Dはsimが分かったと言っていたのでEを見る.
modいっぱいとるやつ.単調減少にした後よくわからない.
Dが勘違いしてたらしいので,Dに合流する.
mojaがE みてmodで小さくなって区から二分探索でやっていけばそんなに回数かからなそうと言って通す.
(´ ✪ω✪` )ｽｺﾞｲ!!!
Dはsimと同じ勘違い嘘解法をはやしたのち,実はそれで合っているのでは？と思ったが mod M のMが素数でないのでやっぱり嘘だった.
mojaが強連結成分分解でいいのでは？と教えてくれる.
【ｺﾞｸﾘ】ﾟωﾟ；)凄い・・・
simが強連結成分分解した後にトポロジカルソートすればいいのでは？と教えてくれる.
(´ ✪ω✪` )ｽｺﾞｲ!!!
出すとWAなのでテストケースをいっぱい試すと確かにWAだなぁとなるが, mojaが最後のifの順番が逆なことに気づいてAC.
simとFを見る
それっぽいのが思いついたので,共有したら合ってそうとなってsimがもっと綺麗な実装を詰めてくれる.
mojaに説明している間に,simが通してて草となる.
ｿﾞｲ最(ง˘ω˘)ว強ｿﾞｲ
Gを見る.
M <= 20 なので、マラソンだあああああ！！！！行くぞ！！！！！！=͟͟͞͞(๑•̀=͟͟͞͞(๑•̀д•́=͟͟͞͞(๑•̀д•́๑)=͟͟͞͞(๑•̀д•́)))
2点swapと区間反転をしようとするが1000回くらいしかできなそうで悲しい気持ちになる.
そうしてるとslackが飛んでくる
（ ＾ω＾）・・・はい
2^Mはしたいけど,M=20だからキツイよなぁという話をする.
simに2^MはM=20だからキツくないですよという話をされる.
（ ＾ω＾）・・・はい
お気持ち解法を言っているとsimがそれでいけるといって補足してくれる.
自分が考えてたものと全然違かったが,あってそうなのでGO
色々詰めるとWA
問題文を読み直すとA[-1]に+1することをするっぽい
色々訂正してAC
時間がカスだけど, 7完 できたので良かった(Cしか解いてない小並感)
ACPC2020 day1 参加記
ACPCにSiMoJappyで参加してきました
A,B,Cをそれぞれjuppy,moja,simが見る.
Aはよくある分数の大小を比べるやつなので通して,Dをみる.
Dは座標圧縮してBIT木使えばいけそう.
最近BITライブラリを整理したので,ニコニコになる
と考えている間にmojaがBを通す.
mojaとEをみる.
Eは何個使えばいいかが分かればいけそう...となってからmojaが細かいところを詰めてくれる(感謝)
simがCでハマっていたので,実装を代わってもらいDを通す.
Fを見ると見せかけて誤クリックでGを見る.LかMの端っこが点になりそう
simとmojaがCを解いたのがsample-3で落ちてるのでデバックをすることにする.
その間にmojaがEの部分問題を投げてsimが解く. 連携【ｺﾞｸﾘ】ﾟωﾟ；)凄い・・・
Cのデバックをする.
K本有効な無向辺を貼ったあと,サイクルになるようにN-K本有向辺を貼る...
見れば見るほど合ってそう......というか実装綺麗だな
問題文を読み直す.
1 <= N となっている（ ＾ω＾）・・・（ ＾ω＾）・・・
N = 1は、ズルだろ
N=1の時だけ除外して提出する.
・・・落ちる.(´･ω｀･ )ｴｯ?
「これは沼問題だなぁ・・・」と思いながら何個かテストケースを作ると
N = 2 のとき無向辺1個で完成するのに,それに加えて有向辺1本(2-1)も足してない？
となる.
ということで, N=2 の時も外して提出する.
また落ちる・・・(´･ω｀･ )ｴｯ????????????
よく考えると,上の議論はどのNに対しても使えて,無向辺をN-1本貼ったら有向辺はいらないよね(それはそう)となるので,出すと通る.
やっとC通ったー！となるが, EがTLEとMLEで地獄になっている
Fは三分探索許してくれませんか？となる
EがTLEなのよくわからんなぁと思ってたけど,logが重かったらしい.
ということでカチコチに冷えました
順序付き集合もどき Python
こんにちは。最近読んだ『メイドさんは食べるだけ』って漫画がお気に入りのじゅっぴーです。
クエリ先読みや値の範囲などを用いて、最終的に一度でも入る可能性のある値の配列(all_values)が分かっているとき
・値の追加,削除 (insert_val,delete_val) ・小さい方からk番目(0-indexed)の値 (find_kth_val) ・値がx以下の個数 (count_lower) ・xより大きい中で最も小さい値 (find_higher)
をO(logN)で行う。初期化でソートを入れるためO(NlogN)かかる
BITで個数を管理し、使うのはOrderBITの方。
import bisect class BIT: def __init__(self,len_A): self.N = len_A + 10 self.bit = [0]*(len_A+10) # sum(A0 ~ Ai) # O(log N) def query(self,i): res = 0 idx = i+1 while idx: res += self.bit[idx] idx -= idx&(-idx) return res # Ai += x # O(log N) def update(self,i,x): idx = i+1 while idx < self.N: self.bit[idx] += x idx += idx&(-idx) # min_i satisfying {sum(A0 ~ Ai) >= w} (Ai >= 0) # O(log N) def lower_left(self,w): if (w < 0): return -1 x = 0 k = 1<<(self.N.bit_length()-1) while k > 0: if x+k < self.N and self.bit[x+k] < w: w -= self.bit[x+k] x += k k //= 2 return x class OrderBIT: def __init__(self,all_values,sort_flag = False): if sort_flag: self.A = all_values else: self.A = sorted(all_values) self.B = BIT(len(all_values)) self.num = 0 def insert_val(self,x,c=1): k = bisect.bisect_left(self.A,x) self.B.update(k,c) self.num += c def delete_val(self,x,c=1): k = bisect.bisect_left(self.A,x) self.B.update(k,-c) self.num -= c # find the k-th min_val (k:0-indexed) def find_kth_val(self,k): if self.num <= k: ##### MINIMUM VAL ####### return -10**9 return self.A[self.B.lower_left(k+1)] # count the number of values lower than or equal to x def count_lower(self,x): if x < self.A[0]: return 0 return self.B.query(bisect.bisect_right(self.A,x)-1) # min_val higher than x def find_higher(self,x): return self.find_kth_val(self.count_lower(x))
verify
N <= 5*10^5 O(NlogN)で1128ms
Submission #16480680 - CPSCO2019 Session1
Submission #16482407 - AtCoder Regular Contest 033
Submission #16505873 - 全国統一プログラミング王決定戦本戦
使い方
初期化 O(NlogN)
・最終的に一度でも入る可能性のある値の配列 A
・A がsortされているならsort_flag = True
T = OrderBIT(A)
値の追加・削除 O(logN)
・値 x を c 個追加or削除する
T.insert_val(x,c) T.delete_val(x,c)
k番目に小さい値を返す O(logN)
・kを0-indexed(0,1,2,...)
・k が全体の長さを超えている場合 MINIMUM VAL -10**9 を返す
T.find_kth_val(k)
値がx以下の個数を返す O(logN)
T.count_lower(x)
xより大きい中で最も小さい値を返す O(logN)
・存在いない場合 MINIMUM VAL -10**9 を返す
T.find_higher(x)
KUPC 2020 Spring
KUPC2020にSimojappyで参加した。
simojappy準備完了#kupc2020spring pic.twitter.com/BCSNWumSWG
— じゅっぴー (@juppyjappy) March 20, 2020
コンテスト中の動き
sim,MojaがA,Bを見る。Bの実装が重そうだったけどモジャが通してくれていた。
その間に問題文に目を通す。
D、simがdp[i][j][k] : i 番目までのxorがjで末尾がkを提案してくれる。実装していたら、「k」ではなく「k以下」の方がいいのでは？となる。
計算量的に厳しそうなのでsimに実装を変わってもらう。AC
その間にモジャがEのN=奇数の時を解いてくれる。その後を引き継ぐ。モジャとsimがMに行く。
色々考えてると N = 偶数の時は最小値を見ればよさそうとなる。AC.
Mに合流する。問題分の内容をsimに確認していると、Mojaとsimが問題文を誤読していることに気づく。(部分列を勘違いしてたみたい)
その後一瞬でACしてた。
結局問題文はよくわからなかった。
Fをsimと詰める。木DPチックだなと思いながら、勘解法が思いつく。
Mojaに実装してもらって投げてみる。実装してる間にsimが証明してくれる。AC
いつの間にかモジャがKを通してる。
その後Lが何ケースか通らずマゴマゴしてたら終わった。
— じゅっぴー (@juppyjappy) March 20, 2020
Kyoto University Programming Contest 2020 Spring
— じゅっぴー (@juppyjappy) March 20, 2020
D. dp[i][j][k] i 番目までのxorがjで末尾がk以下
E. Sumの偶奇の変化をみるよくあるやつ
F. 葉から上に負債を押し付ける感じで解をO(N)で構築。その後無駄を省く
本郷で参加してた人達15人で中華に行った。
北京ダックおいしいね。
大所帯のHUPC懇親会 pic.twitter.com/jPA8BdMUrg
— じゅっぴー (@juppyjappy) March 20, 2020
こるとんさんと 今までで激冷えしたRatedのコンテストの話をしながら帰った
— じゅっぴー (@juppyjappy) March 20, 2020
Google Hash Code 2020 SiMoJapPiyo 参加記
こんにちは。じゅっぴーです。
sim,Mojumbo,piyoとGoogle Hash Code 2020 に参加してきました。
Google Hash Codeはマラソン系のコンテストです。
全員マラソン初心者で、焼きなましだけお気持ち理解していきました。
コンテスト前
ぴーよ、、ありがとう！！！
pc複数台使えるの調べてなくて、実家にpc置いてきてて詰んだ。。。ってなってたのでマジでありがたい。
コンテストが午前2:30~6:30からなので、24:00に集合となった。
実はこれは罠で、コンテスト開始は2:45~からだった。
15分暇なんか？
— sim (@i_am_karen_kujo) February 20, 2020
ぴーよは平常運転で1時間半遅刻してきたので、24:00集合でよかったと思う。
みんな集まったところで、前半の流れを軽く決めて、ルール確認をしたりした。テストケースが五個くらいで、テストケースごとにコードを変えていいとか知った。
Google Hash Code 2020いきます pic.twitter.com/BgPa7hUUVs
— じゅっぴー (@juppyjappy) February 20, 2020
ぴーよさん？
コンテスト前半（マラソン）
問題文を読む。
L個の図書館とB種類の本がある。i 番目の図書館に入ってる本と、本ひとつひとつの価値が与えられる。
図書館を何個か選んで、並び替える。前に並んでる図書館ほど多くの本を排出できるとして、排出できる本の価値の最大値を出せ。
ただし排出できる本が被ってるときは二冊目は価値をカウントしない。
のもうちょい複雑版。原文読んで。
図書館の順番と、選んだ図書館が排出する本を選ぶぞ！
抽出する図書館とその順番を決めたとき、その評価関数を決めれば焼きなましできそう！！！！！！！
もじゃが焼きなましを実装する。simが評価関数を考える。piyoとjuppyがテストケースA~Fを調べる。
A : ギャグ。
B : 本の価値が一定。(本の種類を増やせばよい)
C : 図書館の順番が関係ない。
D : 本の価値が一定。(本の種類を増やせばよい)
E : 選べる図書館の個数が少ない(全体の図書館の数 L は大きい)
F : 選べる図書館の個数がさらに少ない(全体の図書館の数 L は大きい)
テストケースの研究をpiyoにまかせて、simの評価関数考察に加わった。
自分は本の価値をぶらしたりする(登場回数が多い本は価値を下げるとか)方法に粘っていたのですが、
simが図書館それぞれに前計算で評価値を付けて、評価値の小さい図書館から貪欲に本を選んでいった時の価値の合計 という評価関数を提案してくれたのですが、図書館に評価付けるの(・∀・)ｲｲﾈ!!となって大賛成でこれを詰めました。
図書館の評価値は、とりあえずその図書館にある本の価値の平均にしました。
でもそれだと例えばテストケースB,Dだと意味ないよねと心の中で思ってましたが、simの実装邪魔してもあれだし本の価値をぶらすやり方は∞通り思いついてたので、ノートに書いて発声だけしときました。
最初のまともなsubmitがコンテスト開始から2時間後で、mojaがバグらせないで実装してくれてちゃんとした点数が一応出たのですが、これはmojaの実装力◎のおかげで今コンテスト一番のファインプレーだと思います。
ここでバグり散らかしてたら、もう終わってた。
チーム練、各々が独り言言ってて怖いんですが、正直基本的に誰も聞いてません。ICPCだとそれでいいんですが、マラソンだとヤバくない？となります。
時間が短いので全ての実装をこだわることとか到底無理で、むしろ数個しか改善できないだろといった感じなので、スコアに対して致命的なことだけ改善してぇ(コナミ)となってました。
とりあえず発声だけしといて大事そうなことを言われてたり言ったりしたらノートに書き留めて、必要なときに共有するように途中からしてました。
コンテスト後半（謎解き）
図書館の順番も、順番決める用の評価値を前計算しとけば焼きなましの回数めちゃんこ増やせるなーとか考えてたら、ぴーよが突然
「待って！待って！待って！待って！！！待って！！wwwwテストケースB最適解出るんだけどwwwwwww」*1
と笑いはじめました(深夜テンション)。
Bは図書館ごとに本の被りが存在していないらしいです。なんでそれ気づいた？
ここで、「もしかしてテストケースの研究本質コンテストなのでは？」となります。
順位表を研究します。全く同じスコアの団子が三つあります。
この人たちぜっっっったいテストケースエスパーしてるじゃん！！！！！！！！
自分もテストケース研究に入ります。今の実装でうまくいかないのは、本の価値が一定なB,Dのケースなので、Dのエスパーを頑張ります。
この時点で僕とpiyoはマラソンをやめて、謎解きを開始しています。
ﾌﾑ( ˘ω ˘ *)ﾌﾑ
・ 選べる図書館の個数は全体の半分。半分選んで、半分捨てる。。。 ( ・ω・)ﾌﾑﾌﾑ
・図書館ごとの収納されてる本idは、、φ(ﾟДﾟ )ﾌﾑﾌﾑ…
9 10 11 12
9 13 14 15 16 17 18 19 20 21
22 23 24 25 26 27 28 29
22 30 31
...
・φ( •ω•́ )ﾌﾑﾌﾑ......え？
隣り合う図書館でしか本は被っていなくね？
しかも一律で片方が強いやつ、もう片方が弱いやつじゃね？？
隣り合うやつで強いやつだけ取っていけば勝ちってこと？？？？？？？
実装！！！！うわあああ点数たけぇぇぇぇぇ！！！！！！キタキタキタキタキタキタキタキタキタキタ！！！！！！！
(㊟：上で述べた発見は、実はちゃんとテストケースをスクロール＆観察すると嘘であることが分かります。
コンテスト中は、この時点で B: 5,822,900 C: 1,400,620 D: 4,865,770 E: 2,243,011 F : 1,601,552 だったので、B,Dは完全に理論値が出た気分になってます。)
ここまでくると、E,Fは焼きなましが刺さるマラソン問題、B,C,Dはテストケース研究コンテストなのでは？？？となります。
テストケースCを見てもランダムな値にしか見えません。(それは、そう。)
ランダムは、おかしいだろ。（おかしくない）
時間が20分くらいしかないので、逆に完全ランダムに見せかけた最悪問題だとエスパーをします。
図書館の順番は関係ない 全日数が10^5 図書館の数が10^4 サインアップが1~10^3
→ サインアップが10^2以下の図書館は全体の10%にあたる10^3個。。。かけ合わせたら10^5かぁ。
→ サインアップが小さい順に取っていったら、実は全く被りがありませんでした とかのオチなのでは？？？（最悪）
こ、絶対これや！！！！！！！！！！！！(根拠のない自信)
実装いくぞ！！！！！！*2
とpiyoと二人でギャグ*3をしていたら、simが「なんか初期解でめっちゃ高いスコア出たんだけどwww」と言いはじめます。
どうした？
コンテスト終了10分前でのスコアは160万点、凍結前の一位は260万点。
mojaが爆速でコードに組み込んでくれます。
moja「なんか260万点くらいいくんだけどwww」
simが何をやったのかよくわからないまま、100万点スコアが上がった。そしてコンテストが終わった。
juppyの独り言を実装してくれたらしいけど、simの説明聞いても理解が追い付かなかった。多分それ、simの脳内じゅっぴーの独り言だと思う。
A 21
— sim (@i_am_karen_kujo) 2020年2月20日
B 5822900
C 5647902
D 4865770
E 5031861
F 5342764
∑ 26711218
国内15位。まだ形式に慣れるとか典型を知るとかそういうレベルの段階なのでかなりの上振れだと思う。
