Heno World practice 2020/02/04
久しぶりにチーム練をしました。
今回はQWE_QWE, The atamaと合同で、コンテストはこれ
僕がIあたりから、やむなくがEから?読む。
Iは見た瞬間2部グラフの最大独立集合だけどさすがに1問目にフロー書くのはおかしいので一旦保留。
Eをやむなくが解いてへのくんが書いてAC(0:07)。
実装キュー[I]
Dがすぐ読めてすぐ解けたのでへのくんにパスしてAC(0:09)。これは普通に自分で書けばよかった。
実装キュー[I]
この時点でちょっと通ってるCをへのくんが考えてそのまま書いてAC(0:14)。確かこの頃Mが解ける。
実装キュー[IM]
保留してたIをへのくんにパス。なんか写経ミスってつらそうだったけどそこそこすぐ治ってAC(0:35)。この頃Jが解けるけどどう考えても面倒なので放置。
実装キュー[MJ]
僕「MはUnionFindでできるけど僕が書いたら添字で頭おかしくなりそう、Aはわりといつもの全方位っぽい。好きな方書いて。」
へのくんがMをわりとすぐ通す(0:52)。すごい。その間にAの実装方針をつめておく。
実装キュー[AJ]
全方位木DPをライブラリ化しているらしいへのくんにAをパス。バグってたらしい(は?)。まぁでも無事通る(1:19)。この頃僕がL、やむなくがBを解く。
実装キュー[BLJ]
へのくんに6問連続で実装させていて少し申し訳なくなったので僕がBを書く。AC(1:33)。へのくんがFの考察を終えてた。
実装キュー[LFJ]
Lをへのくんに投げる。1WAの末AC(1:48)。やむなくと2人でGとKを解く。
実装キュー[FGJK]
へのくんがFを書く。1WAしたけどそこそこすぐ通る(2:10)。
実装キュー[GJK]
へのくんがGを書く。通る(2:31)やむなくがHがシミュレーションするだけなことに気づく。
実装キュー[HJK]
てんぷらがバイトに行くために離脱。へのくんがHを書く。通る(3:02)。
実装キュー[JK]
京阪で座れたので降りるまでには書ききれるだろうと思ってKを書き始める。書き切れたけどWA。終わった。。。
乗り換えでコーディング不可能になったのでへのくんに実装をパスしてJを書いてもらう。AC(4:36)。
やむなくがバグを見つけて、パソコンを触れるようになった僕が直してAC(4:58)。
滑り込み全完。
まとめ
・僕が途中離脱してなかったら全完タイムもう少し縮んでそう。
・へのくん以外も実装をしような
・へのくんがすでに記事を書いてたことにこの記事をだいぶ書いてから気づいた。まぁ僕視点ということで...
ABC135 E Golfのパターパート
・偶奇によってどうしようもないことがある。
・必要な手数は基本はceil(距離/K)で、偶奇によって+1が必要なことがある。
・残り2手までは適当に近づく。
あたりは一旦いいとして
・今いる地点と目標地点の距離が2K以下
・かつ偶数
のところから最後2手でどうやってカップインするかという話。
考察1
上の2条件が満たされているとき必ず2手でいける。
証明: そうじゃないと困る。
考察2
(X, Y) = (x+y, x-y) として座標変換(いわゆる45度回転)すると、(x,y) からマンハッタン距離がちょうどKであるような点の集合は変換後の座標では (X±K,Y±K ) の4点を頂点とする正方形になる。
証明: 略
以下では今いる地点を(x1, y1), ゴールを(x2, y2) とし、
2点の座標変換後の座標を(X1, Y1), (X2, Y2) とします。
また最初の2条件は満たされているものとします。
考察3
(X1, Y1), (X2, Y2) を中心とする2つの正方形が共有点をもつとき、
(Xi ± K, Yj ± K) と表すことのできる共有点が存在する。
証明: 共有点をもつ正方形の図をいくつか書くとわかる。
考察4
(Xi ± K, Yj ± K) と書ける点は逆変換でxy平面に戻しても格子点(xy座標がともに整数)である。
証明: 読者への演習問題とする。
つまり
①45度回転
②(Xi ± K, Yj ± K) と書ける頂点を全探索
③どれかが共有点になってる
④③を45度逆回転で戻した点はちゃんと元の座標でも格子点になってる。
⑤そこが最後から2手目で行くべき点である。
めでたしめでたし
まとめ
完全な解にはいたれなくても全探索等が現実的な時間に収まりそうなところまで持っていけたらあとはパソコンにやらせちゃうのはかなり有効(他の問題の例: AGC041-C, エクサウィザーズ2019-F)
ICPC 2019 Danang Regional 参加記(コンテスト編)
それ以外編はそのうち書きます。かなりTLで実況してくれてた(本当にありがとうございます)のでその情報もだいぶお借りしています。
コンテスト
- 入場が遅れて15分遅延。問題文が配れなくて15分遅延。問題文が配り終わって10分早まる。結局20分遅れでコンテスト開始。僕が環境設定。やむなくが後ろから読む。へのくんがトイレに行く。
- やむなくがMを通す(0:07)。
- Lがフローでできるらしい。他に書けるものもないのでとりあえずトイレから帰ってきたへのくんに書いてもらう。
- 通り始めてるIをやむなく、Dを僕がやる。やむなくがIを解けたのでへのくんと代わって書く→WA→こんなの落ちるわけなくない?変な位置に空白を出力していたので関係ないと思いつつ直して提出→WA
- Iの誤読を疑う。Dも解けてたのでとりあえず書いて出す→WA。今まで応援ありがとうございました...。(わりとマジで終わったと思った)
- Iは誤読でした(重要な知見としてインタラクティブで誤読をするとデバッグでの回答も間違えるのでどんなサンプルでもあってしまう)。修正してAC(00:58)
- Dは入出力高速化をテンプレで貼ってたのにcinとscanfを混ぜていたからでした。修正してAC。
- Lもそこからすぐに書き終わる。これは一発AC(00:64)。一旦4位に浮上して安心はするけど他の4完チームとのペナ差が異常(それはそう)。完数で勝たないとダメなのしんどいなぁ。
- Hは全探索やるだけ。へのくんに実装を投げると1回TLEしたけどすぐに直ってAC(1:24)。2位に浮上したらしい。ペナがやばいので6完する手前では4位か5位くらいまで落ちてた気がする。
- Gがなんとなくできたので提出。WA。やむなくにコーナーケースを無数に指摘されて1個ずつ潰す。AC(1:41)。このタイミングでも2位だったらしい。
- やむなくがK、僕とへのくんがAをやる。N<=14とか書いてるしbitDP系だよなぁ、どう考えても遷移できませんが...。突然ギャグ(制約はそこまで小さい必要がなくて実は10^9でも解ける)なことに気づく。AC(2:06)。ここで首位浮上。なんかこの辺りから現地のスタッフが僕たちの動向を監視するようになる(提出の気配を察するとビデオカメラが向けられるようになる)。AをACしたときの動画はFacebookにあがっています(フリ素なので積極的に公開はしないけど)。
- Kをやる。相談していると1個の挿入が2手でできるから198手は簡単なことがわかって、あと4個分減らす必要がありそう。へのくんがいい感じの長さ5の増加列or減少列があるといいことに気づいて、さすがにないわけがなさそうなので(実はこの方針だとギリギリだったことがコンテスト後に判明)へのくんが書く。少しバグっていて2WAを出すもののAC(2:51)。再び首位浮上。このあたりからカメラが1台三脚で目の前に置かれるようになる。
- Fに行く。やむなくが微分係数の小さいやつから貪欲に足していくとよさそうと言う。完全に正しそう。へのくんが実装に入るけどこのシミュレーションどう考えてもつらい気がするのでもう少し考える。シミュレーションが終わったときの様子を考えるとにぶたんで簡単に実装できそうなことに気づく。ちょうどへのくんの実装がバグったので交代して書く。わりと長いジャッジの末AC(3:39)。この時点でWFをほぼ確信する(結果的にはここで1位が確定していた)。
- 凍結。どのチームに並ばれてもペナ差で勝てそうなことに気づく(7, 8, 9完が最速だったあたりで逆転していたらしい)。優勝では?という気持ちになる。
凍結したかー
— そすうさ(素数うさぎ) (@wk1080id) 2019年12月6日
へのわもう一問解けば安心だけど pic.twitter.com/9ptJ5EdHK8 - Cの解法が生えたので実装する。嘘やんけ。おいおい。任意mod NTT をすれば解けそうではあるけど...。
- 問題文が長い&&一目やばそう なBを一応へのくんとやむなくで読み直すと超やるだけだった。書く。当然のようにAC(4:31)。勝ったなガハハ。
- ここから11完が出るとも思えないけど何もしないわけにもいかないのでEをちょっと書くけど当然終わらず終了。終盤はこのままだとYes/No で1位から一度も落ちないことに気づいて9完していそうなチームの応援をしていた(治安さん...。)
結果発表
優勝でした。
通ってなくても1位の状況でダメ押しのYesをするHeno Worldがみたーい!
— 迷路 (@pazzle1230) 2019年12月6日
— やむなく (@yamerarenaku) 2019年12月6日
勝因(?)
- 破滅ノルマを序盤に消費できた。序盤に破滅したのはひどかったけど3連続ACで勢いに乗れたのも確か。
- F問題で実装に入ってからも横で考察を続けて結果実装を軽くできた。横浜ではCの実装に入ったあと他の問題に移ったらCでバグってそのまま終了して終わったのでその反省をいかせたと思う。
- 他チームが破滅した(本質)。実はやるだけのBとか制約が意地悪なだけのAとかが結局ほとんど解かれなくて、これがICPCなんだなぁとなった。
- そもそも強いチームが多くなかった(本質)。
最後に
コンテストが終わってTL開いたら想像以上に盛り上がっていてびっくりした、本当に応援ありがとうございました。WF頑張ってきます。現役が伸びたのでJAG入会にはもう少し時間がかかりそうです。
Heno World practice
久しぶりに5時間コンテストをやったので。
2018-2019 Hanoi Regional をやりました。https://hanoi18.kattis.com/standings
コンテストの流れ
やむなくが前から、てんぷらが後ろから読む。へのくんはテンプレとかを書き次第真ん中くらいから
C AC(12:24)
へのくんがテンプレ書いたあとそのまま書いてた
H AC(20:38)
後ろのほうを読みながら順位表眺めてたらちょっと解かれてたので読んだら解けた
D WA, WA, AC(72:20)
Iが包除原理をしてくださいと問題文に書いてあるがよくわからないのでへのくんにぶん投げる(まじでごめん)。へのくんが実装を始めるも辛そう。やむなくとDのインタラクティブを考えると普通に中間値の定理からできるね、となる。適当に書いて出すとWA。オーバーフローっぽい何かに気づいて出しなおしたけどWA。冷静になってクエリ数を数えると1回オーバーしてました(完)。最後の処理を丁寧にしてAC。この辺の戦犯度合いやばいね
I TLE, WA, AC(97:41)
結局へのくんが解いてくれました。bitDP的な感じなんですけど最初のは計算量がやばくてTLEしたのでちゃんと必要なところだけ残すようにしたらWA。原因はintのオーバーフローでした(完)。なおしてAC。ここまでがかなり辛かった。
B TLE, AC(116:01)
僕とへのくんがI詰めたりしてる間にやむなくが実験しまくってGrundy数がこれな気がしますって見せてきたので、2人で証明を試みるとできる。気づいてしまうと実装はないので適当に書く。適当に書きすぎて二分累乗でk/=2を忘れてTLEを出す。は?競技プログラミングをやめろ。なおしてAC。5完時点で全体最速ではあったがペナルティがinfで厳しいねという気持ち。
L WA, AC(147:44)
Iの実装を終えたへのくんがLの考察をしてなんかいい感じらしいのでちょっと相談して考察を詰めて書いてもらう。わりとすぐ書けててすごかった。配列外参照で1WA出したのでめちゃくちゃはすごくなかった。
J AC(156:40)
Lをへのくんに書いてもらってる間にやむなくと相談する。完全グラフと輪っか以外にないだろとか言ってたら完全2部グラフでもできることにやむなくが気づく。色々書いてみるが他はダメそう。証明もできたつもりになったのでLが通ってすぐやむなくが書いてAC。
A 4WA, AC(259:56)
最小費用流でいいことは分かっていたがライブラリの写経とかが面倒で後回しになっていたのをへのくんに書いてもらう。書き終わって、手作りしたテストケースもちゃんと通ったが投げてみるとダメ。細かい修正をいろいろするも全然合わなくてだいぶ経ってからフローの復元がバグってたことに気づく。僕が書き直してなんとかAC。Aをバグらせてる間に他のチーム(本番のオンサイト優勝チーム)に先に8完されて焦ってたけど結局ペナ差で逆転して1位になる。まぁ本番ではネットワークがぶっ壊れてた時間があったらしいのであまりあてにならない。
G 3WA, AC(295:47)
Aの実装待ちの間に、辺数が多いほうは完全グラフでできて(こっちは証明もできた)、辺数が少ないほうはトリボナッチでどうにかなりそうな気がしていたので書いてみる。だいたいあってそうなので出してみるとWA。後者の辺の数が全然おさまってないことに気づく。フィボナッチじゃ頂点数足りないよなぁ→足りるやんけ!となって急いで書き直して提出してAC。4分前AC、心臓に良くない。
結局単独9完の1位でした。やったね。
反省
・全体的にペナルティが多すぎる
・てんぷらIできないの何?
・フローの復元の実装がやばそうなのにもう少し早く気づくべきだった。
・9完はえらいのでRegional本番もこれをやろうね
AtCoderで赤になるまでにしたこと
赤コーダーになりました!!!!
— てんぷら (@tempura_cpp) September 21, 2019
チュートリアル修了!!!!! pic.twitter.com/WMPzYqnfrL
ひとつの到達点なので。
自己紹介
・京都大学理学研究科M2(数学系)
・公立高校出身
・ぎりぎり数オリ勢(春合宿参加1回で数オリ勢名乗るのおこがましい)
・競技プログラミングも含めてプログラミングを始めたのは2018年1月から(当時B4)
したこと
問題を解いた
Solved By tempura0224
— てんぷら (@tempura_cpp) September 23, 2019
TopCoder: 19
CodeForces: 432
AtCoder: 1076
AOJ: 181
yukicoder: 95
Sum: 1803
https://t.co/JyHa0kaQ4F
1800問くらい。
作問
今年の春くらいから伸びた理由の1つだと考えていることその1。
yukicoderで数え上げセットを作って以降CPSCOやHUPC、JAGで出題させていただいたりと作問に関わる機会が増えました。
僕は解法を先に決めてから問題をつくることが多くて、その過程で解法の持つ性質だったりどこまで抽象化できるかを考えるようになりました。例えば、答えを決め打つ二分探索が想定解の問題を作ろうと思うと、その解法が適用できる問題は「そのままだと難しいがYes/Noの判定なら高速にできて、Yes/Noに単調性(ある境目が存在してそれ以上ではYes, 未満ではNo など)がある」という性質を持っていることが分かっている必要があります。あるいは「セグ木で問題をつくりたい→セグ木はmax/minとかsumだけじゃなくて一般にはモノイドが乗るらしい→具体的にどんなことができるだろう?」と考えたりです。要は作問をすることでその周辺に対する理解度がかなり上がることがあります。テストケースを作ろうとするとコーナーケースや嘘解法も一通り考えることになるので、それもかなり良さそう。あともっとわかりやすく自分の作った問題がコンテストに出ると瞬殺できるのでお得です(直近2回のコンテストの勝因はこれも大きい)。
実際に出題する/しないはともかくとして、自分で問題を考えて自分で解いてみる習慣はかなりいい訓練になるかなぁと思います。実際にyukicoder等で問題を出したくなったらテスターは暇な限り引き受けるので気軽にお声掛けください。
ICPCのチームを組んだ
伸びた要因その2。チーム練はいいぞという話。
・シンプルに練習時間が増える。
・自分とタイプの違う人と組むと今までなかった視点に気付けたりする。
・国内予選通過とかWF進出とかわかりやすい目標があると精進もはかどる。
ただ僕はかなり環境に恵まれている自覚はあって、これは誰にでも通用するものではなさそうです。
その他
普段意識してることとかTwitterのリプでいただいた質問とか
必要そうな知識
AtCoderはほとんど知識が要求されないこともあってかなり難しいんですがライブラリとしてはAtCoderだけなら600点くらいで出うる内容くらいで十分なんじゃないかなぁ。僕はそれ以上使った記憶がないです。
テクニックも
・単調性→にぶたん
・マンハッタン距離→45度回転
・(思い出したら書き足す)
みたいな青あたりでも十分知ってることくらいで黄色の頃から極端には増えていない気がします。
赤になる前後の変化でかなり実感しているのはアドホックでない500点以下が瞬殺できるようになったことで、個人的にはこれが1番大事そうです(うーんAtCoderの点数基準で書くの微妙そうで、こどふぉ換算のほうがより正確そうなんだけどこどふぉの点数事情がよくわからない、たぶん1900とかその辺)。
これくらいができるようになると、高得点の問題でも何らかの性質を見つけたときにそれが良さそうかあまり使えなさそうかの判断を間違える確率がかなり下がって、解法探索のコストがかなり下がりがちです。
で、これはたぶんAtCoderよりこどふぉのほうが鍛えられる印象があって(良くも悪くもこどふぉのほうが典型+1ステップ系が多い気がします)、こどふぉを埋めると良さそうな気がします。
精進
最近できてません(完)。
AtCoder、codeforces、yukicoder あたりにだいたい出ると週3.5くらいにはなって、それとチーム練を合わせると週5くらいになるのでそんなに余裕なくない...?(ほぼ同じ環境で問題を解きまくってる人がいるのも知っているのであれだけど...)
JAGとかACPCとかで最近できていなかったけどこどふぉのDiv1バチャは再開したいと思っています。何人かで集まってバチャる(最悪同時でなくてもいいが友達の成績が把握しやすいとよくて、その点こどふぉはえらい)と集中できるし解くのにかかった時間とかも管理できるから個人的にはかなりいい練習方法な気がしています。前半の簡単枠でACが稼げるのも精神に良いですね(1日1問を悩み続けて終わり、大事な経験とは思うがつらいので...)
コンテストの立ち回り
これは自明なことしか言えないですが基本的に前から解いています。順位表を見て逆転が起きてるところがあったら考えたりします。現時点で解かれているわけでもないのに後ろを見に行く立ち回りは現時点で求められたことはないです。あとtouristはできるらしいですが並列思考は一般人には無理だと思います。
ARC級は後ろから2番目の問題を高速に解けば普通に赤パフォが出ます(そうでないときは最後の問題が解けないとダメな回なので解いてください)。そういう意味でも500以下の瞬殺力は大事だなぁと思っています。
あと考察に詰まったときは一旦力を抜くのは大事です。ちょっと歩き回るもよし、トイレに立つもよし、なんとなく順位表を開いて友達の進捗を眺めるもよしです。1回深呼吸してから問題に戻ると今まで全然見えなかったことが見えたり見えなかったりします。
赤になって変わったこと
ARCがunratedになった
オンサイト予選がunratedになったのはかなりありがたいです(最悪遅刻して参加とかも許されるので)。
ユーザー名が変更できなくなった
知らなかったんですけど赤になると原則変えられなくなります。サポートに連絡するとできたりできなかったりするらしいですが少し面倒。近々赤になる予定があって名前を変えたいかもしれない人は今のうちに変えておくことをお勧めします。
Twitterでバズった
赤になったツイートに1200いいねがついてフォロワーが200人増えました。赤になる行為は言ってしまえばただの私事なのでそれを多くの人にお祝いしてもらえるのはとても嬉しいしありがたいことです。
TBA
まだ赤になってから何もしていないので何かがあるたびに書き足します。
今後の目標
・AtCoderのwriterをする(まずはABC、できればARC級)
・chokudaiに勝つ
・オンサイトで賞金
・WF
最後に
正直なところ赤になった実感はあまりないです。いやTwitterでは散々ネタにしてるんですけどなんかまだ単に自分の持ってるコンテンツが1つ増えただけ、みたいな感覚です。赤になることがほぼ確定した瞬間は嬉しかったし武者震い(?)もしたけど、いざなってみると呆気ないというか。当たり前なんですが日常は何一つ変わらなくて明日も人生が続くんですよね。
でもそれでいいと思っていて、まだここは通過点であってゴールにはなって欲しくないので。
この数回のコンテストが相当上振れなのは自分でも分かっているけどそうはいっても橙を8回で抜けられたあたりまだまだいけるだろうという思いも当然あるので、もう少しこの調子でレートを上げられたらなぁ。
次回のAGCでパフォ2580くらいを叩いたら一発脱色らしいのでそれは避けたいね(フラグ)
ACPC 2019 参加記
少し遅くなりましたが。
Day0
みんなでボドゲをした。ここには名前がないけどmonkukuiとidsigmaもいた。
わいわい#リトルケイブ pic.twitter.com/fnnOsr46bb
— てんぷら (@tempura_cpp) September 17, 2019
新宿の安心お宿に宿泊してコインランドリーを回したり風呂に入ったりしてたら3時になってて崩壊
Day1
朝
いけだくんに5時過ぎに起こされる。鈍行で会津へ。ナンも一緒だった。
いけだくんから今日の行程を聞いてありえねぇっつってる
— てんぷら (@tempura_cpp) September 17, 2019
「たぶくん郡山着いたんだって」
— てんぷら (@tempura_cpp) September 18, 2019
「「かわいい〜〜〜」」
「たぶくん解説書いたって」
「「かわいい〜〜〜〜」」
「「えらい〜〜〜〜」」
この直後たぶくんと郡山駅で合流してちょっと気まずい気持ちになる。
コンテスト
たぶくんとおるふぇと組んだ
単独全完で優勝〜〜〜〜〜 pic.twitter.com/inGxoviVHw
— てんぷら (@tempura_cpp) September 18, 2019
終了30秒前くらいにGの貪欲を詰めきれてACできたので最高だった。あとは忘れた。
反省: 無駄にlong longにしてMLEを出さない
Day2
コンテスト
えびちゃんとあんぱんまおまおさんと組んだ。
惨敗。
コンテスト後てんぷら「J、順列に対する操作と見れるのはそうでcをセグ木に投げる前に潰せるの気づかなくないですか?」
beet「そこは0点です」
てんぷら「はい...。」
反省とか : 2DFFTを書く。円環に慣れる。へのくんを探さない。
懇親会
中華だったのだけれどテーブルの治安が最高だったのでレートの高い順に料理を取れるシステムが採用されていた。僕とbeetくんがほぼ真反対に座っていたせいで無駄な移動が行われ続けていた。卓の転倒数は3くらいでそんなに酷くはなかったはずなんだがなぁ。
なんか次に赤になるのはさすがにbeetさんですかねみたいな話をしていた気がするけど僕が先になっちゃった。beetすまんな。
反省とか : やむなくを探さない。
Day3
コンテスト
いけだくんとおきもちで組んだ。
いけだくんにBの実装を押し付けた。おきもちが冷えてた。AEのFAをとった。Gの実装が間に合わなくて惨敗。
チーム名を「ikeda_no_okimochi」にしたらFA発表でいけだが呼び捨てになることにいけだくんがキレてて笑った。
反省とか: SAを書く。DPはちゃんと詰めてから実装する。チーム名に名前を入れるときはHNかくん付けにする。
帰宅
翌日のキャンプの買い出しをして帰ったら25時になってて絶望。
反省: 旅行はなるべく連日にしない。必要な買い出しは早くに済ませておく。
まとめ
来年から社会人なので会津に行くのは最初で最後かも?ですが、とても楽しかったです。コンテストはもうちょっとちゃんと勝ちたかったです。ありがとうございました!
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が飛んでたから出る。
こどふぉ 2551 -> 2599 赤復帰ならず
— てんぷら (@tempura_cpp) September 14, 2019
つまらん。
Day2
つくばセット
教習所から参加のやむなくも含めてHeno World で出た。
・Eてんぷら、Aへの、Dやむなく
・Fの嘘を書いて落ちる。Fが一般マッチングに帰着される。完。
・やむなくから「ぼくのかんがえたさいきょうのいっぱんまっちんぐ」が送られてきてへのくんが実装する。僕は無理だろっつって止めてた(この辺わりと空気が悪かった)。
・けっこうバグるのでJを割り込んで書いたりする。添字でバグらせたりmodでバグらせたりして最悪な気持ちになるけど一応通る。
・Fが通る。は?????俺が悪かった。
・Iのジャッジが治ったので考えるとへのくんが解いてくれた。てんぷらこれジャッジが壊れる前にそこそこ考えて解けなかったのだめでは?
・途中教習で抜けてたやむなくにCを投げたらほどなくして答えが返ってきた。こわい。AC。
・Gのそれっぽいのをへのくんが書いたけど通らない。解説を聞いた感じわりと惜しい嘘だったっぽい。
7完でオンサイトでは1位、やったね。
解説を聞くとHが当然やんけという気持ちになる。ダメだなぁ。
ABC
てんぷら?
— heno (@heno_code) September 15, 2019
てんぷら冷えてるか〜w
— beet (@beet_aizu) September 15, 2019
てんぷらさんがバグってるのをニヤニヤしながら見てる(最低)
— heno (@heno_code) September 15, 2019
完。
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としては難易度感覚さん。
いろいろと学びの多い合宿でした。ありがとうございました!!!!!