2023-01-13

モーニングルーティン制定【トポロジカルソートあり】

はじめに

みんなモーニングルーティンってありますか？
僕はまだないので、今から制定していきます。

手順１：ルーティンの列挙

まずは朝起きてから毎日やりたいことを列挙してみます。
例えば

顔を洗う
歯を磨く
服を着替える
寝癖をなおす
コーヒーを淹れる
コーヒーを飲む

など

手順２：依存関係の検討

手順１で挙げたルーティンたちの間には、依存関係があったりなかったりします。
例えば

コーヒーを飲むのは、コーヒーを淹れた後の方がよい。
歯を磨くのは、コーヒーを飲んだ後の方がよい。
- コーヒーがミント味になってしまうので
服を着替えるのは、顔を洗ったあとの方がよい。
- せっかく着替えた服がびしょ濡れになってしまうので
寝癖をなおすのは、服を着替えた後の方がよい。
- 服を脱ぐときに結局髪が乱れるので

など
これをすべてのペアについて検討しておきます。

手順３：実行順の決定

あとは、手順２の要求がすべて満たされるようにルーティンの実行順を決めればモーニングルーティン完成です。
これは、手順１の各ルーティンをノード、手順２の依存関係を有向辺とみたグラフをトポロジカルソートすることと同じなので、以下のアルゴリズムを適用すればよいです（Wikipediaより引用）。

L ← トポロジカルソートした結果を蓄積する空リスト
S ← 入力辺を持たないすべてのノードの集合

while S が空ではない do
S からノード n を削除する
L に n を追加する
for each n の出力辺 e とその先のノード m do
辺 e をグラフから削除する
if m がその他の入力辺を持っていなければ then
m を S に追加する

if グラフに辺が残っている then
閉路があり DAG でないので中断

手でやるもよし、パソコンにやらせるもよし
手でやりたくない人向けに作りました→https://gyouzasushi.github.io/morning-routine/

まとめ

いかがでしたか？

完

2022-12-31

2022年ふりかえり

AtCoder (Highest) : 2080 → 2080 (+0)
Codeforces (Highest) : 2157 → 2157 (+0)
修得単位合計（見込）: 138 → 140 (+2)

🤔
2023年もよろしくお願いします🐇

完

2021-11-08

近況

今週（広義）解いたAtCoderの問題たちです（黄diff以上）

AGC055 B - ABC Supremacy 🟨

（問題文）
状態 $S$ に操作を施して状態 $T$ にできますか？みたいな問題、（逆操作が存在する場合は）「 $S, T$ に操作を施して同じ状態 $X$ にできますか？」と言い換えると見通しが良くなりがちな気がする。
これを念頭に操作を観察していると xABC を ABCx に変換できることに気づくので、ABCABCABCxx...xx みたいなやつを共通のゴール $X$ に据えると解けそう→AC。
解説「 $f(S)$ が well-defined であることは明らかではありません。」→失礼しました…
（提出）

ARC057 B - 高橋君ゲーム 🧪🟨

（問題文）
$N$ 日間で $K$ 回以下ゲームに勝った場合の答えは簡単なDPで求まる。
勝ち数が増えたからと言うて機嫌のいい日が増えるとは限らない（例：サンプル２）のが悩ましいところやけど、そうなるのは $\sum a = K$ なときだけだと思う（勘）ので解けた。
（提出）

ABC129 F - Takahashi's Basics in Education and Learning 🟧

（問題文）
愚直に計算すると $O(L)$ とかになるけど、平方分割の要領で $\sqrt L$ 項ずつ計算していくと $O(\sqrt L)$ になった。
しかし $L \leq 10^{18}$ なのでまだ微妙。そこでもう一度同じ要領で高速化すると、なぜか $O(L^{1/3})$ になって通った。
そんなはずはないと思うので、どこかが二度手間ザウルスやったんやろなあ。
（提出）

ABC128 F - Frog Jump 🟧

