JAG夏合宿2019 参加記

いつもの

Day1

JAGセット

小遅刻。ごめんなさい。コンテストは僕、への、せいかちゃんで出ました。

・Bはてきとうに書くと通る。

・Cをへの、Aをかちゃんが通す。

・Eはdfsしてmod見たらいいねってことでへのくんに書いてもらう。modとり忘れたり全然違うmodをとったりして冷えてた。まぁ無事通ったのでよし(よくはない)

・Dは中国剰余定理だけどどんなにサボっても間に合う計算量っぽいのでひたすらサボる。コピペ禁止だとサボり力は大事なのでね。AC。

・Jもやるだけらしくてへのくんが書いてAC。

・Gの実装を始めるもちゃんと詰めずにPCが空いてるという理由だけで書き始めたせいで色々間違っててひどい目にあう。書く前にちゃんと詰めような...

・Hはとりあえず平方分割でできることはわかったのでGのデバッグと並列してへのくんに書いてもらう。

・Gのデバッグが先に終わってAC。Hは計算量怪しすぎるしブロックサイズガチャかなぁと思ったのになぜか一発で通る。へのくん気持ち悪い。

・IはCHTでできるので書き始める。途中でKの畳み込みという声が聞こえてきて冷静になると簡単だったので途中で実装を変わってKが通る。

・Iが誤差で死ぬ。デバッグが世界一下手。手元でテストすれば気づけそうなことに気づけないまま10ペナと1時間を費やしたのであった。完。

・Fはこんなの凸としか思えない、三分探索でできるに決まってると主張し続けていたのですがなぜかなかなか聞き入れてもらえませんでした(証明できなかったのが悪い)。完。

ペナ差でうくにきあに負けた。ありえねぇ。あとチームのために買ってきたお菓子の9割がへのに消費されていた。許せねぇ。

こどふぉ

前回のcombinedで相当冷えたから避けるか迷ったけど「こどふぉに出なさい💢」WiFiが飛んでたから出る。

 つまらん。

 

Day2

つくばセット

教習所から参加のやむなくも含めてHeno World で出た。

・Eてんぷら、Aへの、Dやむなく

・Fの嘘を書いて落ちる。Fが一般マッチングに帰着される。完。

・やむなくから「ぼくのかんがえたさいきょうのいっぱんまっちんぐ」が送られてきてへのくんが実装する。僕は無理だろっつって止めてた(この辺わりと空気が悪かった)。

・けっこうバグるのでJを割り込んで書いたりする。添字でバグらせたりmodでバグらせたりして最悪な気持ちになるけど一応通る。

・Fが通る。は?????俺が悪かった。

・Iのジャッジが治ったので考えるとへのくんが解いてくれた。てんぷらこれジャッジが壊れる前にそこそこ考えて解けなかったのだめでは?

・途中教習で抜けてたやむなくにCを投げたらほどなくして答えが返ってきた。こわい。AC。

・Gのそれっぽいのをへのくんが書いたけど通らない。解説を聞いた感じわりと惜しい嘘だったっぽい。

 

7完でオンサイトでは1位、やったね。

 

解説を聞くとHが当然やんけという気持ちになる。ダメだなぁ。

 

ABC

完。

 

Day3

有志セット

writerの1人でした。

A ほむほむ。開始後に投げられた最初の4提出がすべて落ちて笑った

B 原案ほむ。てんぷらは演算をちょっとだけ改造した。最終的にはほぼ全チーム通してたけど序盤全然とおらなくて焦った

C これも意外とACが遅くて慌てた。難易度感覚壊れる。

D 原案。一捻りある2-SATを作りたかったんですがかなり思ったとおりになったっぽい?これも予想よりはるかに解かれず。。。直前に最大ケースが入ってないことに気づいて追加したらwriter解がMLEして制約が下がったりしてドタバタした。

E この問題好き。tester解ちゃんと書いてないけど。

