ABC366 （2024/08/10）
〇A問題
まーす.icon$ \dfrac{N}{2} < A ∨ \dfrac{N}{2} < Tのとき，‘‘Yes’’ を出力．それ以外は，‘‘No’’ を出力．
まーす.icon$ \LaTeX の練習がてら...
CarpDay.icon文字まで数式内に入っているけど，意図的？？
まーす.icon8/19までに，LATEXで発表資料作らないといけないので，意図的です．変な改行が入ったりした場合には，LATEXで書いていないのでご安心を…
CarpDay.iconTeXでの引用符について記そうと思ったけど，このページでは「`」（バッククォート）2つ入れると表示がおかしくなる．残念．参考サイト こちら まーす.iconありがとうございます！！
まーす.iconいくらか検索かけてみましたが，見つからなかったのでとりあえず全角で代用．参考サイトには，全角はダメだと書いていたので，留意しておきます．
tako.icon > N // 2
Kaplam.icon別件で頭悩ませてたらとっくに開始時刻過ぎてたし適当にやりすぎてA問題でWA2回出すし('ω')
CarpDay.iconmax(T, A) > N // 2
kakip.icon高橋君が勝ち確定か判定と読み間違えた
〇B問題
tako.icon 文字が残ってなかったら*用のリストに*詰めて残ってたら*リストと文字を詰める
まーす.icontako.iconさんの操作を行った後の文字列リストに対して，転置行列みたいな操作を行ってできた文字列のリスト を文字列ごとに逆順で読むだけ．
まーす.icon自動で改行になってしまうのか......．
まーす.iconこの問題だけ，$ \LaTeX で書くの諦め......
Kaplam.icon転置っぽいことして横見てまだあったら0を*にしてみたいな
CarpDay.iconB問題から解いたけど，難しくて焦った．．zipで転置したけど，*の処理に苦労した．素直に作った方が良かったか．
kakip.iconitertools.zip_longest(fillvalue='*')して、reversed()して、str.rstrip('*')
CarpDay.iconすごいなぁ．．．
〇C問題
tako.icon 辞書使うだけ
まーす.icon$ 辞書でボールの数を記憶．
Kaplam.icon$ 辞書でボールの数と種類を記憶．
まーす.icon確かに，Kaplam.iconさんの記述の方が正しい．言葉足らずでした．
CarpDay.icondefaultdictだと1から0になったときにlenで正しく種類カウントできないと（誤った）判断して，ボールの数を記憶するリストとボールの種類を記憶する集合を作成．うーん．体調悪くないけどなぁ．．
kakip.icon同じくdefaultdict
〇D問題
tako.icon 問題が理解しにくかった。LxからRxまで二次元累積和回すの間に合うか不安だったけど間に合った
まーす.icon$ 2次元の累積和．めんどくさい．
Kaplam.icon3次元累積和...じゃないの？
まーす.icon2次元の累積和＋forで足りた．
Kaplam.icon言わんとせんことはわかるけど最初から3次元作るのが自然だと思ってた(´・ω・`)
まーす.iconむずいもん......
Kaplam.icon言われてみれば確かにどこを引いて足してっての3次元より2次元回した方が楽か...
まーす.icon逆に3次元でやったのか......スゲー！！
Kaplam.iconサンプル1個目で8の場所を求める時は(1+2+...+7+8)-(1+2+5+6)-(1+2+3+4)-(1+5+3+7)+(1+3)+(1+5)+(1+2)-1って感じで出来る
まーす.icon簡単そうだったら，ICPC用にライブラリに追加ってのもありだったけど，結構複雑だね......
Kaplam.icon今回提出したのそのまま載せればライブラリとして十分使えると思うの
まーす.icon$ n次元はさすがに無理か......
Kaplam.icon再帰使えば出来るだろうけどだるい！！！↑
CarpDay.icon3次元累積和なのだが，それを作るのに一苦労．みんな速いなぁ．最近kakip.iconさん書き込みなくて淋しい．
kakip.icon# 3次元累積和を計算して、クエリに答えるって書いてAI補完してもらう
CarpDay.icon書き込みありがとう！最近ABCのレベル上がっている気がする．そろそろルール範囲内での生成AI利用を検討しようかな...
〇E問題
tako.icon全然わからん
Kaplam.icon45°傾けて2次元累積和とかと思ったけどO(n^2)かかるから無理
CarpDay.icon到着したときには残り20分．F問題も見て（F問題の方が面白そうだけど20分では絶対に無理と踏んで）E問題に戻る．まずXとＹに分割して，マンハッタン距離は中央値のときに最小になるから...までは合っていると思う．その後実装するも，入力例2WAで間違いに気付く．
kakip.iconXとYに分割して、各座標からのマンハッタン距離の合計を計算して、二分探索で各座標軸ごとの個数を求める
CarpDay.icon諦めてkakip.iconさんの伏字見て感心．なるほど．解説読んでさらに理解．O(10^6)で諦めてはあかんね．
〇F問題
まーす.icon$ 定義された函数fは，単調増大なので1 \leq i \leq K 回目時点での最適解を考えてやればよさそう．
まーす.icon$ 函数fが単調増大とは，A \sub \mathbb{N}をfの定義域として，\forall a,b \in A,a<b \Rightarrow f(a)<f(b)を満たすことである．
まーす.icon$ なんかDP使えそう．
CarpDay.icon楽しそうなので，明日ゆっくり考えまーす．
まーす.icon(^O^)／
CarpDay.icon翌日．まーす.iconさんの指摘通り，どの関数も単調増加なので，重複が許されるなら毎回最大となる関数を選べばよい．重複許されないから，過去に選択していない関数を選んでできる上位$ K個の値を保持し続ければできるのでは？としたが26TLE2WA．WAの原因は関数を選ぶ順番にあると踏んで，f1(f2(x))とf2(f1(x))の大小関係を考えて性質を発見するも，その後の方針立たずにGiveUp．解説読んで納得．良問だ！まーす.iconさん，やるな！
〇G問題