予鈴

アウトプットとメモ書きの中間みたいな記事がたくさん出ます。

ABC311 反省会

全体的な反省

  • 考えていた解法はサンプルできちんと試そう

A,B問題

  • 今回は特になし。あっさり解けたと思う。

C問題

  • 閉路検出の問題。Cに配置されていることを考えると再帰無しでも解けそうだが、あんまり書いたこと再帰で解いた。
  • サイクルの部分だけ出力する必要があるので、適当に工夫した。提出

D問題

  • 各盤面についてどの方向で移動しているかという情報を記録できるので、幅優先探索すれば良い。提出

E問題

コンテスト中に頑張ったが解けなかった。

考えていたこと

各マスからどの程度伸ばせるかということが判別することができれば、解ける。
ただし、 3000 * 3000 * 伸ばせる数 程度の計算量になるので、前計算か高速に答える必要がある。
コンテスト中の方針としては、前計算として、各マスから最も近い穴の座標 (x,y)を、それぞれ独立に累積minで記録して、各マスごとにどこまで伸ばせるかを計算しようとした。が、うまくいかなった。提出
なぜだめだったのかを反省も込めて書いてみる。


コンテスト中の方針は、あるマス (i,j)から、最も近い穴の座標 mx,myを記録しておき、それをもとに計算するというものだった。
(モチベーションは,、正方形 i + t, j + t を考えるときに、最初に当たりそうな穴の座標を mx, myでそれぞれ記録したいという感じ。)
ここで、マス (1,1)のときに、座標 (3,1) (1,3)にそれぞれ穴があるものとする。この時、 (2,2)は右下隅とする正方形は答えの候補となりえるが、 mx, my (1,1)となってしまい答えを導出できない。
 mx, myがそれぞれの軸についての上限となってくれることを期待したが、最小値同士だと情報が足りない。 例えば、 (2,1) (1,2)に穴があっても (1,1)となり、情報が消える。
それぞれの情報をマスの座標を保存すれば解ける気もするが、計算パートが大変そう。
いずれせよ、記録しておく値だけで情報が不足する/答えの導出に足りないという部分には気づくべきだった。


解法

結局累積和と二分探索で解いた。こっちのほうが解法が明確がわかりやすいかも...
コンテスト中にひらめきたい解法だった。

#include <bits/stdc++.h>

using namespace std;
using Int = long long;

template<class F,class T>
auto  maximize(T imin,T imax,F &f){
    while(imax - imin > 1){
        T mid = imin + (imax - imin)/2;
        if(f(mid)) imin = mid;
        else imax = mid;
    }
    return imin;
}

template <class T>
class Cumulative2DSum {
    // query[sx,gx),[sy,gy)
public:
    vector<vector<T>>sum;
    T e;
    Cumulative2DSum(vector<vector<T>>&v,T e) {
        // W is x, H is y
        int W = v.front().size();
        int H = v.size();
        ++H , ++W;
        sum = vector<vector<T>>(H,vector<T>(W,e));
        
        for(int i = 0; i < v.size(); ++i){
            for(int j = 0; j < v[i].size(); ++j){
                sum[i + 1][j + 1] +=  v[i][j];
            }
        }
        for(int i = 1; i < sum.size(); ++i){
            for(int j = 1; j < sum[i].size();++j){
                sum[i][j] += sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1];
            }
        }
    }
    T query(int sx,int sy,int gx,int gy){
        return sum[gy][gx] - sum[sy][gx] - sum[gy][sx] + sum[sy][sx];
    }
};