（問題文）
$A-B$ が $A$ を割り切るとき、戻ってきた先に蓮がなくて溺れうるので注意する。
ある $x$ があって $2x+1$ 回目のジャンプでぴったりゴールしなきゃだめなので、 $x(A-B) + A =N-1$ が必要。
→ $A, A-B$ を全探索する。 $(A,A-B)$ の組として考えられる個数は $1$ から $N-1$ の約数の個数の和で抑えられて、これはまあ許せる個数そう。
→ あとは各 $A-B$ でシミュレーションしていけば解けそう。
最後のシミュレーションが間に合うか諸説あるところやけど、小さい $A-B$ の場合を前計算しておいたら通った。
（提出）

ABC135 F - Strings of Eternity 🟨

（問題文）
文字列の一致判定が高速にできると、グラフの最長パス？を求める問題に落ちるので解ける。
非本質なはずのグラフパートで無限に手こずってしまって悲しい。
以下学び

DAG の最長パスはトポロジカルソートからのDPで簡単に求まる。
トポロジカルソートに失敗すればDAGじゃない→サイクルがある。

今回はサイクルがあれば答えは必ず $\infty$ なので、これで解けた。
（提出）

ABC226 F - Score of Permutations 🟨

（問題文）
まず問題文がちょっと難しくて困った…。
要するに、各 $d$ について「 $\mathfrak{S}_n$ の元 $\sigma$ のうち位数 $d$ のものはいくつか？」が知りたい（たぶん）。そして $\sigma$ の位数はその巡回置換型から簡単に計算できる（長さの LCM をとればOK）ところ、巡回置換型のパターン数は十分少ない（ $N$ の分割数で、 $N=50$ のとき $204226$ 通り）。ので、解けた！
代数学入門入門が役に立って嬉しいね😊
（提出）

おまけ

AtCoder 黄色に戻ってきました！ぎりぎりで草。
f:id:gyouzasushi:20211108000547p:plain
とりあえず黄色を維持できるようにがんばる。

完

2021-05-10

AtCoder 黄色になるまでにやったこと

AtCoder 黄色になりました！

gyouzasushi - AtCoder

f:id:gyouzasushi:20210510003853p:plain

f:id:gyouzasushi:20210510004140p:plain

やった〜！

コンテスト時間 120 分のところ 118 分 55 秒で D が解けました。ドラマすぎる

やったこと

（競プロ）

ここのところはひたすら Codeforces の Educational Codeforces Rounds のバーチャルコンテストをやっていました。競技プログラミングの好きポイントが「競技」7 対「プログラミング」3 ぐらいなので、コンテスト形式で練習するのが一番テンション上がっていいです。

あとは ECR バチャにちょっと飽きてきたぐらいのタイミングで AtCoder の黄色 difficulty の問題をじっくり時間をかけて解いていくやつをやっていました。こちらの方が濃い練習？力がついてる？感があるような気もします。

（競プロ以外）

自分は数学が高校の IA・llB で止まってしまっているのですが、やはり数学はもっとできた方が得だなあと感じる場面がしばしばあります。そこで、三月から ICPC のチームメイトでもある中高の同級生（理学部）二人と一緒に代数学の勉強を始めました。正直 1 割も理解できている気がしないのですが、そういう話題に対する抵抗がまんまと薄れてくれたのが一番大きいです（今日の D とか？）。何よりおもしろいしね。二人ともいつもありがとう！

今後の目標

低い方の目標：青に落ちても萎えずに戻ってくる。

中ぐらいの目標：黄色を維持する。

高い方の目標：二段昇格。

めっちゃ高い方の目標：AtCoder 橙！

解いた問題

f:id:gyouzasushi:20210510010952p:plain

f:id:gyouzasushi:20210510010827p:plain

f:id:gyouzasushi:20210510010832p:plain

完

2021-02-10

ネタバレ

ブンブンハローユーチューブ。今日は僕の好きな漫画を紹介したいと思います！！！！！！！！

