ABC416 （2025/07/26）
〇A問題
まーす.iconfor文でひとつずつ確認．$ Sの$ L文字目（1-index）も判定する必要があるので，range(L - 1, R)に注意．]
CarpDay.iconスライスしたs[l-1:r]とoをr-l+1を並べた文字列を比較
wataumi.iconprint("Yes" if not 'x' in S[L-1:R] else "No")
Kaplam.icon for i in range(l-1,r)
N_N.icon for 文でひとつずつ．
〇B問題
まーす.icon#の後にoがないかをflagで管理．サンプル３のように.のみのケースのために，flagの初期値はTrue．
wataumi.icon まーす.icon さんと同じく．
CarpDay.icon.が連続する最初にoを入れる．
CarpDay.icon解説みたら，1-linerがあった！すごい！
Kaplam.icon # が来たらoを置く権利が復活するみたいに愚直に、タイトルとかDaily akariからとってるのかしら
CarpDay.iconどういう意味？akariって「明かり」？
Kaplam.iconhttps://dailyakari.com/ dailyakariってゲームがあって、今回の問題みたく光(o)を置けるかどうかを考えるゲームなのと、競プロの人がやってるのが割と回ってくるのとで元ネタなのかもな～と思いました CarpDay.icon情報ありがとう．リンク先見たらやりたくなったけど，まずここ書いてから(^^)
CarpDay.icon操作性快適なゲームだね！「とても簡単」でも結構考える．．
Kaplam.icon普通でえらく詰まって何回も盤面リセットするときもあれば逆に難しいとなってる問題があっさり解けちゃうこともあって最初の当て勘の調子によって体感難易度大分変わってしまうので難易度表記はあんまりあてにならない気がしてます_(:3」∠)_
CarpDay.iconどこかでやったことあるパズルだと思ったら，ニトリ（パズルの名門）での「美術館」でした（https://www.nikoli.co.jp/ja/puzzles/akari/ ）．ペンシルパズルだと光が届く範囲を描くのが面倒だったのであまりやりませんでしたが，上のサイトはいいね！0を顔文字にしているのも良い！面白くて日曜日の時間，だいぶ溶けました．．あと，問題名の1D Akariの1Dは「Daily」と「1次元」と掛けているのかも！ N_N.icon CarpDay.icon さんと同じく．
〇C問題
まーす.icon考え方は簡単だけど実装が地味にむずいやつ．
CarpDay.icon単純に文字列作ったらTLEになるやつだ，と思って文字列作らずに実装したらWA．ロジック合っていると思ったけど理由が分からないからダメもとで文字列作ったら（やり方はKaplam.iconさんと同じ）234msでAC．うーん．
CarpDay.icon上のロジック，Sの中に同じ文字があったとき，正しく動きませんでした．早めに見切り付けてよかった．
Kaplam.iconitertools.product(range(n),repeat = k) で全探索してソート
wataumi.icon最初は３進数で考えてて、完全に沼りました。最終的には Kaplam.icon さんと同じく．
wataumi.icon反例（3 2 3 \ a \ aa \ aaaa）→ 辞書順１番目＋辞書順３番目よりも辞書順２番目＋辞書順１番目の方が辞書順で前になる。
CarpDay.iconおんなじです！N進数でのK番目にしたらWAでした．（a, b, c)→(aaa, aab, aac, aba, abb, abc, aca, acb, acc, ..., cca, ccb, ccc) なのでN進数で解ける！と思いましたが，(a, a, c)でN進数使うと上の例でbをaに代えればいいので(aaa, aaa, aac, aaa, ．．．）となって間違いになります．
N_N.icon 再帰呼び出しで全探索．自作の SortedList に入れていく．（Java には SortedSet しかないため．）
〇D問題
まーす.iconAを昇順sort，Bを降順sortして，上手い感じにずらす．
Kaplam.iconA,B全部modとってAをsort , BをSortedListに入れて Bの中であるAの要素と足し合わせてMを超える値を見つける、WAはいつもの癖でSortedListじゃなくてSortedSetでやっちゃった_(:3」∠)_
CarpDay.icon多分上のお二人と同じ．$ Mでmodとった数の個数を保持した方が速いかと思ってほぼ実装したあと，$ M\leq 10^9に気付いて素直にmodとった数を残す方針に変更．これでかなり時間ロス．
N_N.icon Aを昇順にソートしておいて，Bの相棒をその中から一つずつ探していく．Bはソートする必要なし．相棒は，M-B 以上の最小の値をAのリストから探す．C 問題で自作の SortedList を使って AC とったのでいい気になって，D問題でも使ってたら TLE．．．標準の TreeMap に変えて実装しなおしたら AC．
〇E問題
Kaplam.iconワーシャルフロイドへの理解が足りませんでした！！！
まーす.icon最初にダイクストラ法で，街$ i, j間の最短距離を求める．そして，クエリごとにダイクストラ法で，街$ i, j間の最短距離を更新した結果ほぼTLE．任意の組に対して変更をおこなってるからか......
まーす.icon解説見た．ワーシャルフロイド法は名前しか知らなかったので，せっかくだし勉強するか．
CarpDay.iconむっちゃシンプルなので，ぜひ自分のものにしてください！
CarpDay.iconワーシャルフロイドで全点間距離求めて，初期状態での値は計算できたが，道追加や空港新設したときにワーシャルフロイドの一部の処理をO(N)でするんだろうけど，O(N)で行う方法が分からず終了．
CarpDay.icon解説見る．O(N^2)でも良かったんじゃん！計算量誤って評価して諦めるの早すぎ．反省．
N_N.icon きっとワーシャルフロイドを使うんだろうなと思ったけど，手元に実装がないのであきらめる．
wataumi.icon【コンテスト中】TLE×11，RE×5．→ 解説見た．空路を 超頂点 とする φ(..)
【23:48】修正を試みる．なぜかTLEが増える．TLE×12，RE×5．お風呂に入る．
【02:04】INF = float('inf') を INF = 10**9 に変更．WA×24，TLE×1．洗濯物を干す．
【03:36】INF = 10**11 に変更．WA×３．
【03:39】INF = 10**12 に変更．TLE×２．そもそも論，最大経路長分 ≒ (500 - 1) * 10**9 は余分に欲しい．
【04:27】ループ不変条件をループ外に移動させること でAC！理由は 配列アクセス回数を減らせる から。
CarpDay.iconお疲れ様でした！空路のパターンは頻出ですね．多スタートの最短経路問題とかでも使います．
CarpDay.icon一週遅れで取り組む．初期入力値で同じ都市間を結ぶ枝が複数存在する可能性を見落としてWA連発．他の人の投稿見て気づいて修正するも今度はTLE地獄．wataumi.iconさんと同様，最終的には多重ループで二重リストへのアクセス回数を減らす処理をしてやっと3437msでAC．そのあと，ChatGPTにTLEコードをC++に変換してもらって投稿したら257msでAC．．Pythonで通すなら不自然な高速化が必要，という問題が最近減っていたのに残念．制限時間短すぎ．
kakip.iconN^3通らないと思ってた
〇F問題
CarpDay.icon最後の数分に覗く．Greedyな方法で求まるのかな？1つ目採用したあと，木が2つ以上に分割したらどうするんだろう？
N_N.icon E問題をあきらめて，こっちを少し考える．ノード毎に，そのノードを通る重み和最大のパスを求めるとかかな？
kakip.iconKの存在忘れててK>=N/2のときだけ解けた。問題ちゃんと読め
〇G問題
kakip.icon解けた 長さが同じ文字列のうちいちばん小さいのだけ残す 後ろから最小になるように文字列を決めていく 比較するのは前10文字だけでいい