int main(){
    std::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int H, W, N;
    cin >> H >> W >> N;
    map<pair<int,int>,int>pos;

    vector<vector<Int>>h(H, vector<Int>(W,0));
    for(int i = 0; i < N; ++i){
        int y,x;
        cin >> y >> x; --y; --x;
        h[y][x]++;;
    }
    
    auto csum = Cumulative2DSum<Int>(h, 0LL);
    
    int cx = 0, cy = 0;
    auto f = [&](int mid) {
        if(cx + mid  >= W or cy + mid  >= H) return false;
        return csum.query(cx,cy,cx + mid + 1,cy + mid + 1) == 0;
    };
    
    Int ans = H * W - N;
    for(int y = 0; y < H; ++y){
        for(int x = 0; x < W; ++x){
            if(h[y][x]++) continue;
            cx = x; cy = y;
            Int remu =  maximize(0, 3001,f);
            ans += remu;
        }
    }
    cout << ans << endl;
}

E- NAND repeatedly

問題

 \sum_{i=1}^{N} \sum_{j=i}^{N} f(i, j)を求めよ。
ただし、 f(i, j) = \begin{cases} 
A_i & \text{if } i = j \\
\neg ( A_i \land f(i,j - 1)) & \text{if } i < j 
\end{cases} である

考えてたこと

・二重和なので、一度全体の和を求めて、いい感じに調整して N回計算するのだろうなという予測を立てる
・否定論理積の性質から、 f(i, j)の値は0または1のどちらかである。
・ここで、 f(i,j), \text{if } i < j は、先程の式から一つ前の値と i文字の値で決まる。つまり、 i文字目は直前の値の種類だけ状態数がある。
・一つ前の値が pbitとしたときの、iからN番目までの累積和を計算して、この2つで累積和の値をメモ化しておく。
・あとは一つ目の和をループして終わり。

#include <bits/stdc++.h>

using namespace std;
using Int = long long;
int N;
string s;

Int rec(int idx, int pbit,vector<vector<Int>>&memo, vector<vector<bool>>&used, vector<int>&A){
    if(used[idx][pbit]){
        return memo[idx][pbit];
    }
    used[idx][pbit] = true;
    return memo[idx][pbit] = (idx + 1 < N ? rec(idx + 1,!(pbit && A[idx]),memo,used,A) : 0) + !(pbit && A[idx]);
}

int main(){
    std::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> N; cin >> s;
    vector<int>A;
    for(auto c : s) A.push_back(c - '0');
    vector<vector<Int>>memo(N,vector<Int>(2,0LL));
    vector<vector<bool>>used(N, vector<bool>(2,false));
    
    Int ans = 0;
    for(int i = 0; i < N; ++i){
        ans += A[i] + (i + 1 < N ? rec(i + 1,A[i],memo,used,A) : 0);
    }
    cout << ans << endl;
    
}

感想

解放までは5分だったけど、累積和の書き方でこじらせた。

ABC310 反省会

はじめに

私生活があまりに忙しくなりましたが、なんとか生きてます。
最近またABCに出始めたのですが、ボコボコにされているのでクイック反省会をブログでやりたいと思います

全体的な反省

  • 問題文をちゃんと読もう
  • Cぐらいまで速解き失敗するとゴタゴタになるのやめたい

A, B問題

  • B問題で一生誤読していて辛かった。上方互換というより、価格が安いが同じ機能があるものみたいな言い回しにしてほしかったな
  • ちゃんと読めてない自分が悪いが...

C問題

  • 重複している棒の数の問題を解いていて、一生あわなかった

D問題

  • どうみても全探索しか思いつかなったので、計算量がかなり不安だが全探索の方針を考えた。
  • 実装してみるが合わない。最初の実装はこんな感じ
void dfs(int p, int t){
   // 空のチームがあったらNG
    if(p == N - 1){
        bool ok = true;
        for(auto& v : team)
            if(v.empty())
                ok = false;
        if(ok)
            ++ans;
        return;
    }
    for(int nt = 0; nt < T; ++nt){
        // 追加予定のチームを舐めて、組み合わせが悪いペアがなければ追加する
        bool ok = true;
        for(auto u : team[nt]){
            if(e.find(minmax(p + 1, u))!= e.end())
                ok = false;
        }
        if(ok){
            team[nt].push_back(p + 1);
            dfs(p + 1,nt);
            team[nt].pop_back();
        }
    }
    return;
}

