(N+2)/5*5 一発で二捨三入できた。切り捨て切り上げを定型で覚えているだけで考えることをしないから無駄なことをする。……というのもちょっと違う。(A+B-1)/B と (A-1)/B+1 がどうして切り上げになるのか過去に考えたことがあるから (A+2)/5 もわかる。ボーダーは動かせる。■B 問題「ABCDEFG」。もっともあほな書き方をしても 42 通りなので好きに書く。累積和を用意するときに要素数が少ないからうっかり暗算しそうになったけど、間違えるから機械にやらせた方がいい。■C 問題「Snuke the Cookie Picker」。人間はなんとなく答えが出せるけどコンピュータに出す具体的な指示は案外難しい。すべての行と列で上端下端左端右端を検出して数が多いものを採用する解答を提出してランタイムエラーを出した。最小ケースを作ってみて気が付いたんだけど、１対１で同数になるので答えが出せない。たとえば上端には最小値、下端には最大値を採用するのが正解。■D 問題「Sleep Log」。方法はいくつかあるのかな。睡眠時間の累積和に適切な座標を割り当てて二分探索ができればいいように思った。でも実装方法(座標圧縮？)が見えなかったのでもうひとつの案。累積睡眠時間を数えながら各クエリの入りと出のときに値を記録した。同時に扱う時刻が睡眠時間とクエリを合わせて３つあって、組み合わせて正しい式を得るのが難しかった。クエリの入りと出の２か所に書いて揃って間違えた。それは提出前に修正できたけどデバッグ出力の消し忘れで All WA をくらった。人間は都合良くデバッグ出力を無視してサンプルの答え合わせができるんよね……。■E 問題「Art Gallery on Graph」。これは簡単。BFS で頂点を訪問するだけ。罠があるとすれば、グラフを勝手に木だと仮定してはいけないということと、何も考えずに BFS を繰り返して値の更新が続くと O(KN) で TLE になる可能性があるということ。プライオリティキューで提出して２秒ぎりぎりで AC だったけど、BFS を(１回だけ)やりながら適時キューに警備員が立っている頂点を追加するようにするともっと余裕があった。ここでは出力形式を間違えてまた All WA をくらった。■F 問題「Dungeon Explore」。制約からもこちらに許された操作からもグラフをしらみつぶしに訪問するような探索が書ければいいとわかる。隣の頂点にしか移動できないから探索は BFS ではなく DFS。あとは E 問題と似た文面が見えることからわかるように、勝手にグラフが木だと想定しないようにだけ注意。なんでこういう注意が必要かというと、「木ではない木ではない」と唱えていないと勝手に木を想定したコードを手が書いてしまうからだ。E と F が似たようなグラフの問題でどちらも軽い問題だったから、F 問題を提出した後で F 問題を開いて解こうとして混乱したよね。■最近また落ち目だったからか解けるものを(序盤でそれなりに苦戦しながら)解いただけでレートが上がったのは微妙な気持ち。コンテスト成績証。■■■@2023-06-15 F 問題。自分の提出 #42157034 は 10 行目と 11 行目がやばく見える。10 行目は隣接頂点リスト全体を走査しているし、11 行目は隣接頂点リストがソート済みだということを無視して、頂点 N を目指しているというのに最も小さい頂点番号から順に訪れようとしている。10 行目は「DFSを非再帰に書き換えるとTLEするようになったという心霊現象」について 20221125 に書いたまずい書き換えの例と同種のミスだ。たとえば入力が頂点１を中心とするスターグラフで、頂点 N だけが頂点１から距離２の位置にあるとしよう。長さが N に近い頂点１の隣接頂点リストを N 回近くスキャンするのは O(N^2) でいかにもまずい。だけど実際には問題にならないだろうということも予想できて、当日は解答を作成しながら制約を再確認したりしていた。つまり、提出コードがどういう形で書いてあるにせよ、頂点１の隣接頂点リストを N 回近く標準入力から読み込むことは最悪の場合に避けられないのであり、それでも TLE にならないような制約が書かれていないかを確認していた。なかった。でも実際にはまずい解答でも問題が起こらないような入力だったので AC だった。まずい書き方をしたけど実際にはまずくなかったのだという話。■……でもないのかな？ 日記に「(そんな制約は)なかった」と書くに際してまた問題文を読んだけど、これまで見たことがない「
この問題のジャッジはアダプティブです。つまり、制約および以前の出力に矛盾しない範囲でグラフの形が変わる場合があります。」という注意点に気が付いたよ(今です！)。入力が頂点１を中心とする完全なスターグラフだったときに自分のまずい提出は(アダプティブに)救済されようもなく TLE していただろう(一番最初の入力で頂点 N への辺が示されているから)。あまりにも間抜けすぎるのでそんなうっかり提出を弾くためのケースを用意しようとは考えなかったのかな。あぶなかったね！