F N頂点をK個の根付き木にする場合の数がケーリーの定理の一般化(?)で求まることに気づく以外のパートは簡単だと思っていた。テスター失格。

G 原案。こういう期待値計算好きだから流行ってほしい。

H 原案。UnionFind自体もマージテクが含まれるのでマージテクをマージテクする問題になっててなんか面白い気がした。テストケース生成が苦行だった。

I 数学。解説がかなり賢くてすごいなぁって言ってた。係数を全力で眺めると、

f(x) = a1*x+a2/2*x*(x-1)+a3/6*x*(x-1)*(x-2)+a4/24*x*(x-1)*(x-2)*(x-3)+...

のf(1)~f(N)を求めてくださいに帰着できて、僕はこの多項式を分割統治っぽくFFTで計算して代入するをして解いた。logが1個多いけど高速なNTTなら通る。

J 僕が通算9時間くらい考えて 2*奇数 のケースの構築を作ってそれをうまく倍々にしていく解法を生やしたらけんちょんに天才解説をされてキレた。グラフ理論でもうまく説明できるらしい。

 

解いてくださったみなさん、校正等でかなりお世話になったJAGのみなさん、本当にありがとうございました。

 

その後

東京の友達と久しぶりに会ったら地下アイドルのイベントに拉致された。イベント代は友達が出してくれたので絶対に自分は財布を開かない強い決意のもと臨んだら見事その場にいたアイドルにつられてチェキを撮ることになった。完。てんぷらはハニートラップに弱いんだよな、プーさんなので。

 

総括

コンテスタントとしては大反省(僕がまともならあと1問ずつ通っているので)、チームとしてはへのくんがやばい、writerとしては大満足、testerとしては難易度感覚さん。

いろいろと学びの多い合宿でした。ありがとうございました!!!!!

 

HUPC2019 参加記

 参加記を書くときの書き出し、迷いがち。

4月〜7月くらい

ほむちゃんが有志コンテストの作問を募集していたので入った。8問コンテストのはずなのに原案が最終的に30問くらいあつまってすごかった。ほむちゃんはday1のほうの作問も忙しそうだったりで大変そうだなぁって思ってた。交通費やばくない?って思ってたら長野県で10万円を得たので無事飛行機を取ることができた。

 

Day0

 19時くらいに北海道に着いて、ほむちゃんとジンギスカンを食べた(ツイートするのを忘れていた、ツイッタラーとしてあるまじき行為)。ほむちゃんのお家にお泊まりして、合鍵をもらってはしゃいだりday2どれくらい解かれるかなぁとか話したりした。

 

Day1

 ほむちゃんと一緒に家を出た(家が同じなのでそれはそう)ので設営のお手伝いをした。

  コンテストはそすうさとMatsudaさんの3人で出た。てんぷらは後ろから順番に読むことにして、F解けたけど実装したくないーとか言ってとりあえずBをそすうさが解いてくれたりAをまつださんが解いたりしてくれてる間にDを無証明O(1)で通したりEのインタラクティブでオンサイトFAを取ったりCの構文解析を泣きながら書いたりした。最終的にFも配るDPで実装したら意外と重くなくてAC。Gは去年のICPCのHだなぁって思ったけど実装間に合わなくて悲しかった。

 ほむ「オンサイト優勝はhupc_homunokoibitoさんです!」勝ち。

 懇親会はkenkooooooo(oの数を忘れてしまって申し訳ないんですが大は小を兼ねてほしい)さんが「AGCに出ないなんてことありますか?」って言いながらビールがんがん飲んでて面白かった。fixstarsの人事さんに「てんぷらやさん」って言われたけど僕は売られる側なんだよな。

 懇親会を途中抜けして出たAGCは冷えて悲しかったので、お酒を飲んで酔っ払ってほむちゃんに泣きついたりしてた。

Day2

 朝はちゃんと起きれた。この日は運営。

