ARC 169 / 大敗

競技プログラミング

訓練は特に無し、 AHC も不参加となった。

ARC 169

ARC 169 に参加した。初の 0 完を体験した。

A 問題 では、そもそも読解に失敗していた。 $P_i < i$ より、浅い位置のノードから親 (P arent) に向かって順番に出力していくことになる。限りなく多い回数操作を行うため、最も深いソースからの出力の和 ($/= 0$) の符号が答えとなった。

B 問題 ではすべての $[l, r]$ 区間に対して $f(l, r)$ を求める必要があり、主客転倒または累積和 + 平面走査を考えた。しかし結局 $O(N^2)$ 解法しか思いつかなかった。

公式解説は尺取り法 or 2 分探索 + DP で、 constructrN が上手くハマった。計算のパターンとしては初で、まだ上手く言語化できない。

いずれもシンプルな解法に帰結し、良問であると感じた。完敗だった。でも初心に帰れて面白かった。

Misc

Haskell

Haskell のアドベントカレンダーが例年通り盛り上がっている！　衰退ダ〜などと日記で零して申し訳なかった。

僕の投稿は進捗 30% 程度で、そろそろまずい。でも書き切れる目処は立った気がする。

Keyball 44

Keyball 44 が初見の人に簡易キーボード・省スペースのキーボードと認識されたのが面白かった。実際に使ってみると、むしろ片手間では操作できないヘビータイプな存在だ。