どうやらチーム数の区別がうまくいってないらしい。
具体的には、 T_1: \{0,1\}, T_2: \{2,3\} T_1: \{2,3\}, T_2: \{0,1\}を重複して数え上げているらしい。
順序性を導入すると重複なしで数え上げることができそうだが、コンテスト中は思いつかず...

解説

一番大事な部分を引用するとこうなる

ここに i番目の選手を追加するには、たかだか  Tチームのいずれかに  i 番目の選手を入れるか、(チーム数が Tより少ないとき)新しく i番目の選手しかいないチームを作るかのどちらかです。

自分がやりたいことを正しくやろうとすると上のような感じになるらしい。
具体的に考えてみよう。人 iに対しての操作を考える。全てのチームに対して追加可能かどうか判定するのは、重複して計算してしまうので無駄になる。

すでに人が存在するチームに追加するかどうかは、全て試す。 iを新しいチームに追加する場合は、できるだけ小さい数字のチームに追加するように変更してみる。(つまり、ただ一つに定まる)

ACしたコード

void dfs(int p, int t){
    if(p == N - 1){
        ans += (team.back().empty() ? 0 : 1);
        return;
    }
    for(int nt = 0; nt < T; ++nt){
        bool ok = true;
        for(auto u : team[nt]){
            if(e.find(minmax(p + 1, u))!= e.end())
                ok = false;
        }
        if(ok && not team[nt].empty()){
            team[nt].push_back(p + 1);
            dfs(p + 1,nt);
            team[nt].pop_back();
        }
    }
    // 新しくチームに追加する
    for(int nt = 0; nt < team.size(); ++nt){
        if(team[nt].empty()){
            team[nt].push_back(p + 1);
            dfs(p + 1,nt);
            team[nt].pop_back();
            // break immediately
            break;
        }
    }
    return;
}

と修正したらACした。
たったこれだけでteamを区別無くカウントできるのはすごい。思いつけなかったので完全敗北です。

E問題

なんかDより解かれているイメージ有るので、後日解きます。
解きました。

E - Safety Journey

2023年苦手なジャンルを克服しよう数え上げ編です。

問題

 N頂点の完全グラフが与えられる。このうち、 M本の辺は使えない。
 K + 1個のパスのうち、始点と終点が1で終わるパスの数を答えよ。

atcoder.jp

解法/ 考えてたこと

解説ACしたが思いつけそうな問題だった。反省。

  • 総当りは当然不可能なので、 k番目のときに頂点 vにいるときの総数を管理する方針を考えた。ただし、これは更新が O(N^2K)かかる。具体的には、  k番目の vに対して N個の更新を考える必要があり、できない。
  • ならば余事象で攻めるか?となるが、できない。使えない辺を使っているパスを重複なく列挙するのは難しい。これを実装するまで気づかなかったのが本当に良くない。
  • 最初の方針で攻めるしかないかなとなりつつ、計算量を減らせない。おそらく更新をサボるんだろうなぁ(つまり、使わない辺だけを使って更新するんだろうなぁ)と考えていたが、思いつけなかった。
  • ここから解法。3番目の方針で解ける。 dpテーブルは以下の通り

 dp[i][j] := i 番目のパスのときに頂点 jにいるときの総数 で解ける。

更新は、使わない辺だけを使うのではなく、すべての辺を使った結果から、使わない辺を使っている結果を引く で更新すれば良い。イメージ的には累積和みたいな感じ。

 dp[i][j] := \sum\limits_{v \in V} dp[i - 1] [v]  - \sum\limits_{u \in edge[j]} dp[i - 1] [u]

うーん確かに。式にしてみればあっさりしている。列挙となった時かなり頭が固くなっている気がするので、慣れていきたいところ。

提出したコード

特に理由は無いけどGoで書きました

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var sc = bufio.NewScanner(os.Stdin)

func nextInt() int {
	sc.Scan()
	i, e := strconv.Atoi((sc.Text()))
	if e != nil {
		panic(e)
	}
	return int(i)
}