A, B Hokkaido University

 北大っぽい問題で好き。チーム戦って前半は分担みたいな戦略で臨むチームが多いので、ABが共通問題だと戦略ちょっと乱されそうだなぁと思ったりした。

C 串刺し

 実はこれは最初CPSCOのC(300点)に提案されて全力で止めた問題。HUPCでもBに置かれかけて全力で止めた(この過程でほむちゃん原案の問題がday2から消えたりした、ほむちゃんごめんね)。実際そんなに解かれなかったし証明込みで通したチームってなるともっと少なそう。問題文がてんほむになったのはつぶあんくんの優しさです。

D Two Colors Sorting

 原案がO(N^2)だったのでO(N√N)になるよって言った。典型の組み合わせで綺麗で好き。bitsetを落とそうとしたらPythonが不可能になったのにbitset自体はど愚直以外何かしら工夫すれば通りますになってしまって厳しかった。C++許さねぇ。本番もbitsetで通したチームのほうが多かった気がする。ちなみに2つを組み合わせるとさらに速くなる→http://noshi91.hatenablog.com/entry/2019/07/16/213823

E Jam

 原案出しの終盤にダイクストラとかそういう感じの問題ないねってことで生やした。想定は拡張ダイクストラだったけどパンの処理の仕方はいろんなやり方があるみたい。つぶあんくんが色々投げてくれたからテストケース作りはちょっと頑張って、負辺が絡むような操作をするとだいたい落ちるはず。意外と評判がよくて嬉しい。

F MOD Rush

 原案てんぷら、問題名と問題文と解説ほむっていう分かりにくいてんほむ。超シンプルな設定で解法に調和級数出てくるの面白くないですか?(自画自賛) もともとEとFが逆だったけどこっちのほうが難しい気がして入れ替えたのにこっちのほうが解かれた。難易度評価難しいね。beetさんに8分で解かれて笑った。

G Tree

 もともとK=2固定だったのがTester解書いてる途中でK=300でできることに気づいたので変えた。O(NK)の木DPあんまり問題例ないよねということで。原案はつぶあんくんなので「数え上げが出たらてんぷらだと思う」って言われるたびに違うんだよなぁって思ってた。 

H Revenge of UMG

 もとの問題はこれ。テスター引き受けたときにN=100000で解けないか考えてそのときは無理だと思ったんだけど2ヶ月くらい経ってから考え直したらできたので出した。

 '?'はbitset解を落とすため(?がないと1番出現回数の少ない文字を固定するとかするとすごく速い)と、なんとなく最終問題っぽい見た目にするために足されたあまり本質ではない蛇足。

 

 ということで結果としてかなり後半の問題に関わることになっちゃったので、「てんぷらの好きな問題を集めました」セットになってしまった*1。The Way(双子+tatyam)に2時間切りで全完されたのはちょっと悔しかったけど概ねいい感じの難易度になったっぽくてよかった。

 終わった後ほむの家にもどってちょっと昼寝をして寿司を食べた。北海道は美味しいものが多い。

before

 after

 

Day3

 寝坊すれすれで起きて、ほむちゃんと涙のお別れ。大阪に帰ってきたらクソ暑くてキレた。でもたこ焼きはうまい。

 

 

最後に

 今回は3時間コンテストのcontestantとjudgeを両方できてかなりいい経験をさせてもらえました。オンサイトで関わってくれたみなさん、コンテストに出てくれたみなさん、泊めてくれたほむちゃん、ありがとうございました!!!

 

 

 

 

*1:てんぷらの好きな問題を集めるとHeno Worldが冷えることが知られていて、得意分野がまるでずれてるのがレート以上に結果を出せている理由の1つかも...?

ICPC 2019 国内予選 参加記

 ICPC国内予選に出ました。メンバーはへのこーどとやむなくと僕です。僕はM2なので今年が最後の挑戦です。

 結果は6完3位でした。

 