『僕のヒーローアカデミア』ってどんなおはなし？調べてみました！

主人公が髪の毛を食べて能力を得る。
ありえんぐらい強いのに自信なさげでかわいい先輩がでてくる。
主人公の担任（かっこいい）の親友が死ぬ。
その死体が敵に乗っ取られる。
メガネにスーツのサラリーマン風ヒーローが強くてかっこいい。ばりすき
けど死ぬ。

『呪術廻戦』ってどんなおはなし？調べてみました！

主人公が指を食べて能力を得る。
ありえんぐらい強いのに自信なさげでかわいい先輩がでてくる。
主人公の担任（かっこいい）の親友が死ぬ。
その死体が敵に乗っ取られる。
メガネにスーツのサラリーマン風術師が強くてかっこいい。ばりすき
けど死ぬ。

いかがでしたか？

2020-11-22

AtCoder Regular Contest 108 に参加しました

黄パフォ出た回、饒舌がち　これあります
atcoder.jp

成績

f:id:gyouzasushi:20201121231806p:plain f:id:gyouzasushi:20201121231811p:plain
300位ぴったりやん！飛び賞待ってます。

A - Sum and Product

問題概要：整数 $S,P$ が与えられる。 $N+M=S,N\times M=P$ を満たすような正の整数の組 $(N,M)$ は存在するか？
制約： $1\leq S,P\leq 10^{12}$

うわ知ってるこれ！解と係数の関係やろ！で五分使ってもうた。たいへんもったいない……。 $N,M$ は $P$ の約数なので、適当に調べれば十分。

コードを表示

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int main() {
    ll s, p;
    cin >> s >> p;
    vector<ll> v;
    for (ll d = 1; d * d <= p; d++) {
        if (p % d) continue;
        v.push_back(d);
        v.push_back(p / d);
    }
    sort(v.begin(), v.end());
    for (ll n : v) {
        ll m = s - n;
        if (*lower_bound(v.begin(), v.end(), m) == m) {
            cout << "Yes\n";
            return 0;
        }
    }
    cout << "No\n";
}

B - Abbreviate Fox

問題概要：長さ $N$ の文字列 $s$ が与えられる。「 $s$ から " fox " という連続部分文字列をひとつ選んで取り除き、その前後の部分を連結する」という操作を何度でも行えるとき、操作後の $s$ の長さは最小でいくつか？
制約： $N\leq 2\times 10^5$

" fox " なのが難しい。" fox " を " (o) "に置き換えて括弧列っぽく考えると、stack でシミュレーションにしか見えなくなります。

コードを表示

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define sz(x) int(x.size())
using namespace std;
int main() {
    int n;
    string s;
    cin >> n >> s;
    string t;
    for (char c : s) {
        t += c;
        if (sz(t) >= 3 && t.substr(sz(t) - 3, 3) == "fox") {
            rep(_, 3) t.pop_back();
        }
    }
    cout << sz(t) << '\n';
}

C - Keep Graph Connected

問題概要： $N$ 頂点 $M$ 辺からなる、自己ループのない連結グラフが与えられる。グラフのそれぞれの辺には、 $1$ 以上 $N$ 以下の整数で表されるラベルがついている。
グラフのそれぞれの頂点に $1$ 以上 $N$ 以下の整数を書き込んだのち、以下の条件を満たさない辺をすべて取り除く。
（条件）辺の両端の頂点に書き込まれたふたつの整数のうち、いずれか一方のみが辺に付けられたラベルと等しい。
辺を取り除いたあとのグラフが連結のままであるような頂点への整数の書き込み方が存在するか判定せよ（あれば一例を出力）。
制約： $2\leq N\leq 10^5, N-1\leq M \leq 2\times 10^5$

こういう問題は

サンプルに No がないので必ず構築できるはず、という勘がはたらく（AtCoder あるある）。
適当な全域木で考えたら嬉しいがち、と歴史の教科書に書いてある。