func main() {
	sc.Split(bufio.ScanWords)

	N, M, K := nextInt(), nextInt(), nextInt()

	edge := make([][]int, N)
	dp := make([][]int64, K+1)
	mod := int64(998244353)

	for i := range dp {
		dp[i] = make([]int64, N)
	}

	for i := 0; i < M; i += 1 {
		u, v := nextInt()-1, nextInt()-1
		edge[u] = append(edge[u], v)
		edge[v] = append(edge[v], u)
	}
	dp[0][0] = 1
	prev := int64(1)
	for i := range dp {

		if i == 0 {
			continue
		}

		for j := range dp[i] {
			tmp := prev

			tmp -= dp[i-1][j]
			tmp += mod
			tmp %= mod

			for k := range edge[j] {
				nxt := edge[j][k]
				tmp -= dp[i-1][nxt]
				tmp += mod
				tmp %= mod
			}
			dp[i][j] = tmp
		}

		tmp := int64(0)
		for j := range dp[i] {
			tmp += dp[i][j]
			tmp %= mod
		}
		prev = tmp
	}
	fmt.Println(dp[K][0])
}

E - Throwing the Die

2023年苦手ジャンルがんばって埋めようシリーズ期待値編です。

問題

atcoder.jp

考えてたこと

サンプル2を導出するのに時間がかかって困った。ゲームも組み合わさってる用に見えてかなり時間がかかってしまった。
まず N = 1は容易に導出することができる。次の N = 2の期待値の求め方がしっくりこなかった。
・最初は出目によって場合分けしてたので、二ターン目以降も出目によって場合わけする?
・各ターンで前のターンの出目より大きい場合だけ列挙する?
・ターン毎に独立ならなんターン目でも 1/6* 出目になる?
・最初の出た目に書かわず次の期待値 21/36だけどあってるのか?
などなど
最初は出目によって場合分けして、その後の期待値は全部同じじゃん、そんなことある?みたいな気持ちなってた。

解法

だいぶ迷走してしまったが、問題を解くために必要を知識を整理しよう

  • ゲームを続行するか終了するかを選択できる
  • ゲームを終了する場合は、最後の出目だけがスコアに関係する。途中までのスコアは関係ない
  • これをふまえるとスコアの期待値が最大になるように行動するとは、次の試行で今の期待値を超えそうなら続ければ良い。
  • スコアの期待値自体は試行回数をNとすると21/6^Nになる。
  • スコアが変わらないのに期待値だけ下がり続けるのが直感に反していて答えにたどり着けなかった。論理的に攻めよう
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int N; cin >> N;
    double ans = 3.5;
    
    for(int i = 1; i < N; ++i)
    {
        double tmp{};
        for(int j = 1; j <= 6; ++j)
        {
            tmp += max(static_cast<double>(j), ans);
        }
        tmp /= 6;
        ans = max(ans, tmp);
    }
    
    cout << setprecision(10) << fixed << ans << endl;
}

E - Swap Places

問題

 N頂点 M辺の単純無向グラフが与えられる。頂点1から頂点 Nに、頂点 Nから 1にそれぞれコマを移動する時の最短ステップ数を答えよ。

atcoder.jp

解法

すんなりと解けた。一回の動作で2つの頂点が移動するという点が厄介かもしれないが、拡張グラフ上でのDijkstraの気持ちになれば見通しが良くなる。
Dijkstra法のキモは、ある状態の最短経路(文脈によっては当然最短経路ではない場合もあるけど)を順次確定させていくことで、効率よく全体の最短経路を求める点である。この問題での状態とは2つのコマの位置、すなわち、 d[u][v]である。

#include <bits/stdc++.h>
using namespace std;

