ABC317 （2023/08/26）
〇A問題
Yuto.icon やるだけ
yuichang.iconやる
まーす.iconPiは昇順であるから，X-H≦Piとなるようなiをさがしてbreak．
Kaplam.icon好きなポケモンはヨクバリスです、かわいい(今回ポケモンネタまみれで楽しかった)
まーす.iconかわいい
tako.iconやるだけ
TK.iconソートされてるからやるだけ
CarpDay.icon上に同じ．ポッチャマ
おたふく.icon 以下同文
〇B問題
Yuto.icon print(*(set(range(min(A), max(A))) - set(A)))
yuichang.icon最小値からfor文回す
Kaplam.icon最小値と最大値を求めてからそのlistを作って出てきた数字を記録して最後に出てきてないのが答え、タイトルけつばんですね(ポケモン)
まーす.iconKaplam.iconさんと同じ．制約より，yuichang.iconさんのように最小値或いは最大値のみを使って求める方がスマートだと感じた．
tako.iconソートして順番に
TK.iconソートして探す
CarpDay.icon上二人と同じ．「最初の番号が抜けている場合もあるのでは？」と無駄な気遣いをする（「一意に定まる」のでそんな例はない）
おたふく.icon yuichang.iconと同じ
〇C問題
Yuto.icon Nが小さいので，順列全探索する．ここまでは順調だった...
yuichang.iconnext_permutation。道がないときのコスト0にしててペナ
Kaplam.icon最初10重ループとか考えたけどいくらなんでも無理だと思って再帰で辿った、"1 4"で"4 1"も通るのに気付くのに時間かかった、pypyは再帰苦手ということでCpyで出してTLE7,pypyで同じのを出して725msのAC...わからん(街と道路は勿論ポケモンですね！！)
まーす.iconこういう重み付きのグラフはさっぱり......
tako.icon深さ優先したけどPythonでTLE。わかんなくて飛ばしていろいろ考えてたけど試しに同じやつをPyPyで出してみたら通った...めっちゃくちゃ時間ロスって悲しい。茶色落ちるか―と思ってげんなりしてたらギリギリセーフ！レート保護システムとかあんのかな？
TK.icon幅優先とか深さ優先とか試して見たけど、今の実装だと一度通った点をもう一度見たいとに見れないじゃん
CarpDay.icon10! =3628800なので，全列挙で間に合うと判断して Yuto.iconさんと同じく，itertoolsくん．でも，順列ごとにO(N)かかるから，O(N×N!)になってギリギリアウトか？と思って提出したら TLE．諦めてDFSで組み直し．コンテスト終了後，Yuto.iconさんコード参照して，TLEコードのin setの部分を2次元リストの値参照に変更したらAC．in setはO(1)だけど，ハッシュの計算コストがあるので，リスト参照で済むならその方がよいことを学ぶ．
おたふく.icon Carpday.iconYuto.icon同様、itertoolsを利用して順列全探索して距離の最大値を求めようとしたが、defaultdictで道の距離を管理していたが、CarpDay.iconと同様にその道がdefaultdictに含まれているか判定するとTLEになってしまい焦った。2次元リストで管理するだけで圧倒的に計算時間が短くなってびっくり。
〇D問題
Yuto.icon 貪欲を書いてみたらサンプルが通ったので投げてみたらWA．やっぱりDPかと思って考察してたらコンテスト終了．
yuichang.iconナップサックチックなDP。一つだけサンプルが合わなくて泣いた
Kaplam.iconEの方が得意そうだったからそっち行って帰ってこれなかった、多分ポケモンじゃない
tako.iconDPっぽいなーと思いながら飛ばした
まーす.icon(X+Y)//2+1-XとZの対応をつくり，Zを昇順に並び変えてDPを考えたが，そもそも論(X+Y)//2+1-XとZの対応が作れなかった．
CarpDay.icon(X+Y)//2+1-X = Cとすると，C[i]とZ[i]を作れば，iを介して対応作れますよ．
CarpDay.iconyuichang.iconのおっしゃる通り．貰う型でWAになり，原因が分からなったので渡す型に変更してAC．
おたふく.icon dpだろうなとは思いつつもdpテーブルの設定に困り、一旦E問題へ。解き終わってからもう一度D問題へ帰ってきてから、少し方針が立つも時間終了。以前に頂いたdpの資料をちらっと見てみるとこれやんとなり、そのdpテーブルの置き方を忘れていたことが悔やまれる。少しdp問題が鈍っているなぁ...。
〇E問題
Yuto.icon 視線を壁と見なしてBFSやるだけ？と思ったけど，WA．何がダメなんか分からん
yuichang.icon通れない道を前処理で求めておいてBFS
Kaplam.icon視線のある所を通れないようにして以前の氷の問題みたく再帰で辿ってTLE20、色々工夫して2個TLE減ったけどあまり意味なかった、多分DFSになってるはずだからBFSのやり方考えたら解けたのかもしれない？(トレーナーの視線を避けるのはポケモンです...が最新作では視線避けの必要なくなったのでタイムリーではないですね_(:3」∠)_)
tako.icon視線を壁にしてDFSしたけどTLE,RE
おたふく.icon 最短経路まで求める必要があるものはDFSの必要があるけど、最短距離を求めるだけの問題はBFSの方が基本的に実行時間が短くなると思うよ。
まーす.iconyuichang.iconさんと同じ方針で考えていたが，求めるべきは最短経路で，行先が被ったときの処理が分からずに苦戦．
yuichang.icon幅優先のときは行き先が被っても最小値の更新がされる事は100%ないです
CarpDay.iconyuichang.iconさんと同じ方針だがTLEとれず．C++ならACだった？1回目はYuto.iconと同じくWAでした．入力例1を少し変更して実行して間違いを発見．視線をマークする方法を順次実行すると，2つの視線が交差する場合，2つ目の視線は交差までマークするけど，その向こうはマークされなくなることに気付く．コンテスト後，C問題で学んだように，in setを2次元リストに変更したらAC！TLE対処法として覚えておこう．．
おたふく.icon 事前に視線が届いている部分を!に置き換え、入力例で与えられている図の通りのものを作成してから、いつも通りのBFS。
〇F問題
CarpDay.icon見ることもできず．コンテスト後に読んだが，方針立たず．．翌日諦めて解説を読む．そんなDPあるんや！
おたふく.icon 解説を読み、桁DPというものを知る。勉強のしがいがとても有り過ぎるくらい重い問題でした。関数に処理を切り出すのはコードが見やすくなって便利ですが、関数呼び出しは少しだけ実行時間が遅いので、関数呼び出しの回数がとても多くなってくると無視できない遅さになる。