以上を踏まえて、「どのような木に対しても問題文の条件を満たすように整数を書き込むアルゴリズムがあるはず、なのでそれを考えよう」みたいな方針で考察を進めた。木だったら話が早い。一回 WA になって泣きそうになったけど、すぐミスに気がついて AC できた。えらすぎぶっ壊れ

コードを表示

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
struct UnionFind {
    vector<int> data;
    UnionFind(int size) : data(size, -1) {
    }
    int root(int x) {
        return (data[x] < 0) ? x : data[x] = root(data[x]);
    }
    bool unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x != y) {
            if (data[y] < data[x]) swap(x, y);
            data[x] += data[y];
            data[y] = x;
        }
        return x != y;
    }
    bool find(int x, int y) {
        return root(x) == root(y);
    }
    int size(int x) {
        return -data[root(x)];
    }
};
int main() {
    int n, m;
    cin >> n >> m;
    using P = pair<int, int>;
    map<P, int> cs;
    vector<vector<int>> g(n);
    UnionFind uf(n);
    vector<bool> used(n);
    rep(i, m) {
        int u, v, c;
        cin >> u >> v >> c;
        u--, v--, c--;
        if (uf.unite(u, v)) {
            cs[P(u, v)] = c;
            cs[P(v, u)] = c;
            g[u].push_back(v);
            g[v].push_back(u);
            used[c] = 1;
        }
    }
    int x = -1;
    rep(i, n) if (!used[i]) x = i;
    vector<int> ans(n);
    ans[0] = x;
    auto dfs = [&](auto dfs, int pos, int pre) -> void {
        for (int nxt : g[pos]) {
            if (nxt == pre) continue;
            if (~pre && cs[P(pos, pre)] == cs[P(pos, nxt)] && ans[pos] != x)
                ans[nxt] = x;
            else
                ans[nxt] = cs[P(pos, nxt)];
            dfs(dfs, nxt, pos);
        }
        return;
    };
    dfs(dfs, 0, -1);
    rep(i, n) cout << ans[i] + 1 << '\n';
}

D - AB

問題概要：整数 $N$ と四つの文字 $c_{AA},c_{AB},c_{BA},c_{BB}$ が与えられる（四つの文字はそれぞれ 'A' か 'B' のいずれか）。文字列 $s=$ " AB " に対して、以下の操作を任意の順序で行う。

$s_i=$ 'A' , $s_{i+1}=$ 'A' なる $i$ を選び、 $s$ の $i$ 文字目と $i+1$ 文字目の間に $c_{AA}$ を挿入する。

$s_i=$ 'A' , $s_{i+1}=$ 'B' なる $i$ を選び（中略） $c_{AB}$ を挿入する。

$s_i=$ 'B' , $s_{i+1}=$ 'A' なる（中略） $c_{BA}$ を挿入する。

$s_i=$ 'B' , $s_{i+1}=$ 'B' （中略） $c_{BB}$ を挿入する。

$s$ の長さが $N$ になるまで操作を行ったあとの $s$ としてありうる文字列の個数を（mod $10^9+7$ で）求めよ。
制約： $2\leq N\leq 1000$

何をどうしていいか全くみえないまま二十分ぐらい経っちゃってかなり苦しんだ。でも「数え上げる前に判定問題を解く」の典型を思い出してからはどんどん考察が進んだ！！！！！！えらい。
でも出てきた答えがどう考えても $N\leq 1000$ の制約に見合ってなくて、ここでもうひと苦しみした。まあもう時間もないし、とりあえず書いてとりあえず出してみるか！w の精神が功を奏したね。どうせ僕の提出なんて…… → あ〜れ〜れ〜〜？　を地で行ってもうた。なんか場合分けすれば解けます。

コードを表示

