【ABC477】惨敗！！

こんにちは、柑橘です。
今回はABC477参戦記となります。記事を出すのが大変遅くなってしまい申し訳ないです......。競プロの勘は一向に戻る気配がありません。
あと手元のAC counterはいまだに謎に壊れっぱなしで、死んだ顔になっています。大昔にgeminiに全部環境構築を任せたのが完全に裏目に出ている気がします。

ABC477
- A問題
- B問題
- C問題
- D問題
- E問題（解けず）
- 結果

ABC477

配点：100-200-300-400-450-525-625

A問題

問題リンク：https://atcoder.jp/contests/abc477/tasks/abc477_a
推定diff：17（灰diff）
この日は帰省先からの帰り道でのコンテスト参加でした。もたもたしながらPCをスマホのwifiデザリングに繋ぎつつ、少し考えます。手早い書き方が分かりません。愚直に場合分けすることにしました。2:16、AC。
よくよく考えると、例えばvector<pair<char>> v={{'B','Y'},{'Y','R'},{'R','B'}};みたいにして、for eachで探索しても良かった気がします。何もかもが鈍ってる。

B問題

問題リンク：https://atcoder.jp/contests/abc477/tasks/abc477_b
推定diff：79（灰diff）
Nが高々100なので、愚直にforループを2回回せば終わりです。終わりなのですが、実装に、何故か手間取り......。
7:50、AC。

C問題

問題リンク：https://atcoder.jp/contests/abc477/tasks/abc477_c
推定diff：456（茶diff）
なんと、ここで2回WAを吐いてしまいます。「部分文字列」の意味を勘違いしてしまっていたのでした。おバカ！
部分文字列なので、Tの文字列長をnとして、S.substr(i,n)==Tとなるようなiを全て記録しておけばいいだけです。
40:32、AC。悲しすぎる。

D問題

問題リンク：https://atcoder.jp/contests/abc477/tasks/abc477_d
推定diff：946（緑diff）
......全く分かりません。マジでわかんない。
クエリ逆読みも考えますが、うまいこと処理できません。無為に時間が経ち、ふと、双対セグ木で良くない？　と気付きます。
vector<pair<int,char>> fd(n,{-1,'a'})のような配列に盤面情報を持たせて、q番目のクエリを以下のように処理することにします。
・Type1 query

int x; cin >> x;
if(fd[x].first==inf){ fd[x].first=q; }
else{ fd[x].first=inf; }

・Type2 query

char col; cin >> col;
for(int i=0; i<n; i++){ chmax(fd[i],{q,col}); }

要は各マスにつき{色が更新された時刻,現在の色}を持っておき、タイルが置かれた場合は更新時刻をinfにすることで、Type2をchmaxと捉えるとタイルの置かれたマスだけが色の更新がされなくなるのでした。どう考えても迂遠です。というか今気づいたのですが、単にvector<int>で色を管理していても双対セグ木で解けたような......。
さておき、Type2を上記のようにforループで回していると破滅するので、この全体にchmaxを行う操作が双対セグ木のapply操作で行えればいいわけです。
いや自分双対セグ木ライブラリ持ってねぇな......
仕方ないのでacl::lazy_segtreeに乗せることにします。ここで異常にもたつくなどして、結局83:16にAC。悲しいくらいひどい出来です。
悲しかったので双対セグ木ライブラリを作りました。
github.com
このライブラリを用いてACしたもの：https://atcoder.jp/contests/abc477/submissions/79599130

E問題（解けず）

問題リンク：https://atcoder.jp/contests/abc477/tasks/abc477_e
推定diff：1235（水diff）
明らかに'S->(頂点Nを経由せず)->T'と'S->(頂点Nを経由する)->T'のうち短い方を採用すればいいはずです。前者は単なる累積和、後者はダイクストラで出ます。
なぜか本番中、一切「ダイクストラ」のダの字も頭に浮かびませんでした。うぅ......