脳log[20220221]

2022年02月21日 (月) [AtCoder] 復習。おとといの、だけど前々回の ABC、デンソークリエイトプログラミングコンテスト2022（AtCoder Beginner Contest 239）-F「Construct Highway」(青 diff)。頂点数と辺の数から木であることを読み取り十分に利用しなければいけない。コンテスト中唯一の提出は終了３分前のこれ>提出 #29471962 (WA×18 / AC×11)。木である条件が十分に詰められていなかったし、効率にも配慮できていない(ループ中の find メソッド)。■数時間後の提出 #29479636 (TLE×7 / AC×22)。効率にも配慮したつもりだったけど当然起こりうる状況が想定できていなくて、24 行目の flat_map が予想外に非効率で TLE。単要素の配列が信じられないくらい大量に作られることになる。■さらに２時間後の提出 #29483013 (AC)。この問題のキーであるあと１本だけ辺が欲しい連結成分を特別扱いすることで効率を改善して AC。おまけにソートもなくなった。ところで、不可(-1)を出力して終了する no! メソッドの呼び出しが８か所もあるって多すぎだよね。■今日の提出 #29561496 (AC)。no! の数を５個に厳選してそれぞれに理由を示すコメントを付けた。保険のための余分な no! はもうないと思う。もっと減らしたかったけど 22 行目の no! if U[a,b] の no! を取り除くとダメになるケース(8 4／3 3 3 1 1 1 1 1／1 2／1 3／2 3／7 8)がある。この提出 #29483417 (WA×1) を阻んでいる random_21.txt が同等の(無駄な辺と森化による辺の必要数の減少が相殺する)ケースだと思う。■■■E 問題「Subtree K-th Max」。最近似た名前の問題がありましたね>「Prefix K-th Max」。一読して表現の微妙な変化に気がついたんですよ。ABC234で「K 番目に大きい値」という表現だったものが ABC239 では「大きい方から Ki​ 番目の値」になっていた。それが「中途半端な値は見ようによって大きい値でもあるし小さい値でもある。自分に言わせればそれは単に「大きい方から K 番目の値」なんであって、大きい値でも小さい値でもない」をうけての変化だとは思わないけど、自分が理解しやすい表現になっていたのは間違いない。それなのに AC 前の５分で 2 WA しました(WA、WA、AC)。読んで、表現の変化にも気がついて、でも結局間違えるんだ。手癖で書いてるってことなんだろうなあ。■「AtCoderの公式生放送「あーだこーだー」 第51回 - YouTube」を聞いていると E 問題「Subtree K-th Max」に関連して Wavelet Matrix の単語が何度も聞こえてきた。E 問題では K の上限が意図的に小さく抑えられていて、ここを突破口にして解けよ、というヒントがあからさまだったけど、さもなければ Wavelet Matrix を使って解くことになったらしい。Crystal では通ってるぽいのに Ruby で TLE になるの悔しいよね。通ってほしい。参考図書『[単行本] 岡野原 大輔【高速文字列解析の世界――データ圧縮・全文検索・テキストマイニング (確率と情報の科学)】 岩波書店』は持ってるだけは持ってる。WEB+DB PRESS vol.42 の記事を読んで著者の名前を覚えていた。