脳log[20220226]

2022年02月26日 (土) [AtCoder] 今日は ABC241(Sponsored by Panasonic)があった。結果は ABC の３完。40 分考えて D 問題「Sequence Query」が解けなかった。途中から E 問題「Putting Candies」に浮気してそちらは 20 分で解けたけどコンテストは終了していた>提出 #29711639 (AC)。これは ABC175-D「Moving Piece」と同じ問題だった(どちらかといえば易しいくらい)。そのまま F 問題「Skate」にとりかかって 25 分で解けたけどコンテストは終了していた>提出 #29714203 (AC)。これはやるだけの問題だった。３完だけど５問解けたのでヨシ！■D 問題>提出 #29718230 (AC / C++)。C++ だと multiset と lower_bound/upper_bound が使えますか、というだけの問題になるんだけど、Ruby で通してる人がいる以上 C++ は甘えなんだよなあ。Twitter で読んだけど ABC217-D「Cutting Woods」を Ruby でまじめに解いた人は対策ができていたらしい。自分はテストケースの悪意を読んだヒューリスティクスで Array だけを使って通したので対策はなかった>提出 #26804547。■C 問題「Connect 6」も実は遅い言語には厳しい制約で、盤面の大きさ 100 万に対して係数が 24(=6×4) は 3 秒でもさすがに通らないだろうと思われた。縦と横だけテキトーに高速化するのに 45 分かけて WA も一度出しているあたり、がんばりましょうという感じ>提出 #29690673 (AC / 2088 ms)。■E 問題と F 問題の軽さに対して C 問題が重く D 問題が重すぎた。どんな本でもはじがきと目次と１章から順番に読む以外の発想を持たない人間のことを考えて問題列を構成してほしいものだ(わがまま)。■■■さっき書いた。「Twitter で読んだけど ABC217-D「Cutting Woods」を Ruby でまじめに解いた人は対策ができていたらしい。自分は(略)なかった」 嘘だった。別解として BIT バージョンを通していた>提出 #28790707 (AC)。「対策」とは値から添字を逆引きする BIT のあまり一般的ではないメソッドのことであり、これを通したのがちょうどひと月前だってのに、どうして今日通せなかったの？■@2022-03-01 20220228で (30,60)-木を使って通したあとだけど、コンテスト中の最初の方針であった BIT を使っても D 問題を通したよ>提出 #29790983 (AC / 1944 ms / 後註)。Hash ベースの BIT でギリギリ間に合ってるのに最初の提出(Array ベースの BIT を使っていて有利)で RE/WA/TLE になったのなんでだろう。ともあれ、WA の原因は BIT の使い方に間違いがあったからなんだけど、貼り付けた自分のコードが信用できなくてサンプルを合わせるときに手を入れる場所を間違えたんだな。RE/WA だけならデバッグをがんばれたけど TLE もあったので諦めてしまった。□(註) さっきの提出のコメントに嘘があった。「アクセス可能な範囲(0..@n-1)なら」の正しい範囲は 0..@n-2。スクリプトは合ってる。コメントだけ嘘。