コンテストの流れ

 コンテスト開始もなぜかコーチが問題文を印刷できなくてつらい。へのくんが画面の右半分でテンプレを書いて左半分でやむなくがAの問題文を読む。さすがにすぐできるのでやむなくが書いてAC。

 この辺で問題文が印刷できる。Bはすぐにできたので僕が書く。AC。

 へのがCを書く。ちょいちょい詰まってたけどなんだかんだすぐに通る。

 やむなくがDの貪欲を書くけどサンプルの時点でダメだねとなる。DPじゃんってなって僕が書いてサンプルは合うけどこれも嘘解法だねってなる。とりあえず絶対に正しいO(N^3)は書けるので書いてみるけど計算が終わらなさそうで、累積和っぽくやればO(N^2)になりそうってやむなくに言われて確かにってなる。なんかこの間にへのやむでFの考察ができてたみたいで、「へのがFを書く→てんぷらが割り込んでDのバグを修正するも合わない」*N をする。この時間あたりにTLでは「へのわーるど冷えてるか〜」とか「潜伏か?」とか言われてたらしくて面白かった(20位、別に冷えてはなくない?)(いや学内5位なので通過圏外なんですが)。

 Dがやっと治って提出してAC。FもDの直後に書き終わってちょっと実行に時間はかかるけどAC。20位→5位に急浮上。

 へのが頑張ってEを書く。45分前くらいに書き終わるけど無限時間かかる&サンプルも合わない。ちょっと高速化してみるけど全然ダメそう。まぁとりあえず通過はしそうだしこれまでかなぁってなる。

30分前への「書き直します。」

 4分前への「書けました。」

 4分前への「サンプルが合いません」

 2分前への「あっここミスってる、直した。サンプルチェックする時間ないしとりあえず出します。」

 1分前への「最初のケース通った!」

30秒前への「通った!!!!」

 

神か???

 

反省

 奇跡的なブザービートで成功した感出てるけどてんぷら仕事してなくない?Dを普通に通してればもっと余裕をもってEを書けてたと思うので個人的には大反省。

 模擬国内も国内予選も後輩に介護されっぱなしだったのでアジアではいいところ見せたいなぁ。夏を伸ばしてもらえたのでポエムはまだ書かなくてよさそう。

 

  あと今年は京大から4チーム通過したっぽい。嬉しいね。

 

ICPC 模擬国内予選 2019

 

2019/Practice/模擬国内予選 - ACM-ICPC Japanese Alumni Group の参加記です。僕は模擬国内に参加するのは初めて。結論だけ書くと優勝した。

