脳log[20230228]

2023年02月28日 (火) [AtCoder] 日曜にあった AtCoder Beginner Contest 291（Sponsored by TOYOTA SYSTEMS）のふりかえり。■A 問題「camel Case」。ASCII コードで大文字小文字は特定の１ビットを見ればわかる(それ以外のビットは共通)。■B 問題「Trimmed Mean」。フィギュアスケートとか芸術競技の採点方法っぽい？ ソートして真ん中を取り出す。■C 問題「LRUD Instructions 2」。賢い判定方法があるかなとちょっと気にしてみたけど、普通にメモを取ってシミュレートした。■D 問題「Flip Cards」。D は DP の D！ 直前のカードが A のときの場合の数と B のときの場合の数から今回のカードが A のときの場合の数と B のときの場合の数を出す。初期値をどうするか迷った。A のときの場合の数を 1、B のときを 0 にして、答えは (A のとき+B のとき)%998244353 にしたら合っていた。■E 問題「Find Permutation」。ABC285-D「Change Usernames」を思い出す問題。自分より小さい要素がない要素を順位確定要素としてキューに追加して他の要素の前から取り除いてはキューを伸ばしていった。ただし、どの時点でもキューの長さは１でなければいけない。２つ以上の要素がキューにあるとどちらが小さいかわからない。キューの長さが１ずつしか増えないとわかったときにちょっとせこいことを考えて、キューをそのまま答えの配列にしようとした。残念ながらそのまま答えにはならなくて、順番と添字を入れ替える処理が必要だった。自分の提出にはバグがあるような気がしていて、キューが途中で途切れたときに対応できていないと思う。運良くそういうケースがなかったのかな。E 問題に関連してトポロジカルソートの語が頻出している。トポロジカルソートがわかるなら ABC041-D「徒競走」(青 diff) が埋められないなんてことはないはずなんだよなあ(まだ埋められていない⇒わかりません)。■F 問題「Teleporter and Closed off」。都市 k を通らないケースというのは、都市 k-M+1,k-M+1,...,k-1 から都市 k+1,k+2,...,k+M-1 へ飛ぶ 1+2+3+...+(M-1) 通りが上限であり、M は 10 以下なので、各 k について１つ１つ調べて良い。あとは k の手前の都市へ移動する最小回数と k の奧から移動する最小回数が１ステップでわかればいいので、前からと後ろからの２回 DP をやっておく。考察にはそれほど悩まなかったけどバグ取りをしたりしてるうちに気が付いたら 45 分経っていて驚いたよね。しかも TLE だった。2115 ms であり 22xx ms ではないから 115 ms を削る小手先の変更を２つ入れて AC。ペナルティと合わせて 9 分のロスだった。それ以前に時間をかけ過ぎていて E までを 30 分で片付けた貯金がパーなんですよ。■G 問題「OR Sum」は制限時間８秒がやばいよね。考察であっさりスマートに答えを出す系の問題ではない。あきらめちゃうよ。■自分のすべての提出。コンテスト成績証。■E 問題への提出の潜在的バグについてお風呂で考えてきた。キューが途中で途切れるのはどういう場合だろうか。たとえばグラフが複数の連結成分に分かれているとき。これは始点が複数あると検出されるならバグには当たらない。しかし始点がなかったら。１つまたはそれ以上の連結成分が環状部分を持っているなら、キューは途切れる。バグか？ おそらくそういうケースは「入力に矛盾しない A が存在する」という制約により除外されている。潜在的バグはバグではなかったしテストケースにも不備はなかった。そこまで見切った上での割り切った実装(９行目の if (1..N).all?{|n|)だったらかっこよかったんだけどな。ABC285-D「Change Usernames」のときも「入力制約のきれいさに助けられた」って書いてるんだよなあ。