void solve()
{
    int N,M;
    cin >> N >> M;
    
    vector<int>C(N);
    vector<vector<int>>edge(N);
    
    for(auto& c : C)
        cin >> c;
    for(int i = 0; i < M; ++i)
    {
        int u,v; cin >> u >> v;
        --u; --v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    
    constexpr int inf = 1e9;
    vector<vector<int>>d(N,vector<int>(N,inf));
    d[0][N - 1] = 0;
    
    using p = pair<int, pair<int,int>>;
    priority_queue<p,vector<p>, greater<>>q;
    
    q.emplace(d[0][N-1],make_pair(0,N -1));
    while(not q.empty())
    {
        int cd = q.top().first;
        const auto [u,v] = q.top().second;
        q.pop();
        
        if (cd > d[u][v])
            continue;
        
        for(auto nv : edge[v])
        {
            for(auto nu : edge[u])
            {
                if(nu == nv or C[nv] == C[nu])
                    continue;
                int nxt = cd + 1;
                if(d[nu][nv] > nxt)
                    d[nu][nv] = nxt, q.emplace(d[nu][nv], make_pair(nu,nv));
            }
        }
    }
    cout << (d[N - 1][0] == inf ? -1 : d[N - 1][0]) << endl;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T; cin >> T;
    while(T --> 0)
        solve();
}


E - Colorful Blocks

2023年は数え上げとか期待値とか苦手分野をやっていきます。

問題

以下の条件を満たしながら N個のブロックを M個の色での塗り方が何通り有るか求めよ。

  • 隣り合うブロックの組であって同じ色で塗られている組は、  K 組以下である。

atcoder.jp

解法

条件の部分を言い換えると、隣接している」かつ「同色」を満たすブロックの組は K 組以下であると言い換えると良いらしい。
日本語が読めないので競プロサークルに助けを求めたら言い換えてくれました。Gくんありがとう。

さて、条件の部分から考察を考える。一度に K組以下という条件を扱うのは厄介そうなので、何組使うかを決め打ちして考えることにしよう。(制約的にも間に合う,  K \leq 10^5)
重要な考察として、 N個のブロックの中で、「隣接するブロックの組」は  N - 1個存在する。したがって、同じ色で塗られている組 k組のとき、 N - 1個の「隣接するブロックの組」から k個を選べば良い。

色の塗り方は、隣接する色と違う色で塗らなければならない。これは、最初だけ M色選べて、それ以降は M - 1色から選べるというふうに考えればよい。

提出コード

#include <bits/stdc++.h>

using namespace std;

using Int  = long long;
constexpr Int mod = 998244353;

template <class T> T modpow(T a, T b) {
    if (b == 0) return T(1);
    if (b % 2 == 0) {
        long long d = modpow(a, b / T(2));
        return (d * d) % mod;
    } else {
        return (a * modpow(a, b - 1) % mod );
    }
}

template <class T>
class ModComb {
public:
    T maxn,mod;
    vector<T>fac,finv,inv;
    ModComb(T maxn_,T mod_) : maxn(maxn_),mod(mod_),fac(maxn_),finv(maxn_),inv(maxn_){
        fac[0] = fac[1] = 1;
        finv[0] = finv[1] = 1;
        inv[1] = 1;
        for (T i = T(2); i < maxn; i++){
            fac[i] = fac[i - 1] * i % mod;
            inv[i] = mod - inv[mod % i] * (mod / i) % mod;
            finv[i] = finv[i - 1] * inv[i] % mod;
        }
    };
    
    T computeComb(T n,T k){
        if (n < k) return T(0);
        if (n < 0 || k < 0) return T(0);
        return fac[n] * (finv[k] * finv[n - k] % mod) % mod;
    }
    
};

int main()
{
    Int N, M, K;
    cin >> N >> M >> K;
    
    Int ans = modpow(M - 1, N - 1);
    ans *= M; ans %= mod;
    
    auto Comb = ModComb<Int>(1000000LL,mod);
    
    for(Int k = 1; k <= K; ++k)
    {
        Int res = Comb.computeComb(N - 1,k);
        Int a = modpow(M - 1, N - 1 - k);
        a *= M;
        a %= mod;
        a *= res;
        a %= mod;
        ans += a; ans %= mod;
    }
    cout << ans << endl;
}