ABC324 （2023/10/14）
〇A問題
Yuto.icon len(set(A))==1
kakip.iconやるだけだがなんかいい書き方ないか考えてて微妙にタイムロスした。setが思いつかなくて悔しい
おたふく.icon Yuto.iconと同様
Kaplam.icon1個目と比べる
まーす.iconYuto.iconさんと同じ．
tako.icon全探索。set使えばよかった
CarpDay.iconKaplam.iconさんと同じ．A問題はベタな方法でOK（だと，setを思いつかなかったことから目を背ける）
yuichang.iconsetを使う
〇B問題
Yuto.icon xとyを全探索．$ 2^{64} \gt 10^{18}なので，x, yは64くらいまで試せばok．
kakip.icon適当に上限決めて2重ループ
おたふく.icon Nを2で割れるだけ割ってから、さらに3で割れるだけ割り、残ったNが1かどうか。
Kaplam.icon↑↑と同じ
まーす.iconCarpDay.icon おたふく.icon さんと同じ．
tako.icon全探索
yuichang.icon2と3で割れるだけ割る
〇C問題
Yuto.icon ➀候補を全列挙するか，②全てのSについてTにできるか判定するか，どっちかかな，と思ったけど，最後の制約（＊）「s_1, ..., s_nの長さの総和が10^5以下」を見落としてて，無理じゃね？となったので一旦飛ばした．Dを解いて，Fが無理だったので戻ってきた．制約（＊）に気付き，②ならいけそうなので実装して提出してみるとTLE．明らかに無理なやつを枝刈りしたりしてみたけどほとんど変わらない．ここでコンテスト終了．無念．
おたふく.icon 沼りに沼。あらかじめ、Tと同じ可能性のある文字列T'を全列挙。Tの長さが最大のときに挿入することで出来るT'の個数はアルファベット26文字、挿入位置5*(10^5) + 1通りなので計算量26 * (5*(10^5) + 1)で求められるのでTLEになるの何故？
CarpDay.icon同感．変化なし1通り，挿入$ |T'|通り，削除$ 26(|T'|+1)通り，置換$ 25|T'|通りなので，全部で$ O(|T'|)だと思ったけど，定数倍の26が効いているのかな？
kakip.icon地道に場合分けする。１つ増えるor減る場合は、スライスとかでいいかんじに判定
Kaplam.icon最初全部で5*10**5見逃してて一旦D行って戻ってきた時に気付いたけどWA,原因わかったけどどこかエラーで動かなかった
tako.iconYuto.iconさんと同じく制約を見落として悩んでたけど早くに気づけて愚直実装
CarpDay.icon私も制約条件見落として，おたふく.iconさんと同じ方法で実装するがTLE．制約に気付いて別の実装開始するが，配列外参照でRE．一次的対応で（綺麗なコードでなくて不満だけど）AC．文字列を1文字ずつ処理する癖がなかなか抜けない．反省．
yuichang.icon 全部調べる。枝刈りケチってTLE
〇D問題
Yuto.icon N桁までの平方数を全部作ってみたら4secで間に合いそうだったので，最初に平方数を全列挙して，各平方数がSから作れるか確認する方針に決定．結構重いので，平方数を作る部分のループ上限は慎重に決める．個人的にはCより簡単だった
Kaplam.icon10**13までの平方数入れてそれぞれの0～9の数記録して、0を含んでいる時はremoveしてもう１度比べてってので問題なかったはずが平方数求めるまででかなり時間かかって10**7もないし行けそうだけどこれじゃないのかと思ってCに戻った
kakip.iconYuto.iconさんと同じです。rjustでゼロ埋めとかしてリストでそれぞれの数字が何個あるか数えて判定
まーす.icon①．N+1個の数字だけの文字列Sが与えられるが，Sに0~9がそれぞれ何個含まれているかをdictで記憶．②．1~N+1桁の平方数を文字列でlistに格納する(ある平方数<10^(N+1)となるときは桁数を合わせるように，その平方数の前に文字列0を追加)．③．②で格納した文字列を①でやったようにdictに記憶させる．④．あとは，①と③を使って，0~9の数が同じかどうかを調べる．文字列Sが0となるときを忘れ，1ペナ．
tako.icon Sに出現する数字の個数を数えておき、10**Nまでの平方数と数を比較。N=1の時になぜか9までループが回っておらず1WA。S=9なのがわかってしまったのでそれだけはじいてもよかったけど、ちゃんとと直しました。緑に戻れました。やったね
CarpDay.icon13!通りがネックだと判断してE問題へ．E問題のあとF問題を見て，時間的に間に合わなそうなのでDに戻ったときに解き方ひらめく．平方数を小さい順に作成して，Sから作れるか判定．数値の文字列をソートして，文字列として一致するかどうか判定した．残り時間3分で投稿して必死に祈るも，2ケースでWA．．．コンテスト後にコーナーケース（Sが0ばかりのケース）に気付いてAC．どうやら（WAまで含め）まーす.iconさんと同じっぽい．
まーす.icon考え方は似ていますね．私は"個数"に注目したので少し違います．
CarpDay.iconそっか，その点は違うね．まーす.iconさんは辞書とリストの違いはあるけど，kakip.iconさんと考え方同じかも．
yuichang.iconnext_permutationしか思いつかなくて無理だった。
〇E問題
Yuto.icon 今回文字列多いですね．難しそうだったので飛ばした．
kakip.iconそれぞれのSの前と後ろと、Tの前と後ろから何文字部分文字列として含むか数えたリストを作ってソートしてにぶたんする
CarpDay.icon多分，kakip.iconと同じかな．4問AC（ABCE）でしたが，ランク微減．．水色が遠い．．
〇F問題
Yuto.icon 辺のコストを-b/cとして（念のためdecimal使いつつ），普通にダイクストラした後，経路復元してsum(b)/sum(c)を求めたら，24AC, 14WA, 18TLE．．．流石にFがそんなに単純じゃないよね..
CarpDay.iconコンテスト中に考えた方法は，Yuto.iconさんと同じく比率（美しさ総和÷コスト総和）を距離と考えたダイクストラ法．ただ，ダイクストラ法では順次距離の近い点から最短距離を確定するのに対し，比率の場合は確定済み点の比率から次の点の比率を計算することができないので，比率だけでなく，美しさとコストも保持する必要がある．残り時間20分ぐらいだったので実装間に合わないと判断してD問題に戻る．コンテスト後に実装．DAGであることに気付き，ダイクストラではなく単純なDP的に実装するも，17/55ケースでWA．手計算で確認したら，比率の場合はベルマンの最適性原理（ざっと言えば，手前から順に最適性を確定させ続ければ，目的の最適解が得られる性質．DPが使える性質）が満たさないことが分かりギブアップ．解説見ました．二分探索かぁ．忘れたころに出てくるよね．．すぐに思いつくようにしたい．
おたふく.icon 最近競プロ典型90問を解き始めて、それの001の問題が類題です。勉強になりました。