#include <bits/stdc++.h>
#include <atcoder/modint>
using namespace std;
using mint = atcoder::modint1000000007;
int main() {
    const int N = 400400;
    vector<mint> fact(N + 1), ifact(N + 1);
    fact[0] = 1;
    for (int i = 1; i <= N; i++) {
        fact[i] = fact[i - 1] * i;
    }
    ifact[N] = fact[N].inv();
    for (int i = N; i >= 1; i--) {
        ifact[i - 1] = ifact[i] * i;
    }
    auto comb = [&](int n, int r) {
        if (n < r || r < 0) return mint(0);
        return fact[n] * ifact[r] * ifact[n - r];
    };

    int n;
    cin >> n;
    char caa, cab, cba, cbb;
    cin >> caa >> cab >> cba >> cbb;
    if (n == 2) {
        cout << 1 << '\n';
        return 0;
    }
    if (cab == 'A') {
        if (caa == 'A') {
            cout << 1 << '\n';
            return 0;
        }
        if (cba == 'B') {
            cout << mint(2).pow(n - 3).val() << '\n';
            return 0;
        }
        mint ans = 0;
        for (int i = 2; i <= n - 1; i++) {
            ans += comb(i - 1, n - i - 1);
        }
        cout << ans.val() << '\n';
    } else {
        if (cbb == 'B') {
            cout << 1 << '\n';
            return 0;
        }
        if (cba == 'A') {
            cout << mint(2).pow(n - 3).val() << '\n';
            return 0;
        }
        mint ans = 0;
        for (int i = 2; i <= n - 1; i++) {
            ans += comb(i - 1, n - i - 1);
        }
        cout << ans.val() << '\n';
    }
}

E,F

todo

おしまい

次回 2064 perf で rating 1900 のるらしい。でもこういうこと考えてると絶対失敗するねんな。人生そういうとこあるわ。無欲でいこう。

2020-11-16

AtCoder Beginner Contest 183 に参加しました

全完！嬉しくなっちゃったので書きます。

成績

f:id:gyouzasushi:20201116012146p:plain f:id:gyouzasushi:20201116012151p:plain
Highest！！！！！！サイコーーーーーー

A - ReLU

問題：（リンク）
定義通りに書く。

コードを表示

#include <bits/stdc++.h>
using namespace std;
int main() {
    int x;
    cin >> x;
    if (x >= 0)
        cout << x << '\n';
    else
        cout << 0 << '\n';
}

B - Billiards

問題：（リンク）
相似なつかし〜〜。 $(S_x,0),(G_x,0)$ を $S_y : G_y$ に内分する点が答え。

コードを表示

#include <bits/stdc++.h>
using namespace std;
int main() {
    double sx, sy, gx, gy;
    cin >> sx >> sy >> gx >> gy;
    cout << fixed << setprecision(10) << (sx * gy + gx * sy) / (sy + gy)
         << '\n';
}

C - Travel

問題：（リンク）
$2,3,\ldots,N$ の順列を全部試せばOK。最後スタートに戻ってくるん見落として少しモタモタしてもうた。巡回セールスマンあるある

コードを表示

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
int main() {
    int n;
    ll k;
    cin >> n >> k;
    vector<vector<ll>> t(n, vector<ll>(n));
    rep(i, n) rep(j, n) cin >> t[i][j];
    vector<int> p;
    rep(i, n - 1) p.push_back(i + 1);
    int ans = 0;
    do {
        ll now = 0;
        int x = 0;
        rep(i, n - 1) {
            now += t[x][p[i]];
            x = p[i];
        }
        now += t[x][0];
        ans += (now == k);
    } while (next_permutation(p.begin(), p.end()));
    cout << ans << '\n';
}

D - Water Heater

問題：（リンク）
「区間 $[S_i,T_i)$ に $P_i$ 加算」という操作を $N$ 回行えば、各時刻について合計で何リットルのお湯が使われるかが求められる。いもす法。使われるお湯が $W$ より多い時刻があれば No。