コンテストの様子

 へのくんがいつものを書いてる間にやむなくがA、僕がBを読む。Aはまぁできるのでやむなくが書く。AC。Bもうまいやり方はありそうだなぁと思いながら脳死01BFSを書く。AC。10分くらいかかってるのちょっと遅かったかも。

 へのくんがCが解けたらしいので書いてもらう。2WAしてAC。2回目のWAはサンプルで落ちてたらしいのでそこは反省?なんとなく順位表を見ると最速3完だったので記念撮影。CはFAだったらしい。

 そのままやむなくがDの実装に入る。僕は、rotateは最初だけでいいと思ってたけどダメでeraseのときは工夫する必要がありますみたいな解法を聞いて、「実はそのケースは他で考慮できてることになってたりしない?」とか「すげぇ本当だ、たぶんあってそう、わからねぇ」とか返す係をした(つまり邪魔では?)。1発AC。すごい。DもFAだったらしく4完も最速だったのでまた記念撮影。調子いいねとかまぁでもうちのチームは序盤勝負だしなとか言ってた。

 やむなくくんがDを書いてるときにへのくんとEの相談をする。3列について、どの2列についても両立できるなら3列でも両立できる気がするって話になって、てんぷらは「ほんとかなぁ。嘘では?」とか言ってた(無能)。反例が全く作れないことからできることがわかって、だったら半分全列挙で終わりですとへのくんが言うので、僕は「確かに、すごい」って言った。そのまま実装もへのくんがしてAC。5完も最速だったので例によって記念撮影。

 へのくんがEの実装をしている間にやむなくと相談してFもGも解けた気持ちになる。Eの実装が終わった後へのくんにFの説明をして書いてもらうことにする。僕「前後|Q|-1文字ずつ残しておくとよさそう。一致判定どうしよう。」への「Zアルゴリズムでできます。繰り返しの実装が文字数短い間は二分累乗みたいに足したほうがよさそうで大変なんですけどどうしましょう。」僕「全部二分累乗で実装すればmergeだけの実装でいいじゃん」みたいな感じでどんどん実装がよくなる。これぞチーム戦。とはいえバグって、必死のデバッグをする。いろいろ直すとサンプルが通る。やむなくが作った強めのテストケースを試すと1つも通らない。再びデバッグ。色々直してデバッグもほとんど終わった頃に順位表をなんとなく見ると、6完チームが出てきてて3位に落ちてたものの10数分以内に通せばペナ差で逆転できることに気づいたのでへのくんを煽る(最悪)。無事書き終わって、やむなくテストも全部通過したので出す。通る。やったぜ。

 この後30分くらいあったので一応Gを書こうとするけどそもそも実装方針があまり良くなかったりで間に合わず。

 結果はまさかの全体1位。めちゃくちゃ嬉しいけどあんまり実感はなくて、正直なことをいうとこういうのは本番でやりたい(それはそう)。

 

反省とか

 A〜Eまでが1時間ちょっとで通って、間でパソコンが空くこともほとんどなかったのはとても良かった。てんぷら仕事してないけど。

 Fのデバッグも全員でコード読んでバグ見つけれたり、強めのケース試してWAを防げたりしたのでよかった。

 個人的にはかなりの時間考えてたHがまったく歯が立たなかったのが悔しいけど、全体としては大成功だと思う。

 

 とはいえ模擬だけ勝っても何にもならないし、むしろこれで国内予選で失敗したら笑えないギャグもいいところなので、国内まではあと2週間もないけど気を引き締めて本番に臨みたいね。 

CPSCO2019 参加記(後半)

 これの続きです。

tempura0224.hatenablog.com

 

Session2

 運営なのに起床に失敗してコンテストに10分遅れて到着。僕以外のチームメイトが茶茶無だったので実装詰まったりで困ってたら申し訳ないと思いながら状況を聞いたらABをACしてCも実装に入っていますって返ってきて超頼もしかった。

 Dをくろねぇさんと2人で考えることにして、こういうゲームはとりあえず小さい数で実験するとよくて、みたいな話をしながら紙に書き出していくと性質が見えて証明もできたので書いてもらう。4完最速だったっぽい。

 そこからがつらくて、500が一向にわからないのでとりあえずチームメイトに普通の最小全域木問題の説明をしたりする。

 よくみると600はいつもの2乗の木DPなので書く。入力し忘れとかいう意味のわからないバグに気づかず頭を悩ませるもそこだけ直すと割とすぐに通る。これも解き終わった後軽い解説をしたりしてた。

 500全然わからないなぁと思っていたら終了15分前くらいにけんちょんチームが700を通したので考えることにするとすぐに燃やす埋めるなことに気づく。ただ実装がちょっと大変で詰めきれなくて終了。500にこだわらず700から考えてれば間に合ってそうなので完全に戦犯。序盤を速攻で通してもらって後半を処理できないのはねぇ...。

 

Session3

テスターだったのでちょっとだけコメントをします。

A. ASOKO

もともと問題名「OSAKA」で少し別の問題だったんですが問題名をAで始めたくなったので変更されました。新しいほうを考えたのは実は僕です。

 

B. Balloon

