ABC325 （2023/10/21）
〇A問題
Yuto.icon PG Battle終わって色々してウトウトしてたら寝過ごしました．15分程遅れてスタート．問題自体はやるだけ
CarpDay.iconお疲れさまでした～
TK.iconなんか急にＡ問題簡単になった？splitして、前側にsanつける
Kaplam.iconprint(n,"san")って感じ
おたふく.iconCarpDay.iconTTT.icon sakana.icon特段言うことは無し
tako.icon以下同文
まーす.icon最初Tが与えられた意味が分からず，時間を食った．なにこの問題？
yuichang.iconやる
〇B問題
Yuto.icon 開催時間を全探索
TK.icon開始時間を全探索、最初9～18に当てはまるということから探索範囲をrange(9,18)にしていたが、冷静に考えると違う。時間をかなり無駄にした。
おたふく.icon rangeの範囲を打ち間違い...。開始時間としてあり得る0 ~ 23で回し、全ての時間において参加者の最大値を求める。時差が日を超えて24時を超えたら0時に戻るように24で割った余りを取る。
Kaplam.icon時差戻して9~18と33~42で入ってたらおｋみたいな感じ
CarpDay.icon同じく開催時刻を全探索して，最大参加可能人数を出力．各拠点 i に対して，[x_i + 9, x_i + 17]または[x_i + 9 - 24, x_i + 17 - 24]の範囲に開催時刻が入るかチェック．
TTT.icon TK.iconさんと同じ探索範囲で勘違いをしており, 僕の場合は結局コンテストが終了してからこのページを見るまで勘違いに気づけませんでした。
tako.icon累積和みたいなことをやっていたら時間がかなりすぎてた
sakana.iconTK.iconさんと同じです
まーす.icon方針は他の方々と同じ．私は，開催時間を19～18時と勘違い(なんでこう勘違いしたかは不明)．ずっと，入力例１で5しか出ずに時間だけ無駄に食った．
yuichang.icon4WA。今見ている都市の時刻を9時と仮定する全探索。pair型の配列を構築。第2要素を昇順にソート。最初の要素の第2要素と今見ている第2要素の差が9以上になるまでtmpに第一要素を足していく。それをansと更新する。会議時間は9時間、終了が18時なので日をまたぐことは無いのに何故通らない？？今もわからない。
おたふく.icon (W, X) = (1, 0), (1, 23)の時に、yuichang.iconのコードでは最大値が2と出力されないのでは？
yuichang.iconもう完全におたふく.iconさんの言うとおりです、、ありがとうございます🙇♂
〇C問題
Yuto.icon みんな大好きUnionFInd．お久しぶりです．
TK.icon開始地点ごとにbfsして、前に探索到達済みもしくはセンサでないなら加算しないという感じでやった
Kaplam.icon再帰でDFSした、サンプルがなぜか通らないと思ったら1個"-"が"+"になってた
おたふく.icon 久しぶりUnionFind❤
Yuto.icon (⋈◍＞◡＜◍)。✧♡
CarpDay.iconDFS．UnionFind忘れてた．sys.setrecursionlimit忘れてRE．新しいPyPyなら再帰も速いという噂を信じてPyPyのまま投稿してTLE...orz ． CPythonで提出してAC．
tako.iconUnionFind
sakana.icon最初方針間違えて時間潰しました。DFSしようと思って作ったらRE…もう一回解き直します
まーす.icon考え方はABC304のC問題と同じ．本番中UnionFindに頼らずに書こうとして，一旦D問題へ行きそこで地獄をみた．コンテスト後UnionFindでやってみたらいちころ．
yuichang.icon8近傍の幅優先
〇D問題
Yuto.icon 飛ばした
TK.iconｄｐっぽいなと思い考えてみたが、Ｅと点数が同じだったのでＥを見てみたらダイクストラっぽいと思いそっちへ行った。
Kaplam.icon始まる時間をheapqにして始まる時間が早くて終わる時間の早い荷物から見て行って、印刷出来たらtimer = max(timer + 1,見てる荷物の流れ始めの時間+1)みたいに(大体解説と同じ)したらなぜかWA6、set使う時hashの衝突でもしてる？ とlistでも作ってみたもののWA減らないしTLE出るしそういうわけでもないらしい
CarpDay.icontimer+1した後で，その時刻に開始できる荷物があったらリストに追加する処理していますか？私はその処理を忘れていました．
Kaplam.iconちょうどそのパターンでWAケース見つけた所でした、期限長いタスクを抱えている途中で期限の短いのが来るとそっち先やる必要ありますね確かに...
おたふく.icon 自分はdpで考えたがTLE。
CarpDay.icon多分Kaplam.iconさんと同じ．WA6．heapq使わない方法（開始時刻をキー，終了時刻のリストを値とする辞書）を使う方法で実装しなおしたもののWA6．コンテスト後に解説見て，頭の中の方針はあっていたのに，自分の実装が間違っていることに気付く．heapq版で組み直してAC．
まーす.icon私も最初DPで考えていたが，途中で諦めた．
〇E問題
Yuto.icon ダイクストラじゃないんですか．．．？色々やったけど，7WAが消せなかった．得意なグラフが解けなかったの悔しい
Yuto.icon 解説見た．解説の方法で解けるのは分かるんだけど，なんで自分のやり方だと無理なのか分からん．
TK.iconダイクストラっぽいから、いろいろ記事を参考にしつつ実装。ぎりぎりで出したけどWA13。辺のコストをあらかじめ前計算して、小さいほうしか使わないという形にしていた。まあ、ちゃんとダイクストラの実装からやっていきます。(追記：今見たら自分のライブラリにダイクストラちゃんとあったわ... しかも問題微妙に勘違いしてる)
CarpDay.iconあの方法でAC．ギラティナさんに感謝（解説とはやり方異なっていました）．ABCEの4問ACだが，2ペナが響いたのか，2週連続ランクダウン．辛い．．．
tako.iconダイクストラしてから乗り換え場所を全探索で3WA
〇F問題
CarpDay.icon残り時間20分で見るがすぐには解法思いつかず，D問題に戻る．コンテスト後，あの方法で検討するが，$ O(10^8)になるので無理と判断．コスパの良い方のセンサーのみ使う状態から開始して，無駄の多い区間から順次別のセンサーに切り替えるGreedy法で実装するも8/63WA．諦めて解説みたら．．．その通り実装してAC．