0.はじめに
A~Cは順調に解けたものの、DがDP使いそうなのでちょっと避けて
Eに取り掛かったらTLE1つと絶妙に解けませんでした。
手法を変えればよかったのですが、元のやり方に固執して
変に工夫して嵌り、久々にA~Cの3問のみ正解と、惨憺たる成績に。
レートも-25と急略し941とだんだん下がってきました・・・。
1.A - Spoiler
パイプの間の文字をパイプごと除去する問題。
インプットを文字毎にリスト化し、頭から見ていき
回答用変数ansに一文字ずつ入れていき、
はじめの"｜"から最後の”｜”まではansに入れないことで対応しました。
https://atcoder.jp/contests/abc344/submissions/51028396
2.B - Delimiter
いつも過剰なまでにリストの件数等教えてくれるアットコーダーが
急に不親切な感じになった問題。
まぁ、頭から入力をリストに入れてしていきつつ、インプットが
0だったらループ終了。
今度はリストを最後から開業しつつ出力ですんなりACでした。
https://atcoder.jp/contests/abc344/submissions/51035850
3.C - A+B+C
2個だけ足しとくとか、2分探索駆使とかいろいろよぎりましたが
制約でA,B,Cそれぞれ100個程度とわかったので、とりあえず
変数100個ずつで全部足し合わせた場合に時間が間に合うかを
テスト。
十分間に合ったので、以下の実装
【実装】
1.各入力読み込み
2.リストA,B,Cをそれぞれset化
3.セット化したA,B,Cから一つずつ取り出し
全組み合わせの結果を辞書Dに登録
4.Xを頭から読んでいき、Dにある場合Yes、無い場合Noを出力して終了
https://atcoder.jp/contests/abc344/submissions/51044925
（Dは飛ばしました。）
4.E - Insert or Erase
1時間以上なやんでもTLEを外せなかったでした。
解説を見て、方向性が違いすぎたことを知りやり直したら
うまくいきました。
【考え方1(TLE1をクリアできず)】
・辞書にキーA[i]、値に[str(i+20000000),200000]をセット
値の1つ目は位置、2つ目は自分の後に置かれた人につける番号。
例）1番目の値が３の時
キー：3、値[”20000000”,200000]
・Q回クエリーを読み込む
・クエリー1の時
-辞書Dにキーyを登録、値は、
[D[x]+str(D[x][1]),2000000]
辞書のxの値を結合した値を値の1つ目、値の二つ目は2000000をセット
-D[x][1]から1をマイナス
例）1番目の値が３の時、3の後ろに4をセットしたとき
キー：3、値[”20000000”,199999]
キー：4、値[”20000000200000”,200000]
例）さらに、3の後ろに5をセットしたとき
キー：3、値[”20000000”,199998]
キー：5、値[”20000000199999”,200000]
キー：4、値[”20000000200000”,200000]
・クエリー後辞書から、値の1個目とキーを取り出したtupleを
ansリストにセットし昇順ソート。
・並び替えたリストからキーを取り出して表示して終了。
冷静に考えると、値1個目が長くなりすぎるので
まぁ、うまくいかない気はしました。
解説を読んで、なるほどーと思いつつせこいTLE解消方法の模索
(コンパイラの変更とかC++に変換とか・・・)ではなく真面目に
方法の見直しをすればよかったと反省しました・・・。
【実装(解説を読んで作成)】
1.辞書Dを用意
キーに値、値にリスト[前の値,後ろの値]を持たせる
2.並びの先頭として、値-1、前の値-2、後ろの値A[0]を登録
3.並びの末尾として、値INF、前の値A[-1]、後ろの値INF+1を登録
INFは10**10
4.リストAの値を辞書に登録(以下i=0～N-1)
～前の値を登録
-1.iが0の時
-DにキーA[i]、値-1を登録
-2.iが0以外の時
-DにキーA[i]、値A[i-1]を登録
～後ろの値を登録
-3.iがN-1の時
-D[A[i]]の値リストに、INFを追加
-4.iがN-1以外の時
-D[A[i]]の値リストに、A[i+1]を追加
5.以下Q回繰り返し
-1.1行インプット(以下1個目をq、2個目をx3個目をyとする)
-2.qが1の時
-1.挿入する位置に今ある数(xの後ろの数)をaftxに保持
-2.辞書D[x]1にｙをセット
-3.辞書D[aftx]0にｙをセット
-4.辞書D[y]に[x,aftx]を登録
-3.qが2の時
-1.削除するxの前の数をprexに、後ろの数をaftxに保持
-2.辞書D[prex]1にaftxをセット
-3.辞書D[aftx]0にprexをセット
6.回答用リストansに[D[-1][1]]先頭の数をセット
7.チェック用変数chkにD[-1]1をセット
8.以下、D[chk][1]がINFになるまで繰り返し
(リストの値が1個の時は以下ループを通らない)
-1.chkにD[chk][1]をセット
-2.リストansにchkを追加
9.ansを出力して終了
https://atcoder.jp/contests/abc344/submissions/51099103
以上