今回のキャンプでは運営人数の都合で風船配布はFAのみに行われました。

C. Camp Reception

この問題とBは問題名にこだわっていなかったんですがたまたまBとCで始まったので全問題の頭文字を揃えることになりました。

D. Decode RGB Sequence

原案はスタンプの文字数がもう少し多かったんですがRGBの3文字にしてみたら性質が超綺麗だったのでこうなりました。「条件をみたすN文字の文字列は何通りあるでしょう?」でも解くことができます。

D問題は初心者でも手を動かして考えられる問題にしたかったそうで、実際うまくいっていたんじゃないかなぁと思います。

 

E. Enumarate Xor Sum

ちょっと問題名が怖いですよね。数列にxorでどうこうする問題で素朴な設定を考えるとだいたいちょっとググるとでてきてつらかったです。2人で相談しながら最終的にここに着地しました。DEあたりの難易度調整がたぶん僕のテスターとしての仕事の9割くらいだったと思っています。

 

F. Flexible Permutation

数え上げ大好きおじさんなのでかなり好きな問題です。2乗で解けることに一切気づけなかったので数え上げ大好きおじさん失格です。箱根駅伝っぽくも解けますがswap DPみたいな感じでやるのがわかりやすいと思います。

 

G. Grand Election

テスターの僕が48のオタクだったことは有名ですが原案も問題文も全部けんちょんです。グループ名にだけ口出ししました。

ちなみに僕もコーナーケースを片っ端から踏みました。これ難しいですよね。

 

Session4

 個人戦ですがオンサイトでは負けられない感じだったのでちょっと緊張しました。

冷静に計算するとAのオンサイトFAが取れます。そのまま問題文を丁寧に読むことでBのオンサイトFAも取れます。Cは一瞬N/3チームのマッチングに見えて思考が停止したのでFAが取れません。DはDから解いたやむなくくんが5分くらいで通していました。

 Eは色々実験すると(正しい方の)貪欲法に気づけたので書くとオンサイトFAでした。オンラインのFAも並行世界の僕(arupmet)が取っていました。

 Fは全然わからなくて残り5分で再帰で書くと綺麗に実装できることに気づいたのでtextで解法を提出して諦めました。

 

まとめ

 準備期間も人数も十分とは言えなかったにも関わらず大きな問題なく終えることができて本当に安堵しています。会場その他の運営はほぼはにーまさんが1人でやりきってくださったので頭が上がりません。競プロイベントの参加経験がないにも関わらずすごい細かいところにまで気が回っていてすごかったです。

 作問者としての反省はやはり解説の準備が不十分だったところだったかと思います。あとテストケースを当日に作り直すのは超不安になるのでやめましょう。

 関西競プロerとの交流もかなりできて楽しかったので次回もあるのならまた関わらせてもらえたらなぁと思います。

 参加してくださった皆さん、そして企画してくださったはにーまさん、本当にありがとうございました!!!

 

CPSCO2019 参加記(前半)

 運営として参加しました。その辺も含めていろいろ書きます。

〜0日目

 はにーまさんの企画を見て面白そうだと思ったのと、黄色くらいがいるといい感じに力になれるんじゃないかと思って運営として応募しました。期間が1ヶ月しかなかったのでかなりバタバタしましたがなんとか問題を完成させました。2日前に問題が変わったり1日前に配点が変わったり当日に制約が変わったりしました(は?)。

 

Session1

writerをしたのでそれぞれの問題について振り返ります。

A. Ajihon 

・O(1)算数

・合宿に関係のある設定

・タイトルがAからはじまる

を条件に作りました。切り上げ処理が必要だったりでほどよい問題だったんじゃないかと思っています。226人が解いてくれました。

B. Beautiful Harmony

・文字列系

・s[i]-'a' とかをする感じ

・タイトルがBで始まる

を条件に考えていると新元号の英語がこれらしいので決まりました。reiwaに対する答えが”Yes”になる問題を作れてよかったです。

