ABC 243 D - Moves on Binary Tree から考える競プロでのクソデカ数

(2¹⁰)¹⁰⁰の処理ってなんだよ(笑)

雑感です． 解説ではないのでわかりにくくても許してね．振り返りを記録してるだけなので....

最初に取った方針

+1 の前に出てくる ×2の数(U(-1),LR(+1)で処理したもの)と後に出てくる×2の数を使って+1が出てくるごとに何倍すればいいか(or 足さないか)を記録する

→多分できるんだろうけどバグる

※誰か実装できた人教えてください，僕は無理でした

いわゆるゴリ押しってやつ

クソデカ数がでてきたときの気持ち

1. の操作(ループ・配列)ともにしない！
2. 直接シミュレーションしないで規則性を見つける！
3. 圧縮できる情報は圧縮する！
4. Pythonを使う
5. 文字列として扱い数字として見ない！←今回はこれ

long longに収まらない桁の足し算掛け算とかはstringで筆算すればできますよね....授業でやらされたの思い出しました．

正解解法

ということで1時間考えたのでAtCoderの解説読んでいいでしょうと言う感じでサクッと正解しました．解説読みゃ一瞬でしたね．どうやって思いつくんだ....(勘の鈍りを感じる)

文字列で考えるがわりかしこの解法にたどり着きやすそうだなと思いました．

1. を2進数で表して，string Tに入れる(高々60桁)
2. Uが来たらpop_back() *1
3. Rが来たら0を，Lが来たら1を追加する
4. 最後にbitを10進数に直して出力
   1. 直し方はans*=2と(+T[i]-'0')を繰り返すだけ

できました．この問題から得ることはそこまで多くないので振り返って次にいこうと思います(1hくらいかけてしまった......)

*1:C++stringに末尾消すって関数あるの初めて知った