ABC333（2023/12/16）
〇A問題
Yuto.icon N * int(N)
おたふく.icon for文を回す。
yuichang.icon for文回す
tako.iconやる
TK.iconまーす.icon おたふく.iconさん，yuichang.iconさんと同じ．
CarpDay.icon Yuto.iconさんと同じ．
〇B問題
Yuto.icon A～Eを数字に置き換えて，x1とx2の差を計算する．めっちゃ時間かかった
おたふく.icon 綺麗な解き方を考えるも上手い方法が思い付かずもったいない時間を過ごす。
yuichang.icon 全部書く
まーす.iconS1とS2が隣同士 かつ T1とT2が隣同士，或いは，S1とS2が隣同士でない かつ T1とT2が隣同士でないならばYes，それ以外はNo．これをsetでやるだけ．
tako.icon文字をintに変換して差をとる。あとは適当に場合分け
CarpDay.icon yuichang.iconさんと同じかな？5C2＝10通りの組合せを2グループに分けて，Sの両端ペアとTの両端ペアが同じグループかどうかで判定．文字を数値に置換する方法が自然だと途中で気付くも最後までやりきる．
TK.icon文字をordで数字に変換、あとは差の絶対値とって、その値が３を超えたら５からその値を引くという風にすると、隣接と一つ飛ばしがそれぞれ１と２の数字で表せる。あとは一致判定
〇C問題
Yuto.icon N <= 333なので，レピュニットを列挙して，N番目を出力する．レピュニットを作る時，文字列結合が嫌だったのでbit演算で高速化しようとしてめっちゃ時間かかった２．
おたふく.icon 数学の血が騒いで規則性を考えてしまう愚行を犯す。
yuichang.icon 全列挙
tako.iconSortedSetに全部ぶち込む
まーす.iconまず，例３より値域がわかる．これを利用して，レピュニット数のlistをつくり，あとは，3つのレピュニット数の和が小さい順から総当たり．
CarpDay.icon M桁のレピュニットを作って全列挙．M=10だと足りず，M=12で超えたので，全列挙してできたN番目を表示．
TK.iconレピュニットを１５桁まで作って３つの和をとる。その後作ったものをソートしてＮ番目を表示
〇D問題
Yuto.icon 最初問題を誤読していて，このサイト でビジュアライズして気付く．DFSして部分木の頂点数数えて，個数の合計（一番大きいのを除く）+1が答え．サンプルが全部通ったから提出したら，PyPyでもPythonでもTLE．実装が悪いのか，方針が悪いのか，どっちなんでしょうね． Yuto.icon コンテスト後，解説AC．部分木の頂点数数えるのは合ってたけど，実装が悪かったみたい．みんな大好きUnionFindで実装．
CarpDay.icon「このサイト」いいね！
おたふく.icon 葉というものを勘違いして、入力例3で何故答えが12になるのか全然理解できず...。10分前くらいでやっと理解する。手でグラフまで作成する。C問題で焦らず落ち着いて取り組めば解けたな...。
yuichang.icon dfs帰りがけで子の数を調べる
tako.iconBFSは人気がないのかな？
yuichang.icon 帰りがけ使ったから再帰dfsにしたけど、bfsでやるの難しくない？別方針なのか
CarpDay.icon 訪問済み情報を保持するならBFSでもDFSでも仕組みは同じでOK．木に対するDFSの「帰りがけ」だと，親情報さえあれば訪問済み情報を保持しなくて済むのがメリットだね．
CarpDay.icon Yuto.iconと同じやり方でなせかTLE．理由が分からなったので「大好き」で作り直してAC.
CarpDay.icon TLEの原因は，点1と接続する各点からDFSを開始するたびに，探索済みか否かを示す大きさNのリストを初期化したことでした．探索済みの点を集合で管理して探索済み判定したらACでした．些細なミスで残念．
TK.icon頂点１を削除して、Forestにしてから、それぞれの木の大きさを全て見る。大きさが最大の木以外を削除した際の頂点数＋頂点１。初めは一番小さい木を削除すればいいと思っていたが、1が葉でないと削除できないことに気づき調整した。
〇E問題
Yuto.icon クエリ逆読みかなーと思って実装してたらコンテスト終了．$ K_{\min}を求めるのが間に合わなかった．コンテスト後10分くらいでAC．惜しい．．．
yuichang.icon portionの種類と数記憶してって逆から見て余分な分stackっぽく戻って処理するもWAが沢山
まーす.iconまず，ポーションを全部とったとき，全勝できるかを確認．このとき，使用するポーションは直近でとったものを使用する(portion_list[x[i]-1]の一番後ろを消去)・・・＊．全勝できないなら-1，全勝できるなら，＊の後で残っているポーションは使わないので，とらなかったことにする．インデックスのミスで1WA．これはコンテスト中に解けた問題だわ......
CarpDay.icon 薬ごとに履歴を作って，薬を持つ時間をなるべく短くなるように逆順に探索して，入手する薬を確定してAC．出力する履歴は薬入手のクエリだけなのに，敵クエリのときも0を出力してWA．もったいない．
TK.icon前から順番に処理して行けば、Yes、Noの判定はできると思い、じっそうしたが、Kの最小値をとるところで詰んだ。
〇F問題
CarpDay.icon確率DPと踏むも，最大N=3000要素の状態を保持する方法 ＆ 同じ状態が繰り返されることへの対処 に悩んでいるうちに終了．翌日N=2,3,4の順に地道に樹形図描いて法則性を発見．$ O\left(\sum_{k=1}^N k^2\right)=O(N^3)を何とか$ O\left( \sum_{i=1}^N k\right)=O(N^2)に抑えてAC．途中MOD計算漏れがあってTLEしたのは今後の反省点．数学系問題楽しい．