頭破壊する回、みんな壊れててたすかった
70:59 6完 + 2ペナ 153位
A Five Integers
setにつっこむだけ、forとかset縛られるとちょっと嫌だな
(AC 1:05)
B Prefix?
めずらしく普通にやるだけ、SとTを1文字ずつ照らし合わせる
(AC 2:59)
C Chinese Restaurant
i-1,i+1はiがわかればよいので、とりあえず何回回したら自分の前に来るかを数えます
そしたら、i-1,i+1もすぐわかります
「xが条件を満たすのはiとi-1とi+1」というのを「i回回したら...」という風に視点を変えるのがちょっとだけ難しいかも？
(AC 7:40)
D Unique Username
いろいろ制限が多くてめんどくさいですね
まず、N個の文字列を並び替える必要があり、N≦8なので順列全探索をしようかなと思います
そうすると、間に何個か「_」を入れることになりますが、ある程度枝刈りしてあげれば、愚直にやっても間に合います
具体的にはN1の後に、1個加えるとして...、2個加えるとして...、という風に全部試してあげて、途中で文字列が大きくなりすぎたら打ち切ればよいです
こういう探索はDFSで書くのが一番楽だと思います
文字列の大きさが3以上を見逃しておりペナ...もったいない
(AC 31:28)
E Chinese Restaurant(Three-Star Version)
これむずい、やることはわかるけど添え字大変
Cでやったように「i回回すと自分の前に来る」というiを考えてみます
そこから、さらに1回ずつ回していくとどうなるでしょうか？
基本的には自分からの距離が1ずつ増えていきます
ただ、だいたい反対側に行ったところで距離が1ずつ縮まるようになります
これはよくある典型で「変化する箇所が少ないなら、変化する箇所だけ記録する」ことでうまく計算できそうです
ということで、変化する箇所を記録していきましょう
N=偶数の時は、反対のところにつくまで+1、反対のところを通り過ぎると-1となります
N=奇数の時が少し複雑で、+1,+1,+1,+1, ... +1, 0, -1, -1, -1, ...のような経過になります
あとはそれぞれの人について切り替わる位置をメモしてあげて差分を計算してあげればよいです
結構気を付けないといけないところが多いので汚いですが実装を置いておきます
(ptomはplus to minusのように切り替わる位置をメモしています)
(AC 52:55)
F Best Concatenation
ICPC2021 模擬地区-G Pizza deliveryやEDPC-X Towerなどで間接的に登場している手法なんですが、適切なソート関数をつくってそれでソートした後にごちゃごちゃするという典型があります
今回は2つの文字列を考えたときに、swapしてどれくらい増加するか？を考えます
もともとABだったものをBAに変えると、(BにあるXの数 x Aにある数字の和) - (AにあるXの数 x Bにある数字の和)だけスコアが増加します
気持ちとしては、これが+なら変えた方がよくてそうでなければ変えない方がいい気がします
ということでこれを比較関数にしてソートを行います
ソートしてしまえばそのままくっつけて愚直に計算すればOKです
見たことある典型だったのであんまり考えることなかった
(AC 60:59)
G Random Student ID
惜しいところまでいったけど、prefixの一致にsetを使うと死んだ
Trie木使わな過ぎて忘れていた...
総括
とりあえずARCで溶かしたものをだいたい回収した
