文学徒が競プロをするブログ

競技プログラミングの精進を記録していきます

ABC191 復習

出れなかったんだけど出なくて正解だった気がするな。C問題の問題文が最後まで意味不明だったんだけど、あれで良いとなったのはマジで謎。

あの問題文で速攻通してる人も謎。

A問題 Vanishing Pitch

丁寧に式を書きました。

B問題 Remove It

for文とif文を書きます。append系の操作が出来るデータ構造を使うと良いですね。

C問題 Digital Graffiti

問題の問題。この問題文で速攻通してる人マジで何？エスパー能力が高すぎる。あとサンプルが一個だけなのも謎ポイント。普通に意味が分からなくて困った。ドット絵かと思うだろ。

ちなみに問題を理解してもそこそこ難しいです。問題文抜きでも茶色diff以上はあるんじゃないかな。ハマるとかなり焦るタイプの問題だと思います。

#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define rep(i,n) for(int i=0;i<(n);++i)
#define REPR(i,n) for(int i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
typedef pair<ll, ll> P;

template<typename T>
void print(const vector<T> &x) {
    int n = x.size();
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x) {
    int n = x.size();
    rep(i,n) {
        rep(j,x[i].size()) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

template<typename T>
void print(const vector<T> &x, int n) {
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x, int n, int m) {
    rep(i,n) {
        rep(j,m) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

void input_init() {
    cin.tie(0); ios::sync_with_stdio(false);
}

int main(int argc, char const *argv[]) {
    int h,w; cin>>h>>w;
    vector<string> s(h);
    rep(i,h) cin>>s[i];
    int ans = 0;

    for (int i = 1; i < h-1; ++i) {
        for (int j = 1; j < w-1; ++j) {
            if (s[i][j] == '.') continue;
            int cnt = 0;
            if (s[i+1][j] == '.' && s[i][j-1] == '.') cnt++;
            if (s[i+1][j] == '.' && s[i][j+1] == '.') cnt++;
            if (s[i-1][j] == '.' && s[i][j-1] == '.') cnt++;
            if (s[i-1][j] == '.' && s[i][j+1] == '.') cnt++;
            ans += cnt;
        }
    }

    for (int i = 1; i < h-1; ++i) {
        for (int j = 1; j < w-1; ++j) {
            if (s[i][j] == '#') continue;
            int cnt = 0;
            if (s[i+1][j] == '#' && s[i][j-1] == '#') cnt++;
            if (s[i+1][j] == '#' && s[i][j+1] == '#') cnt++;
            if (s[i-1][j] == '#' && s[i][j-1] == '#') cnt++;
            if (s[i-1][j] == '#' && s[i][j+1] == '#') cnt++;
            ans += cnt;
        }
    }


    cout << ans << '\n';

    return 0;
}

自分は上のようなコードで解きました。

D問題 Circle Lattice Points

問題文を見る -> 「円 格子点の数」でググる -> 勝ちを確信して実装 -> 誤差死

多分上の一連を3000人くらいの人がやってそう。

何がアレってpythonで書き直してもそのままじゃ通らないんだよね。pythonは無条件で無限精度だと思っていたのでびっくりしました(カス)。

情報系の教育を受けていないので、倍精度浮動小数点数の誤差は15桁くらいというのを知らなかったのは痛かったです。

整数に直して考える時も、roundでepsを丸めてやるというテクを知らなかったのでバグり散らかしました。小手先テクとして覚えておきます。あとpythonのDecimalね。

E問題 Come Back Quickly

貴重な癒し枠。こいつがいなかったら心が折れていたと思います。ありがとう......。

各頂点について、1本以上の道を通ったあと元の頂点に戻ってくる最短経路を求めろという問題。
まず明らかに、「自分のところに来る辺が存在しない頂点」には、出ていったあと返ってこれないので考えなくていい。

あとは各頂点からダイクストラして、その頂点に帰る辺でつながっている頂点への最短距離を求めてあげて、総距離が一番短いものを選んであげると通ります。

間に合うか若干不安でしたが、他にやりようもなく、辺の数も少ないのでエイっと投げると通りました。信じる心。

F問題

初手の考察を微妙に間違えて、あとワンステップのところまでたどり着けませんでした......。

まずこういった、操作によって状態を変化させていく数え上げ系の問題は、最後に残る数の上界と下界を考えるのが定石だと思います。

まず下界ですが、最後に残る数の最小値は全ての要素のGCDです。
何故かというと、 gcd(x, y) \leq min(x, y)だからです。 X = Yのとき gcd(x, y) = min(x, y)となり、それ以外のときは必ず二値のgcd < 二値のminとなります。

次に上界ですが、これは与えられる数列の最小値です。gcdを取ると必ずmin以下の数になるため、全ての操作でminを取った結果残る数が明らかに最大です。

ここまで五分かそこら程度でわりとすんなり出来たのは良かったなと思います。数式で考えず直感で考えてしまったのは反省ですが。

ここから「GCDとしてあり得る数を全て求めて、上界より小さいかどうかチェックする」ところまで行ければ考察としては完璧だったのですが、
何故かここで「二乗だし各ペアでGCD取ってグループ分けとかすればいいんじゃね」みたいなとんちんかんなことを考え始めてしまいました。

そして各ペアのGCDを列挙して上界より小さい値であればインクリメントするというアルゴリズムを提出し、無事WA......。どうしてそこでそうなっちゃうかな。

敗因は「考察すべき点をしっかり詰めて、迷いのない状態で進めていかないと脳がバグる」という事実を軽視していたことでしょう。

「GCDとしてあり得る全ての数のうち、上界より小さいものは全て残すことが出来る」「だからGCDとしてあり得る数を全て求めて、上界より小さいかどうかチェックすればいい」という方針を確信を持って言語化出来ていればこんなことにはならなかったはずです。

反省しながらこの主張が正しいことを証明してみます。

Z = gcd(a, b, c, d, ...), M = min_{i=1}^{N} Aとします。

M \lt Z のとき

gcd(Z, M) \leq min(Z, M) \lt Z

となるので、絶対に最後まで残すことが出来ません。

逆に M \geq Z のとき、

Z = min(Z, M) となるので、必ず残すことが出来ます。

頭の中でごちゃごちゃ考えていると
Z = gcd(a, b, c), S = gcd(s, t, u)として、 S \lt Z \leq M の場合、 Zは上界 Mより小さいにも関わらず残すことが出来ないように一瞬思えます。

しかしこれは支離滅裂な例です。
Zと Sは独立している( Sを作っておかなければ Zを作れないというような依存関係はない)ので、普通に Sを作らなければ Zをそのまま残すことが出来ます。

以上より、「GCDとしてあり得る全ての数のうち、上界より小さいものは全て残すことが出来る」ことがわかりました。
場合分けすると脳がバグらないな。ノーベル賞級の発見だと思います。複雑な問題を漏れなく単純な問題に場合分けして、それらを個別で解くと頭をバグらせずに元の複雑な問題を解いたことになるんですよね。魔法。

さて続きですが、「GCDとしてあり得る数を全て求めて、上界より小さいかどうかチェックすればいい」ことも示されたので、GCDとしてあり得る数を高速に求められればこの問題を解くことが出来ます。

一番楽な考え方だと 2^{n}でGCDを求めればいいですが、当然これは間に合いません。部分和問題っぽいDPが何となく浮かびますが、変な形になりそうなので置いておきます

数学的に良い性質がありそうな気がするので、最大公約数の定義を見ます。「２つ以上の正の整数に共通な約数（公約数）のうち最大のもの」です。

ここで各数字の約数の個数を考えてみると、どうやってもそんなに多くならないので、各数字の約数を全て列挙して、その約数が最大公約数になり得るかどうかを一つずつ確かめれば良さそうな気がしてきます。

ある数の約数 Kが、数列 Aからいくつかの要素を選んだ集合のGCDとなるか判定することを考えます。

数列 Aの要素の内、 Kを公約数として含む全ての数(= 全ての Kの倍数)を列挙します。

[a \times K, b \times K, c \times K, d \times K ...]

そしてこの列挙した集合のGCDを実際に取ってみましょう。

もしこの列挙した集合のGCDが Kであった場合、 Kは明らかにGCDとしてあり得る数の一つです。現行犯ですね。

次にこの集合のGCDが Kではなかった場合を考えます。GCDの定義より、この集合のGCDが Kより小さくなることはありません。
よって、GCDが Kではなかった場合、GCDは必ず Kよりも大きくなります。

そのGCDを t \times Kと置きましょう。すると列挙した全ての Kの倍数は、全て t \times Kの倍数でもあることになります。

「全ての Kの倍数は、全て t \times Kの倍数でもある」
　= 「どんな取り方をしてもGCDは t \times K以上になって、絶対に Kにはならない」
ということが言えます。

そして各数字の約数を全て決め打って試すので、この t \times Kも放っておけばいずれ試されます。
つまりある数の約数 Kについて Kの倍数を全て列挙し、その集合のGCDが Kと一致すれば、 KはGCDとしてあり得る数の一つであると言えます。

これを全ての約数について試せば、GCDとしてあり得る数の全てを求めることが出来ます。

あとは、GCD判定された数が上界以下であることを確認して、setか何かに突っ込んでやれば良いです。実装は結構軽いと思います。

約数を全探索するっていう大ヒントは見てしまったけど、その後を自力で出来たのはよかったかな。

以下コードです。

#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(n);++i)
typedef long long ll;
using namespace std;

ll gcd(ll a, ll b) {
    if (a % b == 0ll) return b;
    return gcd(b, a%b);
}

ll gcd_multi(vector<ll> A) {
    ll n = A.size();
    ll G = A[0];
    for (ll i = 1; i < n; ++i) G = gcd(G, A[i]);
    return G;
}

int main(int argc, char const *argv[]) {
    ll n; cin>>n;
    vector<ll> a(n);
    rep(i,n) cin>>a[i];

    map<ll, vector<ll>> mp;

    auto div_cnt = [&](const ll m) {
        for (ll i = 1; i*i <= m; ++i) {
            if (m % i == 0ll) {
                mp[i].push_back(m);
                if (i != m/i) mp[m/i].push_back(m);
            }
        }
        return;
    };

    unordered_set<ll> st;
    ll mini = *min_element(a.begin(), a.end());
    st.insert(mini);

    for (auto &&e: a) div_cnt(e);

    for (const auto [div, arr]: mp) {
        if (gcd_multi(arr) == div) {
            if (div <= mini) st.insert(div);
        }
    }

    cout << st.size() << '\n';

    return 0;
}

ABC163E Active Infants

引っ越しで忙しかったので4日ぶりの精進。

以前解説ACしたが、全く理解をものにできていなかったので再度解いてアウトプットする。

問題概要

N人の幼児が左右一列に並んでおり、左から i番目の幼児の活発度は A_iです。

あなたは一回だけ、幼児たちを好きな順番に並び替えさせることができます。

はじめ左から x番目に並んでいた幼児が左から y番目に移動するとき、うれしさが A_x \times |x−y|だけ生じます。

幼児のうれしさの合計が最大でいくつになるか求めてください。

各要素がそれぞれ重みづけされており、それらを並べ替えると各要素について移動させた距離 × 重み だけコストがかかる。コストを最大化せよ

という問題。

解法

まず典型として、絶対値を見たら二つの式に分解してmaxを取るというものがありますね。45度回転とかでもたまに見るようなやつ。

つまり | x - y | を max(| x - y |, | y - x | )と変形してやります。

これは手間がかからないのでとりあえず機械的にやって、頭の片隅に置いておけばいいかな。

その上で問題について考えると、直感的に大きい方から優先的に動かしてあげると良さそうだなあとなります。
思考の根拠としては重みの大きい要素を長い距離動かすほどお得なわけで、重い要素から自由度を与えてあげたくなるという感じ。

では貪欲に重い要素から端っこに置いていけばいいかとなると少し話は違うような気がして、
例えば一番重い要素が真ん中にあって、僅差で二番目に重い要素が一番右端にあった場合は、恐らく二番目に重い要素を左端に持って行った方が大きくコスト増やせる気がします。
一番重い要素は右端に持っていければ最適っぽいですが......それをいちいち判断するのは難しそうです。

ただ、重い要素から、置ける範囲内で右端か左端に置いていく(両端から徐々に埋めていく)やり方で良さそうなお気持ちが生えてきます。

お気持ちベースで行動するのは怖いので、数式ベースで考えてみましょう。

並べ替えられた後の各項のindexを Pと置くと、総コスト Cは以下のように表すことが出来ます。

C = \sum_{i=0}^{n} A_i \times max( i - P_i, P_i - i )

これを場合分けすると、

if (i - P_i > 0)のとき

C = \sum_{i=0}^{n} A_i \times (i - P_i)

そうでないとき

C = \sum_{i=0}^{n} A_i \times (P_i - i)

となります。

これらの式 A_i \times (i - P_i), A_i \times (P_i - i) はどちらもただの掛け算なので、計算結果を最大化するためには、かける数とかけられる数の双方が最も大きくなくてはいけません。

Aを大きい順に処理していくとすると、

C = \sum_{i=0}^{n} A_i \times (i - P_i)

という式では P_iの小さい順に。

C = \sum_{i=0}^{n} A_i \times (P_i - i)

という式では P_iの大きい順に処理していけば良いことが分かります。

これは、置ける範囲内で右端か左端に置いていく(両端から徐々に埋めていく)というのと同等の操作なので、この方針で良いことが証明できました。

右端に置くか左端に置くかなので、よくある二択のDPをすればいいことがわかります。

dp[右に置いた数][左に置いた数] = コストの最大値

というやり方で解けます。

以下コード

#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i,n) for(ll i=0;i<(n);++i)
#define REPR(i,n) for(ll i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
typedef pair<ll, ll> P;

template<typename T>
void print(const vector<T> &x) {
    int n = x.size();
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x) {
    int n = x.size();
    rep(i,n) {
        rep(j,x[i].size()) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

template<typename T>
void print(const vector<T> &x, int n) {
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x, int n, int m) {
    rep(i,n) {
        rep(j,m) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

void input_init() {
    cin.tie(0); ios::sync_with_stdio(false);
}

int main(int argc, char const *argv[]) {
    int n; cin>>n;
    vector<P> a(n);
    rep(i,n) {
        cin>>a[i].first;
        a[i].second = i;
    }

    sort(a.begin(), a.end(), greater<>());
    vector<vector<ll>> dp(n+1, vector<ll>(n+1));

    rep(i,n) {
        rep(j,n) {
            if (i+j >= n) break;
            ll x = a[i+j].first;
            ll idx = a[i+j].second;

            // 左に置く
            ll lcost = x * (idx-i);
            chmax(dp[i+1][j], dp[i][j]+lcost);


            // 右に置く
            ll rcost = x * (n-j-1-idx);
            chmax(dp[i][j+1], dp[i][j]+rcost);
        }
    }

    ll ans = 0;
    rep(i,n) rep(j,n) if (i+j == n) chmax(ans, dp[i][j]);
    cout << ans << '\n';

    return 0;
}

得た知見・課題

  • とりあえず絶対値は数式をいじるうえで分解しておくと何かと都合がいいことが分かった。
  • お気持ち方針ではなく数式できっちり詰めることを習慣化していく。求めたい値を数式で表し、変形していきながら方針を探っていくことを意識する。

ABC190 反省と解法

ABCEの四完。Eを通したのがせめてもの救いだが本当に不甲斐ない。
1300パフォ程度は取ったが、後日自力でDFを解き直すと10分程度であっさり解けてしまった。全完するべきセットだったと強く感じる。大反省......。

全完の目がある得意セットなんて十回に一回あれば良い方だし、失敗した自分が情けない。もっと頑張ろう。

A問題 Very Very Primitive Game

どう考えてもBより難しいと思います。これなに？
とりあえずお気持ちif文を投げたら落ちたので、適当にシミュレーションして通した。こどふぉDiv2のAみがある。

B問題 Magic 3

最易。問題文に答えが書いてあるので、言われたとおりにやります。

C問題 Bowls and Dishes

びっっっっっっっっくりするくらい初見難しかった。ARC111のB問題と若干似ていたので一瞬グラフを書き始めたが、制約をよく見ると K \leq 16で全てを察した。

普通にbit全探索で全部試してAC

D問題 Staircase Sequences

解けなかったやつ。難しいよ～～～～とか言ってたが、今考察ノートを見返すと取り掛かって五分で本質の式変形まで済ませていて笑ってしまった。何でそこから20分以上悩んだ挙句に飛ばすねん。

S = 数列の和, A = 初項, N = 数列の長さとして、等差数列の和の公式を変形すると

S = \frac{1}{2} N(2A + (N-1))

2S = N(2A + (N-1))

2S = 2AN + N(N-1)

こうなる。長さを決め打つとすると初項Aについて解けばいいので

A = \frac{2S - N(N-1)}{2N}

こういう形の式になります。
この式が整数解を持てばいいので 2S - N(N-1) % 2N = 0 になるかNを決め打って確かめればいいことが分かります。ここまでは速かった。

この後、アホなので {10}^{6}くらいまで決め打てばいいかな～とか言いながら愚直にNを1から決め打とうとしたものの、当然 {10}^{12}まで決め打つ必要があるのでダメになり。

サンプルをグッと睨んで入力が12の時の数列の長さを確かめると、24の約数になっていることがわかったので高笑いしながら 2Nの約数列挙を実装 -> サンプル3が合いません......何もわからない......。になりました。

原因はオーバーフローの見落としでした。真正のアホ。

てっきり 2Nの約数だけ見ればいいわけではないのだと思ったのがこのやらかしの原因でした。

そこで 2Nの約数だけ見ればいい根拠を自戒として示しておきます。
上の変形途中の形をグッと睨むと

2S = N(2A + (N-1))

となっています。 (2A + (N-1)) = M とすると 2S = N \times Mです。よってNとMは両方とも 2Sの約数であることが分かります。決め打ちたい長さはNなので、 2Sの約数だけ見ればいいことが示せました。

本当にノートを見返して脱力してしまった。視野が極端に狭くなってしまっていたのが本質的な敗因ですね。
最近数式を用いて思考を整理し、段階的に考察することを意識しているのですが、まだそれらの行為に慣れておらず、いっぱいいっぱいになりながら頑張っているような感覚があります。数式を思考の道具とする習慣を徹底し続けていくことを肝に銘じます。

E問題 Magical Ornament

これが青diffなの、最近の初心者レベルインフレに慣れていたので逆にびっくり。絶対先週のアフィン変換より簡単だから。新規参入者は全員数強東大生なんじゃないかという僕の疑念がまた深まってしまったな......。

問題文の「魔法石 C_1,C_2, ... ,C_kをそれぞれ1個以上含む魔法石の列を作る」と制約の K \leq 17が「bitDPで解くよ～」と宣言してくれています。自己紹介ありがとう。

で、問題文を読んで考えると、隣に置ける数字がそれぞれ決まっているので、数字どうしの関係性をグラフとして考えることができ、数列 Cの数字が全て連結でなければならないことがわかります。

更にグラフとして考えるやり方を進めると、 C_1を置いた後に C_2, C_3, ... , C_kを置くのに必要な数字の個数は C_1から C_2,C_3, ... , C_kまでの最短距離であることに気づきます。

これで問題は巡回セールスマン問題に帰着され、各辺のコストもわかった状態になったので、bitDPをやっておしまいです。

この「bitDPに必要な重みをグラフの最短距離として求めておく」という考え方は ABC180-Eで既出なのですんなりと出てきました

具体的な実装は、グラフで数字の関係性を持ち、 K*(K-1)/2回BFSして重みを求めたうえでbitDPというそこそこ面倒なものでしたが、結構すんなり通せて嬉しかったですね。でも青diffではないだろ。

F問題 Shift and Inversions

不甲斐ねえ～～～～～part2.

  1. 残り25分あってなんでこれが解けなかったんですか？
  2. 誤読しました................

どう誤読したのかというと b_i = a_{i+k \bmod N}を b_i = (a_i + k) mod Nに誤読しました。

これだと区間加算更新の区間和取得が出来るデータ構造で解けるんですが、使っていたPCにACLを実行できる環境がなく、そもそも転倒数の詳しいことを忘れており(ゴミ以下のアホ)、アルメリアさんのACLの遅延セグ木の記事を見ながらAtCoderのコードテストで頑張りましたが時間切れとなりました。

ちゃんと誤読せず読むと色々やりようはあるのですが、こういう円環として回すやつは同じものを二つ繋げて並べてしまうのが好きです。

そこでBITなりセグ木なりで適当にやれば解けます。別になくても解けますが、無思考で解けるのでやっちゃいました。

総評

何回自分の愚かさを噛み締めれば気が済むんですか？

AtCoder Beginner Contest 189 反省

めちゃくちゃ不甲斐ない。Dが通せなかったのは本当にひどかった。早い段階で方針分かってたのに通せないの最悪すぎて言葉も出ません。

A問題 Slot

if文を書きます

B問題 Alcoholic

\sum_{i=1}^{k} V_i \times P_i \times \frac {1}{100} > X となる最初の添え字を求める問題。こういうのが誤差で死亡しがちなのは経験上(去年のパナソニックコンなど)知っていて、適当に式変形をするといい。

\sum_{i=1}^{k} V_i \times P_i > X \times 100 となる最初の添え字を求めればいい。

C問題 Mandarin Orange

N \leq {10}^{5}とかならDに置かれていても違和感ない問題。普通に初手困った。
良い解法がぱっと思い浮かばなかったから、セグ木貼って O({N}^{2} \log N)ワンチャンお祈りしたけどダメだった。

よく見るとTLが1.5secだったし流石に反省して速い解法考えたけど O({N}^{2})許すなら許してほしいね。

結局Minimum Sumみたいに小さい順にソートしてsetでindexを管理するやり方で解いた。聞くところによると最大長方形なるアルゴリズムで解けるんですね。初めて知りました。

D問題 Logical Expression

今回の反省の本題。まあANDとORでどう考えても数えるやり方が変わってくるからDPするしかないんですね。
敗因は何故か80分もあってこの簡単そうな遷移を詰め切れなかったこと。85分後に通せました。

え、文字にすると意味の分からなさがすごいな。このDP、バグやらで時間かけるとしても10分くらいの見た目じゃないですか？

このDPの遷移を時間通りに詰め切れないのは明らかにおかしいので、原因と対策を考えていく。

今回の件は、「サンプル等からフィーリングで何となくDPの状態の持ち方や遷移を考えていく」という論理的思考弱者ならではの思考パターンが招いた失敗だった。
この問題はたまたまサンプルが少なく、またサイズが小さかったために考慮漏れが頻発してしまった。また手で大きめのサンプルを作ろうとして時間を食ってしまった。それらがこの失敗を生んだと結論するのが妥当である。

実験が大切な問題とか、サンプル見ないと意味が分からない類の問題では確かにサンプルからエスパーしていくこともあるけど、それ以外の問題でやるべきことではない。

DPに限らず、今日を境として脱却することを誓います。

さて、改めてどうすべきかと考えると、やはり数式ベースで場合分けを考えていくという方針が良いように思う。
自分は何となくで問題が解けるほど地頭が良くないので、出来るだけ扱いやすい統一的な構造で問題を捉えていく癖をつけていかないと本当に水色に戻れなくなる。

数学的な考え方だとmaspyさんのDPに関する考え方がシンプルでかっこいいので、参考にしたいなあ。

ひとまずありがちな状態の持ち方として f(i) を y_iがTrueとなるものの個数とおく。そして場合分けを考える。

明らかな場合分けとして S_iがANDかORかを考えると

  • ANDの場合

ANDの時は y_{i-1}の値がTrueでかつ x_iもTrueの場合しか y_iでTrueになることはないので

f(i) = f(i-1)

となる

  • ORの場合

ORの時は更に場合分けをする必要がある。 x_iをTrueとした場合とFalseとした場合である。
ちなみに本番ではここで y_{i-1}がTrueの場合とFalseの場合を考えてしまい、混乱して時間をロスした(その場合分けだと y_iがTrueとなる数とFalseとなる数両方を持つ必要がある)。そもそも定義からしてそんな場合分け考えるなよ。

x_i = Trueのとき

y_{i-1} = True

でも

y_{i-1} = False

でもTrueになるので、そこまでの全ての場合の数を足しこむ。

f(i) += {2}^(i)

x_i = Falseのとき

y_{i-1} = Trueの数だけTrueに出来るので

f(i) += f(i-1)

これでおしまい。うーん。サンプルじゃなくて数式をいじる力をつけたい。

E問題

コンテスト後に問題をしっかり読んだ。
色々考えたけど、全ての点が統一的に動く設定で、多分操作が単純な計算式に圧縮されるようなタイプの問題だと思った。

操作を数式でうまいこと記述できれば上から舐めていって、出力に当たったらその数式をもとの座標に適用すればいいんじゃないですかね。

あとはそのうまいことやる数式を見つければ良くて、何か回転とか平行移動とかでググると行列式が出てきた。行列とか習ってません。おしまいです。

うーんこまっちゃうね。

これに全てが書かれているような気がするんですが、読めない。でもなんかそれっぽい。
これがEで出るってことは行列ライブラリは持っておけってことなのか。ちょっと行列勉強してきます。

解説見た。うーん、考え方はあってたなと思ったけどナイーブ解法見て爆笑した。なにこれ天才？それはそうすぎてびっくりした。ギャグっていうには実装が重そうだけど実質ギャグだろ。

Educational Codeforces Round 102(Div. 2) E Minimum Path

解説見たけど解けねえーーー！っていう気分になった。拡張ダイクストラ、もっと抽象化して理解する必要があるなあ。

拡張ダイクストラもそうだし、区間DPとかあの辺何回勉強しても深い理解が出来ていないので頑張らないといけませんね。

問題概要

Problem - E - Codeforces

普通にグラフの最短距離を考えるのは簡単だから、今まで通ってきた辺の集合を Eとして

\sum_{i=1}^{k} We_i - \max { E } + \min { E }

を最短距離の代わりに求めろという問題。

解法

どちみち最短経路なので、工夫してダイクストラをするしかないなあというお気持ちになる。試しにsumとmaxとminを持つダイクストラしてみたけどダメだった。

拡張ダイクストラの基本はよくけんちょんさんとかがDP入門の記事で言うのと同じように、「今持っている情報じゃ解けないから次元を増やす」ことだと思う。
そこでDPの次元拡張と同じような気持ちになって考えると、頂点数も辺の数も {2} \times {10}^{5} だし、重みに至っては {10}^{9} なのであまり大きく次元を増やせそうにはないことがわかる。

何か良い性質はないか数式をグッと睨む。
するとこれって結局、ダイクストラする中で一回だけコストが無料になって、一回だけコストが倍になった時の最小値を求めろという話と同値であることがわかる。難しくないか？？？言われればまあそうなんだけど。

ということは次元を三つに拡張して、dp[i][j][k] := i番目の頂点に来ていて、コストが既に倍になっているかどうか(j: bool)、コストが既に無料になっているかどうか(k: bool)とすればこの問題を解くことが出来る。

ここまで言われたらダイクストラかDPにある程度慣れている緑コーダーでも解けそうな見た目になったね。
まあ実装がtuple地獄で嫌な気持ちになるんですけど......。

拡張ダイクストラはまあみんなすぐだと思うんだけど、そこから数式の条件を言い換えるのが一番の難所。maxやminがあったらそれを手がかりに考えがちなんだけど、もう少し広く考えることを覚えた。

「こういう発想があった」ということを覚えておかないと一生式変形しちゃう気がするな。

この問題、数式が何か良い感じに式変形すると嬉しくなれそうな、微妙に意味ありげな形をしているので、それでかなり考えてしまった.....。
思考の紛れを誘う要素が多いっていうか、定数個しか次元を拡張できない縛りもあって、実は式を良い感じにすると普通のダイクストラで解けるんじゃないかみたいな方針に行ってしまう。

方針ガチャで当たりを引いてもしっかりそれを詰め切れなければ意味がないので、出来るだけ確実な思考の筋道をここで言語化しておきたかった。けどこれはもう把握しておくしかないかも。

以下コード

#include <bits/stdc++.h>
const int INF = 1e9;
const int MOD = 1e9+7;
const long long LINF = 1e18;
#define dump(x)  cout << 'x' << ' = ' << (x) << ` `;
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define rep(i,n) for(ll i=0;i<(n);++i)
#define REPR(i,n) for(ll i=n;i>=0;i--)
#define FOREACH(x,a) for(auto& (x) : (a) )
typedef long long ll;
using namespace std;
typedef pair<ll, ll> P;

template<typename T>
void print(const vector<T> &x) {
    int n = x.size();
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x) {
    int n = x.size();
    rep(i,n) {
        rep(j,x[i].size()) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

template<typename T>
void print(const vector<T> &x, int n) {
    rep(i,n) {
        cout << x[i];
        if (i!=n-1) cout<<" ";
        else cout << endl;
    }
}

template<typename T>
void print(const vector<vector<T>> &x, int n, int m) {
    rep(i,n) {
        rep(j,m) {
            cout << x[i][j] << " ";
        }
        cout << endl;
    }
}

template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

void input_init() {
    cin.tie(0); ios::sync_with_stdio(false);
}

struct Edge {
    ll to, cost;
    Edge(){}
    Edge(ll to, ll cost): to(to), cost(cost){}
};

//           dist, v, fl_free, fl_doulbe
typedef tuple<ll, int, bool, bool> T;
int main(int argc, char const *argv[]) {
    input_init();
    int n,m; cin>>n>>m;
    vector<vector<Edge>> g(n);
    rep(i,m) {
        ll a,b,w; cin>>a>>b>>w; --a,--b;
        g[a].emplace_back(b,w);
        g[b].emplace_back(a,w);
    }

    priority_queue<T, vector<T>, greater<>> pq;
    vector<vector<vector<ll>>> dp(n, vector<vector<ll>>(2, vector<ll>(2, LINF)));

    dp[0][0][0] = 0;
    pq.emplace(0,0,false,false);

    while (!pq.empty()) {
        const auto [dist, cur, fl_free, fl_double] = pq.top(); pq.pop();
        if (dist > dp[cur][fl_free][fl_double]) continue;
        
        for (auto &&e: g[cur]) {
            // 普通に遷移
            if (chmin(dp[e.to][fl_free][fl_double], dp[cur][fl_free][fl_double]+e.cost)) pq.emplace(dp[e.to][fl_free][fl_double], e.to, fl_free, fl_double);

            if (!fl_free) {
                // 無料なので重みは足さない
                if (chmin(dp[e.to][1][fl_double], dp[cur][fl_free][fl_double])) pq.emplace(dp[e.to][1][fl_double], e.to, 1, fl_double);
            }
            if (!fl_double) {
                // 倍の重みを足す
                if (chmin(dp[e.to][fl_free][1], dp[cur][fl_free][fl_double] + e.cost*2)) pq.emplace(dp[e.to][fl_free][1], e.to, fl_free, 1);
            }

            if (!fl_free && !fl_double) {
                // 倍かけて無料にする(今まで通った辺が一つしかない)時、2*w - w = w
                if (chmin(dp[e.to][1][1], dp[cur][fl_free][fl_double] + e.cost)) pq.emplace(dp[e.to][1][1], e.to, 1, 1);
            }
        }
    }

    for (int i = 1; i < n; ++i) {
        cout << dp[i][1][1] << '\n';
    }

    return 0;
}

Codeforces Round #696(Div. 2) D Cleaning

典型が二つほどあって勉強になった。まあ解説見た後12WAしたんですけど......。

問題概要

Problem - D - Codeforces

数列が与えられる。隣合う二つの数が1以上の時、その二つの数を両方とも1減らすことが出来る(片方だけ減らすなどは出来ない)。
適切に操作を行ったとき、数列の要素を全て0に出来るか？ただし 一度だけ任意の隣接する二点をswapすることが出来るものとする。

という問題。

解法

一度に全てを考えようとするととっつきずらいので、まずswapなしの問題を考えてみる。 例えば A = \langle 10, 5, 8, 3 \rangleのような数列が与えられたとする。実はこれは絶対に全ての要素を0にすることが出来ない。 何故なら A_0 > A_1だからである。一番端の要素は二番目の要素としか数を減らせないため、必ず \langle 5, 0, 8, 3 \rangleより良い状況にはならない。

逆に A_0 \leq A_1の数列、例えば A = \langle 5, 10, 8, 3 \rangleを考えてみる。
するとこれは左端から操作すると A = \langle 0, 5, 8, 3 \rangleとなるのだが、 A_0は0になったために以降考慮の必要がなくなり、 A_1を一番端の要素として扱えるようになる。
つまりこの数列は更にこうなって A = \langle 0, 0, 3, 3 \rangle
最後にこうなる A = \langle 0, 0, 0, 0 \rangle

というわけで、条件を「一番端の要素は二番目の要素よりも小さくなくてはならない」という話に一般化し、それを再帰的に(これ使い方微妙に違う気がするんだけどいい言葉が思いつかなかった)適用することで判定が出来る。
これ典型というか競技プログラミングっぽくて好き。

ではこの解法をswapありでも適用できるように拡張していく。
まあswapする位置を全部試さないことにはどうしようもなさそうな見た目をしているので、全部試す方針でいく。
ここでもう一つの典型だが、 隣接する二点をswapする → 二点の周囲以外は状況が変わらない ことを念頭に置く。

その上で「一番端から数字を減らしていく」ことを思い出そう。
すると左から減らしていった数値を保持しておく数列 lと右から減らしていった数値を保持しておく数列 rをそれぞれ持ち、隣接する二点の周囲だけもう一度計算し直してやれば良いという着想を得ることが出来る。

これを実装すれば解けるのだが、端から減らしていった数が一度でも数が負の数になったらダメということを忘れていて死ぬほどWAした。
学びのある問題だったが辛かった。

キーエンスプログラミングコンテスト2021

キーエンスプログラミングコンテスト2021

最近負けすぎててマジでヤバい。どのくらいヤバいかというとCodeforcesでhighest-400, AtCoderでhighest-250をしてしまったくらいヤバい。
そして緑落ちした。ここ一ヶ月何がどうなってるんですかね。危機感を感じたのでわかんなかった問題は全部ブログでまとめることにした。
よく上級者は、低レート帯なら質より量と言うけど、それって既に数学力の蓄積があることが前提な気がしていて、強い人が一瞬で流せるような思考でも僕には時間をかけて理解しなきゃいけないんだなあということを改めて実感した次第です。
どうしても時間がかかってしまうから一日何問こなせるかはわからないけど、スタートラインに立つ才能もないから仕方ないね......。

A問題

何でこれ解けなかったの？ねえ。純粋に精進不足です。解法ガチャで最初に引っかかったものをずっと考え続けてしまうのをやめなければ。
やった思考としては

  • 積の最大値は最大値どうしの掛け算
  • けどAで選ぶべきindex( i )はBで選んだindex( j )以下でならなければならない。
  • ある範囲のBの最大値を求めて、それより左にあるAの要素の最大値をセグ木とかで求めたらうまくいかないかなーと思いながら投げたらWA。
  • 一番ダメだったのはワンチャンとか思いながらこれを投げたことかも。低難易度でやることじゃねえ。反省してください。
  • こういうペア系を扱うときにガチャで排出される解法は大体「片方固定する」なんだけど、何故かAを固定することばっかり考えてた。は？？
  • 逆から見てみたりもしたけどあまり有効じゃなかった。
  • そして何も分からずしんどくなったのでBに行って終わった。

全てがダメだな。どうしてこうなった。
要はBの方を固定してAの最大値を取ってくれば良いだけ(それまでの値とのmaxを取る)なので、300点です。

敗因は、Bを固定することを何故か1ミリも考えなかったこと。
よく考えるとこういう系でAじゃなくBを固定するの初めて見た気がするな。
これAとBが逆だったら解けてただろうな。いやなんで？？
一度やり方が見えなくなると焦ってしまって、ガチャ結果がどれも当てはまらないように見えてしまうのかも。こころの問題。
高難易度帯では通用しないだろうけど、ひとまずは「いうて自分の知識と思考力で解けないことはないやろ」くらいに高を括ってしまうのが良いのかな。

B問題

若干焦ったけど解けた。K個に分けるの面倒で無意味にバグるからやめてほしいです。

C問題

これは完敗かも。自分の知識にないDPだったけど、正直今のDPのやり方が解法ガチャに依存しすぎているのでもう少し抽象的なやり方を身につけたいね。
解説見たけど三分の二は完全に何？という感じ(そもそも言い換えからして考えなかったな......)。
すぬけさんの動画見た。これ水色diffってマジ？ dp[i][j][k] まではうんうんそうですね～っていうか何でこれ思いつかなかったの？ だったけどそこからkを落とすところで草生えた。そっかぁ......。

dp[i][j][k]に行くまで

ある経路に対して、通っていない空白マスごとに3をかける必要がある。関係ないマスの文字は自由に決めていいからね。
ので、k = それまでに通った空白マスの数として dp[i][j][k] でやると解ける。ここにすら行ってなかったのはダメ。

今まであまりこんな遷移の問題をやったことがなかったとはいえ、通ってない空白マスごとに3をかけることすら分からないの、数弱の面目躍如だな。頭大丈夫か？

kを落とすまで

この発想の転換は正直言われてもしばらく意味が分からなかった。難しくて困るんだよね。
お気持ちというか、再現しやすい考え方としては

  • やっぱり「通ってない空白マス」を扱おうとすると係数をかけるときに必要な情報をDPの状態として持つ必要が出てきてつらい
  • 出来るだけ「通っている空白マス」でやっていきたいですね
  • 空白マスを踏むごとに、情報を更新できるとうれしい
  • 最初のマスの係数を 3^{HM-K} として取っておくと、空白マスを踏むごとに1/3していけばいい ← 大天才過ぎて困る

でもDPとして考えると、最初のマスで係数として 3^{HM-K} を取っておくことを考えるのはまあまあ自然な気がする。そうするとこの更新もまあ自然な気がするなあ。

自分の頭が悪いと困っちゃうね。

DはTLを見る限り天才っぽいので困るな。Eの方が典型っぽいけど......？