案の定というかすっかり冷えっぱなしで1900台行ったり来たり。あめんばーです。
原因はわかりきってるというか普通に最近やれてないっすねー。
プロジェクトでムチャ振りが増えてきたり、採用側のお仕事が来てで張り切り過ぎたり、VRChat側で改変を頑張ったり、あと実はいろいろあって論文の投稿をすることになったり。絵も描きたいっすね。
そういえばVRChatでラタリュールくんの改変を、わりと頑張って行ったのでその技術メモもまとめたいですね。VRC改変もすごい人多いので自分如きがなにしとんって感じもあるかもしれませんが。
黄色に上がれたのもやっぱりあの偶然が重なっただけだなー感出てきましたし、長い停滞誰にだってある感じもしますので焦らずやっていけたらなーって思います。 そもそも自分の中で橙以上の人、本当に「何かが明らかに違う」って感覚非常に強いので、今のままじゃダメな気がすると言いますか。なんかそういうところでどういう違いが現れるのかなーとか、いろんな話集めたりとか、あとはまた夢中になれたらなんか見えてきそうっすね
とりあえずせっかくなので今回のABC-Fは説明してもよさそうかなと。 あとE質問の通知来なかったのナンデ………内側含めないよって終わった後に気づいた… コンテスト中解けはしませんでしたが、ケアレスミスだけで感想会中もそこそこ説明できましたので。
とりあえず1次元で考える
簡単な問題に落とし込んだり、TLEを気にしない場合の解法をひとまず考えてどの過程を削るかとか考えるの、わりと大事。
この問題は1セットの動きを見た後に、同じ動きをした際に重複してしまうマスが発生してしまうことが考えものです。
というわけで「とりあえず1セットではx方向にしか動かない」という前提で、さらにy=0と固定した1列で考えてみます。
まあ他のy列から回り込むことが無いので、一歩ずつ連続するということは発生しなくなるのでその前提でいきましょう。
とりあえず上図のような数直線を掃除したとしましょう。Sから始まってGで終わり、黄色のマスを掃除しました。
この1回で+2移動しています。
ここで注目するのは、この移動分2の余りごとに「鎖」を作ることができます。今回は2つ。
今回のケースの場合、kの値にもよりますが上のものは上のもの同士で、下のものは下のもの同士で重複しあってくれます。 例えばk=3でしたらこんな感じに追加でオレンジのマスが掃除できますね。
k=5ならこんな感じ。なおさら重複が増えちゃってます。
ではこのオレンジのマスがどのように追加されているかですが、困るのは重複してしまっている分です。
ではどういった場合に重複が発生するかというと、隣り合った鎖の幅がk未満である場合ですよね。
というわけで下記の通り、一回目でそれぞれの鎖の何番目が通るか（要は黄色いの場所）インデックスを取得してみます。
こうすると一目瞭然で、黄色と橙で塗られた個数の合計と言うのは、鎖ごとに
と見れる。一番端だけは際限がないのでしっかりとが加わるので。お気を付けを。
二次元に広げて鎖を作る
というわけで、これを二次元に拡張して鎖を考える。
基本的な考え方は同じで、SからGへの移動が二次元になりつつ、同一の鎖上に分類される点毎に、何回分の幅があるかを見ればよい。
ただ、先程の例とは違い、二次元で鎖ごとに端の座標を見つけるというのはあんまり容易ではない。
さらに動きに正と負があるので、非常にややこしいことになってしまう。
しかし思い出してほしい。先程の式、鎖ごとの幅しか見ていない。
つまり基準点はどこでもいい。
つまりつまり正負の判別が不要になるほど遥かに遠くな位置を基準にしても全然問題ない。
もっともっと言ってしまえば正負逆にインデックスを取ってしまっても答えの式自体に影響はない。 正負が混じって3/4と-3/4が同じ0で出てきてしまうことのほうがよっぽど問題である。
というわけでxの遥か遠くの点を基準に取り、その点が鎖の何番目かをざっくり計算してしまえばよい。
そう。幅さえあってればいいのでざっくりでよい。
基準点はめちゃくちゃ小さいことになってしまうが、その辺りの値はmapでいい感じに取りましょう。
あとは鎖ごとに先程の式を適用する。
一回目の移動でxが全く動かない場合はyで基準点を取ることになるので注意。
xもyも全く動かない場合はそんなの1回目のやつだけ合計すればいい。
string s;
ll k;
cin >> s >> k;
map<pair<ll, ll>, bool> bm;
pair<ll, ll> sl;
bm[sl] = 1;
REP(i, s.size()) {
if (s[i] == 'L') sl.first--;
if (s[i] == 'R') sl.first++;
if (s[i] == 'D') sl.second++;
if (s[i] == 'U') sl.second--;
bm[sl] = true;
}
if (sl.first == 0 && sl.second == 0) {
ll ans = 0;
for (auto b : bm) ans += b.second;
cout << ans;
return 0;
}
map<pair<ll, ll>, vector<ll>> dm;
for (auto b : bm) {
if (!b.second)continue;
auto [x, y] = b.first;
ll slide = sl.first != 0 ?
(x + 1e8) / sl.first :
(y + 1e8) / sl.second;
auto bn = make_pair(x - sl.first * slide, y - sl.second * slide);
dm[bn].push_back(slide);
}
ll ans = 0;
for (auto b : dm) {
auto [bs, bl] = b;
SORT(bl);
if (bl.empty())continue;
ans += k;
REP(i, ll(bl.size()) - 1)
ans += min(bl[i + 1] - bl[i], k);
}
cout << ans;
