ABC 338

競技プログラミング

訓練

青 diff DP を 1,600 ~ 1,800 まで解いた。以降は解説 AC も難しくなって来た。特に ABC 214 F - Substrings の『部分列 DP』が解けず、第 11 回 PAST - K でも同じような問題を見た。典型として解けるよう噛み砕きたい。

ABC 338 に参加した。 5 完 (A ~ E) で青パフォだった。

A 問題では (up : lows) <- getLine のように分解する解答が良かった。

B 問題ではアルファベットの数を数えるために accumulate を使った。 group . sort の形でカウントを作る解答もあって、なるほどと思った:

main :: IO ()
main = do
  s <- BS.unpack <$> BS.getLine
  let cns :: [(Char, Int)]
  let cns = map (head &&& length) . group . sort $ s
  -- 以下略

C 問題では変数が 2 つあって、料理 A の数と料理 B の数が変化する。ここで料理 A の数が決まると料理 B の数も自動的に定まるため、料理 A の数を全探索すれば解けた。実装は zipWith や zipWith3 を使うと楽になる。 0 除算には要注意 (サンプルのおかげで助かった！) 。

D 問題では橋の数 \(N \le 2 \cdot 10^5\) に対して経路を構成する辺の数が \(M \le 2 \cdot 10^5\) もあり、単純な全探索では間に合わない。橋を切った際の辺への寄与 (左回りか右回りかを反転したときの経路長の差) を一括で計算可能にすれば高速化できる。

この計算は ABC 290 E における『主客転倒』に近かった。ただし今回はループの数が減ってもループの順番は変わらないため、別に主客転倒ではなかった。

E 問題は幾何っぽい見た目の問題だった。ループのことを考えるとややこしいので、まずはループを忘れて数直線を考え、弦を \([l, r)\) 区間であると捉える。すると弦の交差の有無とは \(\{ [l_i, r_i) \}_{i}\) 同士の intersection が存在するかを聞かれていることになる。ソートすれば 1 回の走査で解けた。ループなど無かった。

F 問題では重みが負の辺の処理に困った。実は Floyd-Warshall で全点間の最短距離を求めると、集合 DP に持ち込めたらしい。ただし Floyd-Warshall の計算の際にも、繋がれていない頂点同士を繋がないようチェックする必要があった。これは解きたかった……！

D 問題も E 問題も遅延セグメント木で解けたみたい。練習しておきたい。

Misc

近況

流行り病から回復した。まだ肌の感覚が鈍い。 24 時間 2 日酔いみたいな感じかも。

応用情報に受かっていた。 Chu! ノー勉でごめん。努力してなくてごめん。

`org-mode`

org-mode をタスク管理ツールとして使えるようになった。次はシェルの操作を org-mode から行って作業履歴を残すようにしてみたい。

SKK

SKK は IME 界の順張りであるという話を見てニヤニヤしていた。試せば 1 日で移行できると思う。やってみたい。

物欲

物欲が復活してしまった。

BOOX Palma が欲しい。 E-Ink 端末で動画再生すら滑らかとは……！　本当は E-Ink のモニタが欲しい。 Desung に期待か……！

Pro Display XDR が欲しい。 miniDivide が欲しい。本棚が欲しい。まともな椅子が欲しい。オーディオ環境も欲しい。高級なコーヒーミルが欲しい。

Flix

X で流れてきた Flix 言語をチラ見した。ある Podcast では『ワシがこの 25 年で学んだプログラミングのすべてが入っていてショックです』というようなコメントがあった。ワシもショックです。