ABC331 （2023/12/02）
〇A問題
Yuto.icon 丁寧にやる
TK.icon年と月の切り替わりだけ条件分岐
まーす.iconCarpDay.icon TK.iconさんと同じ．
tako.icon またまたjavaで。javaは空白区切りがめんどくさい。ということで...。これってグリッチなんだろうか...
Kaplam.iconTTT.iconAにしてはむずい
おたふく.icon 丁寧に条件分岐。
yuichang.icon 出遅れたのでバチャ、条件分岐がんばる
〇B問題
Yuto.icon コンテスト中，考えるのをやめて定式化，pulpで実装，AC．初めてコンテスト中に数理最適化ソルバーを使いました．コンテスト後，改めて考えたら，各パックを何個買うかの全探索で良かったな...
Yuto.icon ソルバー使ったの自分だけかと思ってたら，みんな使ってて草です
CarpDay.icon 特定の研究分野研究者の職業病のようなものですね．．．
TTT.icon Bがすぐに分からなかったのでCを先にしました．Bはコンテスト終了数秒後にACでした，本当に泣きそうです．Sを0~N//6+2個，Mを0~N//8+2個，Lを0~N//12+2個の三重ループで回してもo(10^5)を超えないと分かったので全探索しました．
Yuto.icon しょうもないことだけど，「$ O(10^5)を越えない」という言い回しは変かも．$ O(n)が高々$ nって意味（上から抑える）だから，$ O(n)を越えないってのは頭痛が痛いみたいな感じ．$ O(n^3)だから全探索できますとかだと良いと思う．ちなみに，今回の処理なら，$ \Theta(n^3)という表記でも良いね．
TTT.icon いえいえ，注意すべき大切なポイントだと思います．教えてくださりありがとうございます！
TK.icon全探索だろうなと思いつつも、定式化が思いつき、思考のノイズになったため、そのままpulpで出した。
まーす.icon全探索．
CarpDay.icon最小公倍数の24までは最もコスパの良いサイズ，残りは全探索．．．が誤り．続いて（最近はpython-mipばかり使っているので，使い方調べながら）pulpを使って実装するが，なぜかローカルでも解が見つからない．なぜ？？諦めてB問題なのにDPで実装して無事AC．
CarpDay.icon pulpでの変数の下限はデフォルト$ -\inftyでした．python-mipは0なので，設定し忘れていました．制約条件として明確に非負条件を付けても良かったけど．
tako.icon最初DPかなと思うもB問題でそれはあり得ないと思い適当に全探索。
Kaplam.iconBにしてはむずいと思って変なことしようとしたところで全探索に気付いた
おたふく.icon 全探索。しょうもないミス...。
yuichang.icon 各100くらいまで適当に全探索
〇C問題
Yuto.icon 累積和+にぶたん
TTT.icon Aをソートして，Aの総和から順に引いて辞書に記録していきました．
TK.iconAをソートして、順番に累積和をとっていった。あとは記録から順に答えを格納
まーす.iconAをソートして，Aの値の総和から，逐次Ａの値の小さいものを引いていったものをdictに記録していった．
CarpDay.iconおたふく.icon Yuto.iconさんと同じでしょう．
tako.iconjavaのbisect_rightをずっと調べてそれっぽいのを提出したけどWA。あきらめてpythonでAC。javaでやるとやり方が悪いのかプログラムが悪いのかがまだよくわからない。追記:javaのWAはどうやらintだったのがだめだったみたいです。longにしたらACしました。
Kaplam.iconAをソートしてなんやかんや
yuichang.icon 累積和二分探索
〇D問題
Yuto.icon 二次元累積和だと思うけど，繰り返された分を加算しないといけないのが難しい．通せなかった
TK.icon縦と横の累積和でできそうだと思ったが、２次元で組み合わせたときに破綻した。
CarpDay.icon 実装系はみんな避けるだろうから，絶対に通す！の信念で頑張り，終了10分前でやっとAC．勝負にこだわるならE問題に行くべきだったが，これはこれで満足（でもランクダウン）．
tako.iconそのままpythonで。二次元累積和で実装めんどくさかったけど何とかなれ―で出したら何とかなった。
Kaplam.icon似たような問題前にもあって面倒なことした記憶あるから飛ばし
おたふく.icon 2次元の累積和は求めれたが工夫して数えるところで悩みタイムオーバー。もう少し長考。
yuichang.icon 最近のDっぽいこんな感じの水dif問題解ける気がしない（今のところ
〇E問題
Yuto.icon 色々試したけど無理だった
TK.iconheapqだと、組み合わせ的によくないものを省く作業でダメそう。2部グラフとして解釈して最大流的な考え方は辺の組み合わせ的にTLEになる。どうすんの？もっと簡単に考えれるのかと思ったが、直感的には大きい方から試せば見つかりそうに思ったぐらい。
まーす.iconDとばしてEへ．a, bをsortしたlist，sort_a, sort_bをつくり，Ma：a→sort_a, Mb：b→sort_bの対応 を考え，とってはいけない組をスキップしてやればいけそうと思った．
まーす.icon追記，下手に難しいことを考えずにtupleで上に挙げた写像Ma, Mbを表現して無事AC．2重forだが，探索部分のループ回数はせいぜいN+L回なのでいけたっぽい．c,dをsetで判別していなくて無駄に1WA．
CarpDay.icon 残り10分で挑むがやはり無理．コンテスト後にじっくり取り組んでACしたが，試行錯誤に時間がかかる．コンテスト中に解いた人はすごいなぁ．
CarpDay.iconふと，この問題もpulpで解けると気が付いて実装．でも（やっぱり）TLE．変数多すぎるよね．
Kaplam.icon大きい順になるようにaを1個ずつ進めるかbを1個ずつ進めるかってやると抜けが出たので飛ばさないように大きい方から5*10**5+α個求めようと考えたけれどえらく複雑な方法しか思い浮かばず諦め
tako.icon残り3分では解けない
おたふく.icon 貪欲にそれぞれの主菜に対して最大となり得る副菜を選ぶ。計算量はO (N + L)になるのかな？
yuichang.icon ソートの比較関数定義とか色々考えたけどMが10^5しかないのでsetを要素にした配列でダメなペアを管理して普通にループ回しても間に合う
〇F問題
CarpDay.icon 更新がなかったとしても，各クエリに対してO(1)，あるいはO(logN)程度で解答する方法が思いつかない．諦めて解法見たら，未学習の方法でした．そろそろ学習する時期か？