らての精進日記

修行をします

JAG夏合宿2019参加記

参加しました

day1

担当した問題と、印象に残った問題について書きます
C:
やりまーす

D:
法が互いに素でないような連立合同式を解けばいい
ライブラリの使い方が分からなくてチーム全員大慌てでしたが、冷静になると、ベズーの等式を考えて拡張ユークリッドの互除法でささっと求解できるようなスマート人間になるべき


F:
これすごいですね　感動です

G:
こういう問題楽しいですね
明らかにdpなのはわかって、dpを成立させるために必要な状態の持ち方を考えていきます

H:
writer許さね～～～～～～～という気持ちになるんですが、こういう問題を堅実に実装できるようにならないとダメだな(気づき)

I:
ゾンビを基準とした相対位置・相対速度を考えるとかなり見通しがよい
各人間について二分探索することにすると、普通にCHTになって終わり
しかしライブラリの仕様が分からず大幅にタイムロスした　グッと睨むと蟻本ベースだとわかるので直線の追加の方向が理解できて終わり

上記のlogが2つの解法でギリギリ通ったんですが、並列二分探索すればCHTは線形のものを使用できてlogが減ります　これが想定なのかな

J:
うん
ぽてちくんがフローを使う嘘を考えたんだけど、反省して議論してたら二部マッチングでよいとわかり、写経したフローが生きる　不死鳥　


K:
どう見ても2D Convolutionで、破滅

2D　Convolutionがまともに解けるのは知っていたが、知識がないと無理だと思ってまともに考察しなかった　反省

wikipediaとか見てると、2Dの離散フーリエ変換を行列で表してみたらうれしい性質がある(2Dの離散フーリエ変換は、各行を離散フーリエ変換してから各列を離散フーリエ変換すればよい)ことがわかって、知見でした　　

HIR180先生に、直接的に1D Convolutionに落とす方法を教えてもらって、嬉しい

総評:
時間かければ確実に解けるレベルの問題に時間をかけてしまっているところがある

ギア上げて素早く処理していきたいね　

day2

writer側です。いかがでしたか？僕が書いた問題を当ててみてください。一問も書いてません　ぽてちくんごめんなさい

B:
こんなん無理だろ
C:
最小費用流に落ちるのはまあわかる(実はそこまで正当性をはっきり理解できていないが)

貪欲はよくわからん

F:
そういえばいまだに一般マッチング書いたことありません　理解もしてないし　詰んだ

G:
これかなり難しいと思うけどな　でもsigmaroonはあっさり通している　なぜ

H:
形式的冪級数で解けます(ホントかな？？)


まあ愚直dpしてみるとかなり分かりやすい形になって、エスパーするなり組み合わせ的にイメージするなりdp配列を多項式で表現してみたりすると二項係数が出てくると思う

見た目は威圧的だけど考察はやりやすいと思うな

I:
これ絶対やりたくねえな　アレルギーが出ます

J:
まあある程度分かりやすい式にはなって、計算方法が問題になる
ダブリングしながら多項式補間する方法普通に素敵だとおもった

総評:
ぽてちすごい

酒

酒は飲んでも飲まれるな
人に迷惑をかけるな
酒を飲むな

やむなくさんごめん(いなかったけど)(他に謝るべき人いるだろ)

day3

C:
頭が悪いので貪欲に確信を持てない　実装も怖い　よくわからないことはぽてちにやらせよう

D:
iとi xor Xはどちらか片方しか使ってはダメで、ここから2-SATが芽生える
3^nでダメなペアを列挙できるのはまあ難しくなくて、本当に難しいのは、なぜか2-SATをUFでやり始めたこと(無向辺ではありませんが？？)

2-SATではSCCを用いるという事実を唐突に思い出して、焦りました

E:
なんかぽてちとreewが頑張ってたな　

F:
？
こういう問題見ると頭止まっちゃう　存在意義なし　赤コーダーとは

G:
英語が読めなさ過ぎて、"On the i-th operation, flip a fair coin"を読んだときに、木の頂点にコインが置いてある問題だと思っちゃって一生読解が進まなくなったな(どうして？)

みんなEやってたから邪魔しづらかったんだけど、勇気を出してぽてちに英語読んでもらえばよかったな　

問題自体は面白いと思います(題意が分かれば解けてたと思う(負け惜しみ))

H:
UFをマージすれば解けるけどなあ～～(思考停止)
UFをマージすれば解けるじゃん(天地開闢)(国士無双)

残り15でPCが開いたので書いたけどダメだった　主人公ではないので


I:
解けぬ
解説みても解けない

J:
なんかreewとぽてちが通したな　なんで

総評:
だめ

おわりに

競技プログラミングをやりましょう