ABC305 (2023/06/10)
〇A問題
おたふく.icon あらかじめ、補給所を列挙。適当にfor文を回し、最も近いところを求める。
Yuto.icon 移動量をループで回してn+iとn-iの先に着いた方
TTT.icon Nを5で割った余りが2以下の時とそうでない時とで場合分けしてそれぞれ適切な形で答えを出力するようにしました。思いついてから書き終わるまでにかなり時間を使ってしまいました。
tako.icon右の補給所の位置と左の補給所の位置を求めて現在地との差が小さいほうを出力。
CarpDay.iconTTT.iconさんと同じです．
yuichang.iconおたふく.iconさんと同じ
Kaplam.iconNを5で割った余りaと、それを5から引いたものbとで、aの方が大きかったらN+b、小さかったらN-a
yan.icon2<N%<8の場合は5、それ以外は0とした
〇B問題
Yuto.icon 言われたことをそのまま実装．丁寧に書きすぎて少し時間がかかった
おたふく.icon B問題からテンパりまくる。手打ちでA - Bのように距離を用意しておいて、for文で回し距離を求める
TTT.icon Aと3, Bと1, Cと4, ...のように、開始点とそこからの距離とのペアで考え、スライスとsumとordを上手く使って答えを出力しました。
CarpDay.iconAからの距離（累積和）を手計算してコードにベタ打ち．差の絶対値を出力．
yuichang.icon累積和で差を求める
tako.icon距離をリストに順番に入れておき、始まりから終わりまでの合計を求める。B問題だから計算量適当でいいやと思い累積和は使いませんでした。
Kaplam.iconCarpDay.iconさんと同じ
yan.icondefaultdictを使うのはここしかない！！と思い使ってみたら思ったかすんなりうまくいった。
〇C問題
Yuto.icon 最初制約をちゃんと見てなくて，B問題のノリで計算量を考慮せずに解いて提出したらTLE．計算量を見てみると$ O(HHWW) = O(10^{10})くらい．それは無理か．．となって，累積とか使って高速化頑張ったけど，A,B,C,Dの4重ループが消せない．そのまま試合終了
おたふく.icon コードが汚すぎてデバッグが...。他の人の発想を見て、その手があったかと思わされました。B問題の要領でまず長方形の左上を見つけ、そこから欠けている場所をif文で愚直に探す。
yuichang.icon各行の'#'を数えて欠けている部分を見つける。冗長になりすぎて時間食った
CarpDay.icon各行・各列のクッキーの個数を求め，最大値を取って長方形の大きさを確定．行・列の個数が1少ない位置を探して出力
TTT.icon #を含む行を集めて、その中で#を含む個数が最小の行をyとし, その行以外で# を含む行から、#の連続する開始列と終了列を見つけてから、y行での開始列と終了列との間にある.の列をxとして、(x, y)を出力しました。
tako.iconクッキーの座標の最小値と最大値を求めて長方形を探す、その長方形の中の.の位置を出力
Kaplam.icon縦と横の最大最小求めて長方形を探索、最大と最小が同じだったら縦横1の行か列の中で探索ってやったけど場合分けしなくても解けた気がする
yan.icon縦、横ループ内で#を見つけたら「その列!=次の列」の場合は「その列」をansx,ansyに記憶し#の列が終わるまでループする。その後print(ansx, ansy)した。が、waもreも出てしまった。waは#が2列の場合解が「その列!」か「次の列」かの判断が上手くできていないためだと気づいたが直す時間が足りなかった。それに文字列の読み込みで、横列はいつも通りできるが縦列の文字列の読み込み方がわからず、愚直にforで回して読み込んだ。いつかは忘れたが縦列の文字列を扱う問題がabcであったが、結局どうやってたか理解していなかったのだと思う。
〇D問題
おたふく.icon 二分探索を用いてlとrがどこにいるかを求めておく。愚直に実装するもWA、TLE。毎回for文を回し、l:r区間内に収まる睡眠時間を計算するのではTLEになってしまうので、あらかじめ累積和を計算しておき工夫する。
Yuto.icon 最初l:r区間内に就寝：起床が一組しか無いと勘違いしていた．実装途中で気付いて修正．左端を二分探索で求めて，右端を尺取り的なイメージで伸ばしていこうとしたけど，実装力が無くて書ききれなかった．そもそもこの方針が合ってるのか分からん．
yuichang.icon二分探索だとは思ったが実装できずEを見る
CarpDay.icon二分探索でどの区間に入るか獲得．睡眠区間なら，含まない部分を引いておく．睡眠時間のけ累積和を求めておいて対象範囲内にある睡眠時間の合計を求める．
tako.icon与えられた時間の差から寝てない時間を引く感じでやりました。デバッグ用のprintを消し忘れたWA1回がもったいない。
Kaplam.icon計算量的に二分探索！ と張り切って頑張ったもののうろ覚えとフィーリングで組んだ二分探索くんは答えを返してくれなかった。
〇E問題
yuichang.iconbfsした。TLEだと思って投げたらTLE。枝刈りして頑張ったのに。。
CarpDay.icon警備員がいる点から(体力，点）の情報をヒープに入れて，ダイクストラのようなBFSを実行．自信あったのにWA．．．サンプルを丁寧に見直すも原因が分からずF問題へ．終了後，ふと初期配置の警備員より他から移動してきた警備員の方が体力が高い ケースがあることに気付き，修正したら無事AC．コンテスト中に気付きたかった...悔しい
Yuto.icon 問題は理解したけど愚直解以外に方針が立たない．
おたふく.icon 最初に問題を見たときに始点が複数あるbfsだと思ったので、多点bfsで実装した。サンプルは通ったがWAが半数ほど。CarpDay.iconと同様体力が多い警備員が後からその頂点に来た時に対応できていなかったので、heapqを利用して体力が多い警備員から行動を開始できるように実装してAC。
〇F問題
CarpDay.iconインタラクティブ問題．内容はDFSなのでできるぞ！と思ったが，今度はRE地獄．なぜ？終了後，落ち着いて別の簡単な例で，間違いを発見．帰りの移動を出力していない．修正したら無事AC．悔しい2．
Yuto.icon 問題は理解したけど愚直解以外に方針が立たない
おたふく.icon インタラクティブ型のDFSを実装するだけ。10分程で一発AC。嬉しいが、C, D問題よりも個人的には簡単だった。
〇G問題
CarpDay.iconG問題だし文字列だし，絶対難しいと思い，あまり考えずに解説見たらDPと書いてあったので考え直す（実際はちょっと違う気がするが）．状態推移行列をダブリング使って計算．numpy使って実装するも，WAが取れず（恐らく行列積でMOD取る前に桁溢れ）．他人ACコード参照して，行列積・剰余を実装したらAC．行列計算はいつか使いそう．