Codeforces Round #492 (Div. 1 & 2) [Thanks, uDebug!]

satanic@研究💪 @satanic0258

div1Aは誰かの回転ずしツイートを見てなるほどね～～となったままだった

satanic@研究💪 @satanic0258

div1Aもキャタピラ作戦で通ったね(？)

satanic@研究💪 @satanic0258

朝から解けなかった問題の復習しまくれてQoLが上がりまくるぞ～

satanic@研究💪 @satanic0258

えーdiv1C乱択まじかー

satanic@研究💪 @satanic0258

TLで見た60度ごとに分ける天才解法は確かになるほどと思ったけど，乱択であっさり通ってしまうとは

satanic@研究💪 @satanic0258

えーんジャッジ止まってしまった

satanic@研究💪 @satanic0258

実質同じのを投げて何故後のが先にジャッジ終わるのか🤔 pic.twitter.com/UqGRcfEfDp

拡大

satanic@研究💪 @satanic0258

しかし乱択で93msですか…ぐぬぬ

satanic@研究💪 @satanic0258

はーなるほど，長さが高々rのベクトルv_1,v_2,v_3を持ってきたらv_i±v_jのどれかは必ず長さが高々rになるのかぁ

satanic@研究💪 @satanic0258

この要領で3つのベクトルを常に長さがr以下になるように2つにまとめていって，最後に余った2つをまとめても長さは高々(√2)rになるんだね

satanic@研究💪 @satanic0258

問題ではr=10^6で，最終的に長さが1.5×10^6以下になればよいけど，√2<1.5より上述のやり方でOKなんだね

satanic@研究💪 @satanic0258

「要素を3つ持ってきたらこんな性質が！」，この前のARC-Eでもなったし割と典型的考察テクっぽいね

satanic@研究💪 @satanic0258

残念ながらこの考察を実装する時間が無いので帰ってきたらやりましょう～