ABC353に出た。この前WSLを再インストールした影響でgdb入れてないままになってたり、競技中に一瞬WSLが壊れたりした。調子狂いまくり。全体に2重ループを外すだけみたいな問題ばかりだったのだが、それをやるのが遅くてだいぶロスした印象。

A: やるだけ

B: やるだけ

C: 普通に累積和で2重ループを外すだけなのだが、にぶたんめんどいなーと思って尺取りしようとして頭が壊れ、結局にぶたんした。えらい時間を食ってしまった。尺取りにしろにぶたんにしろ、単調性を利用するやつは単調性の向きを考えてこんがらがると死ぬ。

D: 順序があるのでソートはできない。$f(x,y)=x\times 10^{(yの文字列としての長さ)}+y$なのでこれも2重ループを外すだけだが、第1項がyに依存しているのが厄介。幸いyの長さはせいぜい$\log_{10}(\max y)\approx 10$通りくらいなので、yの長さごとに個数を数えれば$O(N\log(\max y))$くらいで解ける。

E: trie木

F: コンテスト中はGに行ったので触らず。コンテスト後色々考えてサンプルケースは全て合うコードを生成したが、WA出まくりでだめだった。

G: 街はグラフとかではなく直線上なのでセグ木類が使える。in-placeでDPすればよい。愚直にやると全ての街から市場の街への遷移を考える必要があるので$O(MN)$になるが、多少頑張って式を整理するとどうにかなる。気合でどうにかなる問題。

$DP[i]-C|i-T_k|+P_k$

→$DP[i]-C(i-T_k)+P_k\ (i \geq T_k), DP[i]-C(T_k-i)+P_k\ (i < T_k)$

→$(DP[i]-Ci)+CT_k+P_k\ (i \geq T_k), (DP[i]+Ci)-CT_k+P_k\ (i < T_k)$

これで$DP[i]-Ci$および$DP[i]+Ci$をメモって区間maxのセグ木に載せればよい。

---

cpprefjpを読み進めた。ちょっと今日は少なめ。昨日のVulkanのイベントの酔いがまだ覚めていない。

定数式からの仮想関数の呼び出しを許可

この記事には書いてないが、背景としては恐らくもはやコンパイル時に動的型を追いかけるようになってしまったので～というやつだろう。

型の文脈でtypenameの省略を許可

そもそもtypenameを書かなければならないという概念を未だにあまり理解していないので、よく分からないものがよく分からないまま消え去ろうとしているという感触だ。ただ、型も値も両方現れうる文脈ではまだ必要なのだろう。この「文脈」という言葉も未だに若干しっくりこないが。

可変長データを扱うクラスの効率的なdelete

そもそもdeleteを自分で管理するような低いレイヤのコーディングをしたことがないので全く知らなかった。inlined_fixed_stringというサンプルコードが置いてあるのだが、世のC++erは本当にこんなコードを「よく書く」のか！？？？？？