コードを表示

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using ll = long long;
int main() {
    int n;
    ll w;
    cin >> n >> w;
    vector<ll> v(200200);
    rep(i, n) {
        int s, t;
        ll p;
        cin >> s >> t >> p;
        v[s] += p;
        v[t] -= p;
    }
    rep(i, 200200 - 1) v[i + 1] += v[i];
    if (*max_element(v.begin(), v.end()) <= w)
        cout << "Yes\n";
    else
        cout << "No\n";
}

E - Queen on Grid

問題：（リンク）
DP。愚直にやると遷移が忙しすぎるので、縦横斜めの累積和を持っておいて一気に更新。
いやめっっちゃ時間つかってもうた！！！「愚直DPはキツいな→累積和」までがまず遅かったし、焦ってもうて実装もミスしまくりやった……。落ち着いていこ〜〜〜

コードを表示

#include <bits/stdc++.h>
#include <atcoder/modint>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
using mint = atcoder::modint1000000007;
int main() {
    int h, w;
    cin >> h >> w;
    vector<string> s(h);
    rep(i, h) cin >> s[i];
    vector<vector<mint>> l(h, vector<mint>(w));
    vector<vector<mint>> u(h, vector<mint>(w));
    vector<vector<mint>> lu(h, vector<mint>(w));
    vector<vector<mint>> dp(h, vector<mint>(w));
    dp[0][0] = 1;
    rep(i, h) rep(j, w) {
        if (s[i][j] == '#') {
            l[i][j] = u[i][j] = lu[i][j] = 0;
            continue;
        }

        if (i - 1 >= 0) dp[i][j] += u[i - 1][j];
        if (j - 1 >= 0) dp[i][j] += l[i][j - 1];
        if (i - 1 >= 0 && j - 1 >= 0) dp[i][j] += lu[i - 1][j - 1];

        if (i - 1 >= 0)
            u[i][j] = u[i - 1][j] + dp[i][j];
        else
            u[i][j] = dp[i][j];

        if (j - 1 >= 0)
            l[i][j] = l[i][j - 1] + dp[i][j];
        else
            l[i][j] = dp[i][j];

        if (i - 1 >= 0 && j - 1 >= 0)
            lu[i][j] = lu[i - 1][j - 1] + dp[i][j];
        else
            lu[i][j] = dp[i][j];
    }
    cout << dp[h - 1][w - 1].val() << '\n';
}

F - Confluence

問題：（リンク）
少子化
もし生徒全員が同じクラスだったら UnionFind （ACLでいうDSU）一発で解けるのになあ〜〜〜という気持ちを起点に考えた。UnionFind が高速なのは所謂「マージテク」のおかげで、ということはクラスの情報も同じようにマージしていけばいい感じになりそう？→なりました　AC

コードを表示

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
using namespace std;
struct UnionFind {
    vector<int> data;
    vector<map<int, int>> mp;
    UnionFind(int size, vector<map<int, int>> _mp) : data(size, -1), mp(_mp) {
    }
    int root(int x) {
        return (data[x] < 0) ? x : data[x] = root(data[x]);
    }
    bool unite(int x, int y) {
        x = root(x);
        y = root(y);
        if (x != y) {
            if (data[y] < data[x]) swap(x, y);
            data[x] += data[y];
            data[y] = x;
            for (auto [key, num] : mp[y]) {
                mp[x][key] += num;
            }
        }
        return x != y;
    }
    bool find(int x, int y) {
        return root(x) == root(y);
    }
    int size(int x) {
        return -data[root(x)];
    }
};
int main() {
    int n, q;
    cin >> n >> q;
    vector<map<int, int>> mp(n);
    rep(i, n) {
        int c;
        cin >> c;
        mp[i][c] = 1;
    }
    UnionFind uf(n, mp);
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int a, b;
            cin >> a >> b;
            a--, b--;
            uf.unite(a, b);
        }
        if (t == 2) {
            int x, y;
            cin >> x >> y;
            x--;
            cout << uf.mp[uf.root(x)][y] << '\n';
        }
    }
}

完