ICPC ラスト 日記
チーム戦略: チームメイトを退屈させない
[0h~]
チームメイトにA~Cをやらせることにして，Dから読み始める
D 左下の角に点がある場合だけ考えれば良い 右上の角にも点がある場合はできる 一般的なケースは？→何？
E 図が不愉快
F 図が不愉快
G それっぽい必要条件を出す→その条件を満たしたまま辺を追加し続けられる やる AC
AとBが通る 素晴らしい
順位表を見るとCがちょっとやばそう
J あえて解法を言わずにチームメイトに投げる(何様？)
なんかもう一人のチームメイトがEをやってくれている(ありがとう．．．)
[1h~]
H バカだからgcd/lcmでまとめずに各素因数バラバラに管理する→考えうるすべてのバグを踏み抜く(テスターかな？)
J解法言う(最初から言え)
Hのストレスで甘いもの食い散らかして頭が壊れる
H通る(苦しい；；)
J通る
[2h~]
I いつもの実家おまたせ 頭が壊れて変数の更新ができない
チームメイトが2人でEのデバッグをしている
EでWAが生えまくってるが楽しそうなので放置する
I通る 実装入ってから40分経過していて引く
[3h~]
さすがにCを処理しようとする スタートとゴールが変なところにあるのでどうせ右手法が少ない手数で作れる
最後のサンプルに右手法のコード書いてあって親切だなあ(は？)
コピペするのもめんどくさいので5手全探索する(不幸中の幸い) 通る
実装入ってから40分経過していて引く
そろそろEを助ける どうせ外接円の中心が多角形の外部になるケース見落としてるだろ(最悪)と思っていたがちゃんと考慮していたので感心する
余弦定理でcos出してからacosしていてやばそうだったので普通にsin→asinでやってもらう 通る
[4h~]
DFやばそう
K 自明 20分で処理できる
チーム全員退屈な時間を過ごす
反省点
・甘いものを食べすぎない
・協調する
日記 20201217
起きたら18時 課題をやったら23時
競技プログラミングだけではダメだと感じた話
研究に詰まったらやること
研究をやめる
研究をやめるということです。
codechef:PSUM
問題を解く過程で考えたことを書くよ
題意
N個の宝がある
i番目の宝の重さはciで、価値はviである
重さSまで許容するナップザックがある
ナップザックに収まるような(重さの合計がSを越えないように)宝の選び方すべてについて、(価値の合計)^Kを計算して、その総和を求めてください mod 998244353
N,S<=100
K<=100
ci<=100
vi<=10^9
考え方
前からdpしていくイメージで考える
今、[1,i-1]の中からいくつか選んで、その価値の総和がvであるとする。そして、v^Kが求まっているとする
このとき、(v+vi)^Kを計算できると嬉しい(i番目の宝を追加したときの価値^K)
二項展開すると、(v+vi)^K=Σbinom(K,k)v^k vi^(K-k)
あ、exponential generating functionの積が計算できればいいじゃん
→modが998244353 勝ちました
負けました
www.codechef.com
上記の解法について詳しく書くと、
dp[i][j][k]:=宝を[1,i]から選んで、重さの総和がjとなるようなすべての選び方についての、価値^kの総和
と定義すると、二項展開の式から、
dp[i][j][k]=dp[i-1][j][k]+ Σ[l=0,...,k] binom(k,l)dp[i-1][j-ci][l]*vi^(k-l)
という漸化式が生えて、これはO(NSK^2)で計算できる
ここで、漸化式をよく見るとexponential generating functionの積を計算するような形になっている gg
上記をさらに詳しく説明すると、
2つの数列{ai},{bj}があったときに、新たな数列
{ck} (ck=Σ[l=0,...,k] binom(k,l) ai*b
数式を普通に打ち込んだら読みにくいだろ やめました
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:
形式的冪級数で解けます(ホントかな？？)
Hの形式的冪級数解
— うくにたん (@latte0119_) September 15, 2019
(実装してないし確認してないので、係数間違ってるかも 本質は多分合ってる) pic.twitter.com/6PoFo5QyUH
まあ愚直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とぽてちが通したな なんで
総評:
だめ
おわりに
競技プログラミングをやりましょう
ICPC国内予選2019
チームsnuke(latte0119 + potetisensei + sortreew)で出ました ABCDFの5完で12位でした 松坂牛が欲しかったです
続きを読む