ここまでは参加者全員解けて欲しいなぁみたいな気持ちでした。

C. Coins

この問題は実は1番最初につくりました。evimaさんリスペクトの全探索です。

この手の全探索はかなり基本問題だと思っているんですけどそのせいで逆にAtCoderでは全然見ない気がしていて、ずっとどこかで出したいと思っていたので出しました。

難易度という意味では茶色〜緑くらいが対象だったんですが、next_permutationで組み合わせを全列挙できることは黄色レベルの人にも知られていなかったりして当初の予想以上に広範囲に刺さる問題になりました。

 

D. Dessert Planning

この問題はかなり直前にできました。具体的にはコンテスト7日前です。それまで入れていた問題があまり面白くないなぁと思っていたら生えたので入れ替えました。

C問題が比較的プログラミングよりだったので、D問題については

・プログラミングの知識がほぼなくても解ける

・とすると一般項が数文字で書ける数え上げとかかな

・でも階乗逆元はつらいからnCkはダメだな

みたいな条件で考えるとまぁただの階乗か累乗だよねって感じでできました。

てんぷらセットで1問も1e9+7を置かないわけにはいかないのでね。

ここまで(と後半の部分点)が〜緑パートのつもりです。

 

E. Exclusive OR Queries

ならし計算量の問題あんまり見ないな、なんかつくるか、で作りました。

もともとは (値, 個数) をpairで持って工夫する系で考えていたんですがxorという天啓が降ってきて個数を持つ必要がなくなりました。

setでがちゃがちゃする系もあんまり見ないしひょっとするとそんなに解かれないんじゃないかなと思っていたらやっぱり解かれませんでした。lower_boundの罠にはまる人もレート問わず一定数見かけたので出したかいがありました。

Pythonがほぼ不可能なのは申し訳なかったです(これは僕じゃなくてPythonC++のsetと同じものがないのが悪い)。

 

F. Fruits in Season

にぶたんで何かって思ったら生えました。最初は絶対値じゃなくて直線だったけど探すまでもなく射撃王だったので絶対値にしてみたら判定パートが面白くなりました。

この判定パートは僕は難しいと思っていたんですがコンテストではEとほぼ同じだけ解かれてびっくりしました。Fがこれだけ解かれてEがそんなに解かれないのAtCoderっぽいなぁっていう話をしていました(これはAtCoderに対する個人的な偏見です)。

 

E, Fの2問が水〜青向けくらいの想定で、オンサイトだと実質ボス問になるのかなぁと思っていました。

 

G. Game with Division

√X で分けると幸せになれる問題を2日くらい考えていると突然できました。

個人的にはかなり好きな問題です(計算量O(N√X logX ) ってけっこうレアだし)。

個人的にはもう少し簡単な印象だったんですがコンテスト中にACしたのは黄色以上だけだったみたいです。難易度判定難しい。最初GとF逆じゃない?とか思ってた。

 

H. Highest and Ends

勉強用セットの最終問題って何がいいんだろう、高度典型か、うーん分割統治!で生やしました。個人的にも数列の分割統治の問題をほとんど解いたことがなかったので頑張って作りました。そしたら開催1週間前にGCJのR1Bで分割統治で解ける問題が出たり、3日前のえでゅふぉでdistinctにしただけの問題が出たりして相当慌てました。

えでゅふぉで出てしまったせいで問題設定が少し変わって(もともとmaxA_i だったところを A[m] に変えた)、結果として難易度がさらに高くなりました。

解かれないだろうなと思って出したんですけどコンテスト中のACが3人しかいないとは思いませんでした。

 

GとHにはそれぞれ部分点(300)をつけていて、基本的なDPとよくある累積maxだったので、〜緑対象のほどよい問題になったと思っています。実際オンサイトでもオンラインでも多くの参加者が部分点にチャレンジしてくれていました。

 

 

