ABC295 (2023/03/25)
〇A問題
Yuto.icon やるだけ
TTT.icon サンプルも通ってて他の方の解答を見ても方針は同じはずなのにWAが12個出ます。なぜなのか分かりません。本当に悔しいです...(泣)
Yuto.icon TTTへ．Wと比較してるものを出力してみたらこうなったけど，これおかしくない？
https://scrapbox.io/files/641efc03cc7daf001cf35b2b.png
CarpDay.icon 「Nが1または2ならば」は，if N == 1 or 2 とは書かないよ．
TTT.icon なるほど、ずっとorの使い方を間違えていました。お二方とも本当に
ありがとうございます！この機会で知れてよかったです。愚直にw == "and" or w == "not" ...とプログラムを変えたらACになりました！
Yuto.icon バグった時はとりあえずデバッガ使うかprintデバッグして中身を見てみるの大事ですね
CarpDay.icon例の5つの語を集合にして，ある文字列が集合に含まれていればYes．
おたふく.icon 問題の条件の5つの語のsetを用意し、1つでも含まれていたらYesを表示。
TK.icon↑と同じ
まーす.icon↑と同じ(配列の要素の指定をわすれてWAなったのはここだけの話)
〇B問題
Yuto.icon 愚直にシミュレーションするだけ．最初問題を理解してなくて，無駄に時間を浪費してしまった．ここら辺はスムーズに解けるようになりたい．
TTT.icon どうやって爆弾で消し去られた後の「.」に置き換えていこうか考えていましたがすぐに実装できなそうだったのでC問題に行きました。
CarpDay.icon「マンハッタン距離の範囲だけ」という処理は難しそうだったので，全マスを調べて爆弾が届くか判断．どの爆弾からも届かない場所に壁があれば壁を書いた．
おたふく.icon 爆弾のある位置を基準に、上と下に1マスずつ爆破範囲を広げていき、1マス伸ばすごとに左右に伸ばす爆発範囲を1マスずつ減らしていく。
TK.icon20*20のマスなので、答え用にもう一つ盤面を用意して、もとの盤面を参照して数字があれば答えようの盤面を全マス探索して、マンハッタン距離が条件を満たすようなインデックスのマスに来たら空白にする。もう一つの盤面を用意するときにシャローコピーになり、サンプルのひとつが通らなかったためcopyをインポートして強引にディープコピーにした。
〇C問題
Yuto.icon collections.Counter
CarpDay.iconソートして，前から順にペアになっているかチェック
TTT.icon 方針はCarpDay.iconさんと同じです。エラーをとるのに5回分の提出を消費してしまいました。ギリギリで1問だけ滑り込めて本当によかったです。
おたふく.icon CarpDay.iconとTTT.icon同様。
TK.iconsetを用意して、リストを前から見ていき、集合内になければ追加、あれば削除してカウントを加算
まーす.iconBより簡単(Bは解いてない)。解法は↑と同様(集合の考え方)。
〇D問題
Yuto.icon 累積和とか累積XORとかdpとか尺取りとか余事象とか色々考えたけど上手くいかない．
Yuto.icon 解説見た．累積やXORの考え方は良かったけど， 区間の数え上げ→個数数えて組み合わせという発想が出来なかった．
CarpDay.icon方針も立たずにコンテスト終了．範囲DPだと$ O(N^2)になるのであり得ない．数値が高々10通りなので，各数値について判別して併合する？それでも範囲の個数は$ O(N^2)なのでNG．諦めて解説見る．うーん．思いつく発想力が欲しい． 偶数個と言えば，個数を0/1で管理．XORやMOD利用．重要．
おたふく.icon とりあえずTLE出ると思いつつも確実に正解は出せそうなコードを提出しておきました。
TK.icon愚直の探索がΣｋになるため10^10になるため違うなと思い、少し前の文字列内の回文の数を数えるみたいに範囲を拡張していくようなイメージで探索すればうまくいくのかなと思ったが、良い探索が見つからなかった。
〇E問題
Yuto.icon ちょっと見て期待値DPかな？，無理そうだったのでDに戻った．
CarpDay.icon前問に同じく方針も立たずに終了．解説読んで，重要そうな確率の計算式変形を知る．なるほど．二分探索のイメージだね．
TK.icon見に来たが、Ｄの方が方針が立ちそうだったのでＤへ戻る。結局Ｄも解けていない。
〇F問題
CarpDay.icon合っているか自信がない方針を立てたものの，時間内に実装すらできず．2番目のユーザ解説と同じ考えだったが実装力不足．公式解説にある値を求める問題 → 二分探索は，頻出なのになかなか身に付かない．反省．
Yuto.icon ちょっと見たけど無理そうだったのでDに戻った．