結果

f:id:ngtkana:20200314234334p:plain

非常に難しかったとはいえ、明らかに得意セットです。これはせめて全完は間に合わせる必要がありました。悔しいです。

✔A - Kth Term

コピペをして vector a = { ... } です。普段とは雰囲気が違います。振り返れば、このあたりで、鐘鳴りぬべし（ただごとでなさそうです）ということを、悟るべきでした。

✔B - Bishop

盤面が十分に広ければ、市松模様で同じ場所はすべていけますから、2 で割って切り上げです。

片方が 1 のときには移動ができません。コーナーケースです。（引っかかった人です。）

これに引っかかったあたりで、かなりこころを入れ替えて望みました。この切り替えはファインプレーです。WA でよかったかもしれません。

✔C - Sqrt Inequality

両方とも 0 以上ですから、2 乗からの移項で、 √ (ab) = c - a - b としましょう。

次に、もう一度 2 乗なのですが、右辺が正とは限りません。注意です。

ところでこの問題は浮動小数点数でもがんばれたのでしょうか。私には難しいです。

✔D - String Equivalence

ある長さまで生成したら、その次の文字は、今まで使ってきた文字か、もしくはその次の文字です。この規則で伸ばしていけばよいです。実装次第ではソートされた状態になります。

✔E - Three Substrings

制約が小さいですから、位置関係を全探索です。先頭が a, b, c の順になっているとして良いです。このとき、(a,b) は被っていますが、(a,c) と (b,c) は、いずれか一方のみである可能性があります。

判定は、(a,b),(a,c),(b,c) ですべて独立に行えます。同じ判定を何度もしますから、判定を前計算です。たとえば (a,b) がどれくらいずれていてよいかは、2000 通りくらいあり、それぞれ 2000 回程度の比較で計算ができます。

これがあまり通されなかったのは不思議なのですが、判定を前計算すると速いというところが思いつきづらかったのでしょうか。

✖F - Fractal Shortest Path

悔しいです。

避けなければならないものは高々一つです。大きい方から順にためします。

壁 L をチェックです。 I0=i0/L,I1=i1/L,J0=j0/L,J1=j1/L と置きましょう。 I 同士が等しく、J 同士も等しければ、L / 3 をチェックです。逆に異なる＆異なるでしたら、理論値でフィニッシュです。

I 同士が等しく、J 同士が異なるとしましょう。 I%3==1 であり、J の差が 2 以上ならば壁 L に阻まれます。このとき、コストは min(i0%L+1,i1%L+1,L-i0%L,L-j0%L) です。そうでないときには、L / 3 をチェックです。このように繰り返します。繰り返しのたびに、i の方まで違っていないかをチェックです。

言葉で説明すると難しそうなのですが、ソースコードはとっても簡単です。

#include<bits/stdc++.h>
using lint=long long;
int main(){
    lint q;std::cin>>q;
    while(q--){
        lint L=1;for(lint i=0;i<30;i++)L*=3;
        lint i0,j0,i1,j1;std::cin>>i0>>j0>>i1>>j1;
        i0--,j0--,i1--,j1--;
        for(;i0/L==i1/L&&j0/L==j1/L;L/=3);
        if(j0/L==j1/L)std::swap(i0,j0),std::swap(i1,j1);
        lint d=0;
        for(;L;L/=3){
            lint I0=i0/L,I1=i1/L,J0=j0/L,J1=j1/L;
            if(I0!=I1)break;
            if(I0%3==1&&1<std::abs(J0-J1)){
                lint r0=i0%L,r1=i1%L;
                d=std::min({r0+1,r1+1,L-r0,L-r1});
                break;
            }
        }
        std::cout<<std::abs(i0-i1)+std::abs(j0-j1)+2*d<<'\n';
    }
}