ABCでは久々の更新。まぁ勝ててないので今すごい顔をしながら(?)これを書いているのですが、一方で各種RatedコンテストにはほとんどでているとはいえABCに対する精進は暫く全くしていなかったので負けは必然といえばそうかも。ここ2ヶ月で-100ほどしてるので、そろそろ勝ちたいですね。

A - ABC400 Party

よく見るととんでもないストーリーをしていてとても笑っています¹。$A$を$B$で割ったあまりが0なら割ったものが答えで、そうでないなら-1です。提出

void solve() {
    int a;cin>>a;
    cout << ((400%a==0)?400/a:-1) << '
';
}

B - Sum of Geometric Series

言われたとおりに計算をしていって、1e9を超えたら打ち切ってあげればよいです。計算量は$T$を上界(ここでは$T=10^9$)として$O(\log T)$になります。32bit整数だとオーバーフローが怖いのでlong longで。提出

void solve() {
    ll n, m;cin>>n>>m;
    ll x = 0;
    ll cur = 1;
    rep(i,m+1){
        x += cur;
        cur *= n;
        if(x>1000000000ll) break;
    }
    if((x>1000000000ll)){
        cout << "inf
";
    }else{
        cout << x << '
';
    }
}

ところで、一時期#define long longしていた程度には「別に全部64bit整数でいいだろ、競プロの文脈なら困らないし」という派閥なんですが、最近「ピッタリのbitでやるべきだろ」という意見を散見して驚きです。そういった人々が正の数しか取り得ないものに対してunsigned intを使っているのか気になります、どうせ使っていないと思いますが。

C - 2^a b^2(upsolve)

分かりません。あの？ コンテスト中は「$2^a$を固定したい気持ちにはなって、そしたら上界は二分探索できるんだけど重複が辛いですね...」と言っていました。コンテスト戦略的にCに行くよりEに行くべきではあるので、そちらに粘着していたためこれ以上の進捗はなく。

結論としては$a$を固定したうえで条件を満たす奇数$b$を数え上げるんですね。確かに言われてみればという感じで、$b=2^xk$ ($k$は奇数)として表せる場合は、$a=x$のときに数えてあげれば良いからですね。

ということでオーバーフローに注意しながら128bit整数で投げると通すことができます。提出

void solve() {
    ll n; cin >> n;
    ll ans = 0;
    __int128_t cur = 2;
    while(cur <= n){
        __int128_t ok = 1;
        __int128_t ng = 1e9+1;
        while(ng-ok>1){
            __int128_t mid = (ok+ng)/2;
            if(cur*mid*mid<=n)ok = mid;
            else ng = mid;
        }
        ans += (ok+1)/2;
        cur *= 2;
    }
    cout << ans << '
';
}

D - Takahashi the Wall Breaker

とりあえず、移動先が道のときはコスト0で移動できます。壁に向かって移動するときはコスト1、としたいですが前蹴りの操作が2個破壊するので厄介です。 そこで、壁に向かって移動したときにそのもう1マス先もコスト1で移動できる、というように見てあげると一般的な最短経路問題に落ちるので、この問題を解くことができます。 ありうるコストが0か1なので想定は01BFSだろうなーと思いつつ、C++の$\log$であれば許容されるだろうという考えでダイクストラ法を実装しました。が、いつも思いますが凝ったことをしたいときの優先度付きキューが面倒くさいがち²なので、実は01BFSのほうがよかったかも。提出

void solve() {
    int h, w; cin >> h >> w;
    vector<string> s(h);
    rep(i, h) cin >> s[i];
    int si, sj; cin >> si >> sj;
    si--; sj--;
    int gi, gj; cin >> gi >> gj;
    gi--; gj--;
    vector<vector<ll>> seen(h, vector<ll>(w, inf));
    priority_queue<pair<ll, pair<ll, ll>>, vector<pair<ll, pair<ll, ll>>>, greater<pair<ll, pair<ll, ll>>>> pq;
    pq.push({0, {-1, si*w+sj}});

    while(!pq.empty()){
        auto [d, p] = pq.top(); pq.pop();
        auto [r, v] = p;
        int i = v/w, j = v%w;
        if(seen[i][j] <= d) continue;
        seen[i][j] = d;

        rep(k, 4){
            int ni = i + dx[k], nj = j + dy[k];
            if(ni < 0 || ni >= h || nj < 0 || nj >= w) continue;
            if(s[ni][nj] == '.') {
                if(seen[ni][nj] == inf) {
                    pq.push({d, {-1, ni*w+nj}});
                }
            } else {
                if(seen[ni][nj] == inf) {
                    pq.push({d+1, {k, ni*w+nj}});
                    int nni = ni + dx[k], nnj = nj + dy[k];
                    if(nni >= 0 && nni < h && nnj >= 0 && nnj < w) {
                        pq.push({d+1, {-1, nni*w+nnj}});
                    }
                }
            }
        }
    }

    cout << seen[gi][gj] << '
';
}

ところで、入力例の魚屋がどのようにして収益を上げてきたのかが気になります。高橋くんのおかげで来客が見込めそうですが、今までは誰も到達できなかったわけですし。

E - Ringo's Favorite Numbers 3

自力ACですがコンテスト中には間に合わず。

400 numberは、素数$p$, $q$及び正整数³$a, b$を用いて$p^{2a}q^{2b} = (p^{a}q^{b})^2$と書くことができます。制約から$(p^{a}q^{b})^2 \leq 10^{12}$、すなわち$p^{a}q^{b} \leq 10^{6}$であることが示せます。よって、このような値は十分高速に列挙することが可能です。

事前にこれらの値を列挙しておくことで、列挙した値の個数を$M$としてクエリあたり$O(\log M)$時間で求めることができます。よって、全体で$O(M+Q\log M)$時間で求めることができました。提出

vll create(ll n) {
    vll primes = Eratosthenes(n);
    vll res;

    rep(i, primes.size()) {
        rep2(j,i+1, primes.size()) {
            ll cur = primes[i] * primes[j];
            if(cur > n) break;

            rep(_, 1000000) {
                ll x = cur;
                rep(__, 10000000) {
                    res.push_back(x);
                    x *= primes[j];
                    if(x>n)break;
                }
                cur *= primes[i];
                if(cur > n) break;
            }
        }
    }
    return res;
}

vector<ll> primes_sq = create(1000000+1);
void solve() {
    ll a; cin >> a;
    ll ans = 0;

    // a以下で最大のtarg
    ll ok = 0, ng = primes_sq.size();
    while(ng-ok > 1) {
        ll mid = (ok+ng)/2;
        if(primes_sq[mid] * primes_sq[mid] <= a) ok = mid;
        else ng = mid;
    }
    cout << primes_sq[ok]*primes_sq[ok] << '
';
}

int main() {
    sort(all(primes_sq));
    cin.tie(0);
    ios::sync_with_stdio(false);
    int t=1;
    cin >> t;
    while(t--)solve();
}