Panasonic Programming Contest 2020

I have played a few games with Atcoder recently, and I still need to make up for it in the past few days. It’s been a long time since I last updated the solution.

Almost all Atcoder questions can be classified as [thinking questions]. The data structure is not complicated within the scope of my knowledge, but you just can’t figure it out.

I have really forgotten my original intention of writing this blog. I wrote every article so seriously at the beginning, and look at it now.

This round is mainly about questions E and F, and questions A to D are relatively weak.

Title link

E - Three Substrings

Three strings are substrings of one string. Random combination, the original string length is required to be minimum.

This question cannot be greedy by any enumeration combination. During the competition, I had already discovered that I couldn’t be greedy. However. . . I actually asked for all kinds of special conditions, but no matter what I did, I couldn’t get it right. . . Really retarded. . .

Directly enumerate ab, ac, bc offsets, and then combine them uniformly.

 
int ab[maxn], ac[maxn], bc[maxn];
 
string aa, bb, cc;
 
void solve() {
    cin >> aa >> bb >> cc;
    int mid = 1e5;
 
    REP(i,0,aa.length()) {
        REP(j,0,bb.length()) {
            if(!(aa[i] == bb[j] || aa[i] == '?' || bb[j] == '?')) {
                ab[i - j + mid] = 1;
            }
        }
   }
 
   REP(i,0,aa.length()) {
        REP(j,0,cc.length()) {
            if(!(aa[i] == cc[j] || aa[i] == '?' || cc[j] == '?')) {
                ac[i - j + mid] = 1;
            }
        }
   }
 
   REP(i,0,bb.length()) {
        REP(j,0,cc.length()) {
            if(!(bb[i] == cc[j] || bb[i] == '?' || cc[j] == '?')) {
                bc[i - j + mid] = 1;
            }
        }
   }
 
   int ans = aa.length() + bb.length() + cc.length();
   REPP(i,-4000, 4000) {
    REPP(j, -4000, 4000) {
        if(!ab[i + mid] && !ac[j + mid] && !bc[j - i + mid]) {
            int minn = min({0, i, j});
            int maxx = max({(int)aa.length(), (int)bb.length() + i, (int)cc.length() + j});
            ans = min(ans, maxx - minn );
        }
    }
   }
   cout<<ans<<endl;
 
}

F - Fractal Shortest Path

The meaning of question F is a large picture of $3^m * 3^m$, with the block situation in the middle. Then give you two points and find the distance.

What a concise question! But why can’t I figure it out?

Recursive, if found not in the same layer, direct Manhattan distance.

On the same floor, if it is the middle floor, consider whether to go above or below.

Otherwise, just recurse further.

ll wid[maxn];
ll dfs(ll x1, ll y1, ll x2, ll y2, int level) {
    if (level == 0) {
        return abs(y1 - y2);
    }
    ll w = wid[level-1];
    if(x1 / w != x2 / w) {
        return abs(x1 - x2) + abs(y1 - y2);
    }
    if(x1 / w == 1 && abs(y1 / w - y2 /w) >= 2) {
        return abs( y1 - y2 )  + min(x1 % w + 1 + x2 % w + 1, w - x1%w + w - x2%w);
    }
    return dfs(x1 % w, y1, x2 % w, y2, level-1);
}
 
int q;
void solve() {
    wid[0] = 1;
    REPP(i,1,30) {
        wid[i] = wid[i-1] * 3;
     }
    SA(q);
    REPP(i,1,q) {
        ll a1,b1,c1,d1;
        SLLA(a1);
        SLLA(b1);
        SLLA(c1);
        SLLA(d1);
        a1--;
        b1--;
        c1--;
        d1--;
        if(abs(a1 - c1) > abs(b1 - d1)) {
            swap(b1, a1);
            swap(c1, d1);
        }

        cout<< dfs(a1, b1, c1, d1, 30) <<endl;
    }
}