コンテスト全体としては、AC人数がちゃんと崖のない降順になったり最初の全完が130分(150分中)だったりと思っていた以上に綺麗な結果になってしまって、正直めちゃくちゃびっくりしました。できすぎだと思っています。clarもほとんどなく平和に終わってくれてすごく安心しました。

 

初心者向けにしては難しいんじゃないかという意見もあるとは思う(というか実際いただいている)んですが、session1については実質 1-2-3-3-3-4-5-6 のつもりでいて、競技プログラミングの勉強合宿として初心者に対して紹介したいのは300点くらいのところなので個人的にはこんなもんじゃないかなぁと思っています。

どちらかといえば解説を300点まわりにもうちょっとフォーカスして準備しておくべきだったので、そこの準備不足については反省しています。 

AGC033

その日の晩のAGCで橙に上がっていいことづくめの1日でした。これについても後日どこかに書くかもしれません。

 

 

writer自分語りでバカみたいに長くなってしまったので2日目以降については記事を分けることにします。では。

 

Heno_World! practice #2

今回はfour_t たちが Tehran2017(four-t practice 2019 #06 - Virtual Judge)でチーム練をすると聞いたので突然殴り込み

 

コンテストの流れ

 開始ちょっと前にへのが去年数問解いてることが発覚する。おいおいって言ってたらやむなくが寝坊で来ない。まぁへのが見ちゃってる問題があるならチーム練として100%は機能しないしやむなく待たずに始めちゃえばいいかってことで北大に合わせて定刻通りスタート。

 僕が前半、へのが後半を読む。Aを読む。解く。AC。Bを読む。 1-indexの奇数桁目は0-indexedだと偶数桁目なことに気づけずちょっとバグらせる(初心者か?)けどすぐに通る。順位表を見るとHが解かれているのとどうやらへのが解いたことあるのもAとHだったらしいので僕がそのままHを解く。配列をinf初期化したつもりがしていなくて1WA。この辺で集中力が無なことに気づく。

 へのくんがKを書きたそうにしているので書いてもらってその間に残りの前半の問題を読む。Eが簡単だったのとKがだめそうなので概要を伝えて実装してもらう。AC。CDFが幾何虚無幾何で完全に萎える。

 Gの概要を聞いたら解けたのでこれも実装をへのに投げる。なんか変数をintにしていて1WA。デバッグ出力が残っていてもう1WA。実はまだintが残っていてもう1WA。これ今回2人ともダメではみたいな気持ちになる。

 Cは境界全探索のいつものなのでへのに実装してもらう。てんぷら実装を放棄しすぎでは?僕が考察1個飛ばしていて全然合わなくて厳しい気持ちになる。このあたりでやむなくが来た気がする。

 しょうがないのでとりあえずDを書くけどこれも全然合わない。よく読むと誤読に気づく。DFSを書きかけて冷静になるとnext_permutationでいいので書く。AC。

 Iもやるだけなんだけど構文解析(ってほどでもない)パートが地味に面倒で泣きながら書く。区間に重複ないやろへらへらって適当に書いて提出したら当然あるので落ちる。問題嫌いすぎる。

 Cの考察漏れにやむなくが気づいてへのが直してAC。やむなくくん最初からいてくれ(懇願)。直後にIのバグも取りきれてAC。またデバッグ出力消してなくてWAをもらうやつをやったりした。

 あとはへのがK粘ってたけど結局TLEが取れず。悲しいね。

 結局8完でvjudge内では1位。

 

反省

  • デバッグ消し忘れとかintとlong long とか虚無ペナを出しすぎ。っていうか全然集中できてなかった気がする。
  • やむなくくん起きて。
  • てんぷらも実装をしなさい(定期)。
  • 最低でもあと1問+速度は必要じゃないですか?

 

チーム練で他チームと競えるの楽しいね。次はちゃんと3人で出て勝ちます。