週記（2021/06/28-2021/07/04）

06/28 (MON)

9:00 起床。夜更かしをしたのに意外と眠くないし、体調も悪くない。 朝ごはんを食べながら今日の典型を確認する。

https://atcoder.jp/contests/typical90/tasks/typical90_bz

問題概要。$ N $ 頂点 $ M $ 辺の無向グラフが与えられる。 自分より頂点番号の若い隣接頂点が $ 1 $ つだけ存在するような頂点の数を答えよ、という問題。

それぞれの辺に対して、頂点番号が大きい方に $ +1 $ カウントする配列を構成して最後に配列を舐めて、$ 1 $ の要素数を数える。 $ O(N+M) $ で解けるし、グラフを構成する必要も実はない。構成した方が慣れ親しんだ手法な気もするが。 キーワードがわからない。「隣接頂点全探索は辺の数のオーダー」とかですか、わかりません。

わからないながらも大学に向かう。時計をどっかにやってしまってめちゃくちゃ QoL が下がっている。 行きの電車内では昨日の AGC-B を改めて見て考えていた。 挿入 DP は昨日散々考えて不可能であると判断したのでのんびり眺めた。

ちょうど全体の和の半分になるような subset を考えた時にその subset を高橋くんが取る場合の数に思いを馳せた。 高橋くんがとらない数字は青木くんが取る。それぞれの subset を独立に並び替えてその順番で取ることを考えると、それぞれの並べかえと 数えたい順列が一対一対応することがわかる。気づいてしまえばボケ簡単だった。

昨日ちゃんと解けた C といいこの B といい、順列の数え上げというありふれたテーマなのにパターンマッチへのアンチテーゼのようで、AGC の問題の質の高さを感じた。

大学に着いたらいつものケイジャンチーズ牛飯を購入してモンスターエナジーとともに摂取する。 食べ終わる時間ぐらいに、ゼミが開始する。今日も B4 の発表回。いい意味でも悪い意味でもスライドにそれぞれの個性がでているなあと思った。 去年の僕もこんな風に見られていたと思うと震えちゃうね。

今日のセブンのおやつ。先週から試してるんだけどこれがおいしい。

ちなみに今日のおやつにはいつも通りプリンを買ったのだが、先週から試しているこれがかなり美味しいと再確認した。 三層になっているのだが、一番上がチーズケーキっぽく、真ん中はクリームで、一番下がプリンになっている。

そんなこんなで作業をしていた。今日は途中で先輩方と話こみ、様々な話になった結果、色々な知見とかが得られた。 話の話題に出て読もうと思った論文を Paperpile: Modern reference and PDF management - Paperpile に入れた。 こういうののために研究室に行っているというところが大いにある。本当は頻度を増やしたいと思っているんだけど、研究室に行く日はほぼ確実にピアノの練習ができないため、中々難しいところである。

帰ると 22:00 ぐらい。夕食をむさぼる。 夕食後、上に書いた AGC-B の解法で書いて通した。これで通らなかったら上の解法を消さなければならないのでほっとした。

06/29 (TUE)

11:00 起床。正しくは、9:00 には起きていたのだが布団の中でもぞもぞする時間が長すぎた。

今日の典型を確認する。★3 だ。

https://atcoder.jp/contests/typical90/tasks/typical90_ca

問題概要。$ H \times W $ の二次元配列 $ A,B $ が与えられる。$ 4 $ マスの正方形領域に対して一括で $ \pm 1 $ をする操作を行うことが出来る時、$ A $ を $ B $ に一致させることが可能かどうか判定せよ、という問題。

蟻本には $ \mod 2 $ の世界での問題（正方形フリップ）が載っていたような気がする。 今確認したら蟻本 p.141 にそれらしき POJ の問題が載っているのだが、自分の記憶より難しい問題だった。 こういう問題は、端から見ていくとそこで操作を行うべきかが一意に決まるため貪欲に解ける。具体的に言うと、上にも左にも不確定なマスがないようなマスが左上になるような正方形領域に何回操作をするかは自明にそのマスの値により一意だ。 蟻本のやつは、$ 3 \times 3 $ の正方形領域だったため $ 1 $ 行目を決め打たないと一意にならなかったが、この問題ではその心配もない。

バイト先の slack からの返信を確認した。確認しながら、サボってた時期の典型をちょっと見ることにした。

059 - Many Graph Queries（★7） とにらめっこをすることにした。

問題概要は簡単。$ N $ 頂点 $ M $ 辺の DAG が与えられて、頂点 $ A_i $ から $ B_i $ に到達可能かどうかのクエリ $ Q $ 個に答える。 sample の隣接行列を書いてしばらくグッと睨んでいた。

しばらく睨んでまともな解法がなさそうなことに気づき $ 64 $ bit をまとめて処理することを考える。 到達可能性の行列は頂点番号の降順（トポロジカル順序の逆順）に構築可能だ。 $ u < v $ であるような頂点 $ u,v $ を考えたときに、$ u $ の到達可能性を bit vector で考えたとき、 $ u $ が $ v $ に直接到達可能ならば、 $ v $ の到達可能性の bit vector との OR で更新すれば良いことが分かる。直接到達可能な頂点数は辺の数の $ M $ と一致するため、全体で到達可能性行列は $ O(MN) $ で前計算出来る。 OR をとるパートで $ 64 $ bit ずつ処理すれば $ 64 $ 倍速くなり、多分間に合うのだろう。まあ $ 64 $ bit というかワードサイズなのだが…

ここで書き始めるも、Memory Limit を思い出し計算すると $ 1200 $ MB ぐらいかかりそうなことが判明。最悪や。 冷静になると、DAG の到達可能性なので、$ M _ {i,j} \quad (i \leq j) $ の部分だけあれば十分なので大体半分ぐらいになるから足りそう。 この手の高速化は結構カツカツな状況が多いので offset やブロックのインデックスを求める時に割り算を使うと終了しそう。ワードサイズは当然二冪なのでビットシフトや AND を使おう。でも二冪定数の割り算ぐらいビット演算に最適化してくれそうだけど…どうだろ…

色々工夫して頑張って書いたら $ 500 $ ms を割ったので、記念にソースを貼っておく。 まあ測定結果とかキャッシュミス率とかを監視しながらチューニングをしたわけではないのでもっと速くなるかもしれないけど。 やったことを箇条書きしてみる。

• 最大ケースで使用するサイズを事前に求めて、そのサイズでメモリプールをグローバル変数で静的確保。
  • malloc でいちいち確保をすると free も面倒だし困る。今回途中で解放や再利用はしないためこれでいい。
  • bitset が全て連続領域なので多少高速化に寄与する可能性あり。
  • マージの時に連続領域だと次の bit vector の先頭ポインタを使うことで楽に後ろから OR を取れる。
• Fast IO … 入力を一括で静的領域に受け取り、自分でパース。出力はバッファリングして最後に一気に write & flush する。
  • $ 10^{5} $ 行ぐらいあるので、間で何回も flush すると遅そう。入力もそこそこ多いけどこっちの影響は不明。
• 最適化オプションは O3 にした。何か起これと祈る。

▶ソースコードを展開

#pragma GCC target("avx2")
#pragma GCC optimize("O3")

#include <vector>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <cstdint>
#include <cstring>
#include <cctype>

using namespace std;
using u64 = uint64_t;

//-------------------------------------------------
//--Fast I/O (Chotto Hayai Nyuushutsuryoku)
//-------------------------------------------------
class FastIO
{
private:
    static const int IO_SIZE = 3e6;
    char rbuf[IO_SIZE], wbuf[IO_SIZE], *rp, *wp;
    char temp[19];
    inline bool minus(char c){return c=='-';}
    inline int cnum(char c){return c-'0';}
    inline int numc(int c){return c+'0';}
public:
    FastIO(){
        fread(rbuf,1,IO_SIZE,stdin);
        rp=rbuf; wp=wbuf;
    }
    ~FastIO(){fwrite(wbuf,1,wp-wbuf,stdout);}
    template<typename T=int>
    inline T readInt(){
        bool s; T ret=0;
        while(!isdigit(*rp) && !minus(*rp)) rp++;
        if (s=minus(*rp)) rp++;
        while(isdigit(*rp)) ret=ret*10+cnum(*rp++);
        return s?-ret:ret;
    }
    inline void readStr(string &s){
        string t="";
        while(isspace(*rp)) rp++;
        while(!isspace(*rp)) t+=*rp++;
        s.swap(t);
    }
    inline char getc(){
        while(isspace(*rp)) rp++;
        return *rp++;
    }
    inline void putc(int c){*wp++ = c;}
    inline void puts(const char *s){while(*s!='\0') putc(*s++);}
    inline void writeStr(const string &s){
        for(auto c:s) putc(c);
    }
    template<typename T>
    inline void writeInt(T x){
        if (x==0){putc('0'); return;}
        if (x<0) putc('-'), x=-x;
        char *tp=temp; T y=x;
        do{
            y=x/10;
            *tp++ = numc(x-y*10);
        }while(x=y);
        while(tp!=temp) putc(*(--tp));
    }
    FastIO& operator<<(const char a){putc(a);return *this;}
    FastIO& operator<<(const char *s){puts(s);return *this;}
    FastIO& operator<<(const string &a){writeStr(a);return *this;}
    FastIO& operator<<(const int a){writeInt(a);return *this;}
    FastIO& operator<<(const long long a){writeInt(a);return *this;}
    FastIO& operator>>(char &a){a=getc();return *this;}
    FastIO& operator>>(string &a){readStr(a);return *this;}
    FastIO& operator>>(int &a){a=readInt<int>();return *this;}
    FastIO& operator>>(long long &a){a=readInt<long long>();return *this;}
};
#define br '\n'
FastIO io;

constexpr int N_MAX = 100001;
constexpr int POOL_MAX = 78224992;
u64 pool[POOL_MAX];

u64 *ptr=pool;
inline u64 *get_from_pool(int sz){
    u64 *ret = ptr;
    ptr += sz;
    return ret;
}

inline void pool_clear(){
    memset(pool,0,sizeof(u64)*(ptr-pool));
}


u64 *vs[N_MAX];

inline void set_bit(int i, int j){
    int b = (j>>6) - (i>>6);
    vs[i][b] |= (u64)1 << (j&63);
}

inline bool get_bit(int i, int j){
    int b = (j>>6) - (i>>6);
    return vs[i][b] >> (j&63) & 1;
}

inline void or_merge(int i, int j){
    for(u64 *p=vs[i+1]-1, *q=vs[j+1]-1; q>=vs[j]; p--, q--){
        *p |= *q;
    }
}

inline void print_bitset(int i){
    int lead = ((i>>6)<<6);
    for(int j=0; j<lead; j++){
        putchar('0');
    }
    for(u64 *p=vs[i]; p<vs[i+1]; p++){
        for(int j=0; j<64; j++){
            if ((*p)>>j&1) putchar('1');
            else putchar('0');
        }
    }
    putchar('\n');
}

int main()
{
    int N,M,Q;
    io>>N>>M>>Q;
    
    int sz = (N+63)>>6;
    for(int i=0; i<N; i++){
        int offset = i>>6;
        vs[i] = get_from_pool(sz-offset);
    }
    vs[N] = ptr;
    pool_clear();
    
    vector<vector<int>> G(N);
    for(int i=0; i<M; i++){
        int x,y;
        io>>x>>y;
        x--; y--;
        G[x].push_back(y);
        set_bit(x,y);
    }

    for(int i=N-1; i>=0; i--){
        set_bit(i,i);
        for(int j:G[i]){
            or_merge(i,j);
        }
    }

    // for(int i=0; i<N; i++){
    //     print_bitset(i);
    // }

    while(Q--){
        int a,b;
        io>>a>>b;
        if (get_bit(a-1,b-1)) io<<"Yes\n";
        else io<<"No\n";
    }
    
    return 0;
}

そして、毎週恒例のピアノしばき。今週は、最後まで譜面の流れの把握が終わった。 ここからは只管にスムーズに綺麗に速く弾けるかを、訓練によって伸ばしていくパートなのである意味気が楽。

夕食まで少し時間があったので論文を読む。集中力が持たないので終了。

夕食のあとは通話をする用事があったのでする。 そういえば、この前研究室の先輩がやっていたため初めて知ったんだけど、zoom ってスペースキーを押しながら喋ると一次ミュート解除ができるらしい。これを使えば色々な場面で誤爆を起こしにくいし、わざわざどっかに行ってしまった zoom の窓を探してミュートボタンを解除する作業が必要なくなる。 自分は感動したんだけど、実はみんな知っていたりしますか？

通話が終わる。もうなんか今日はいいかという気分になる。 競技プログラミングの問題を一問通してもうだらだらすることにした。

D - アルファベット探し

問題概要。$ 7 \times 7 $ のサイズの $ A,B,C $ の文字のドットパターンみたいなのが与えられる。 これが $ 90 $ ° 単位で回転したり、相似比が正整数になるような拡大が可能である。 大きな図面 $ H \times W $ が与えられるので、それぞれのアルファベットの出現回数を答えよ、という問題。

拡大があるので、真面目にパターンマッチングっぽいことをすると工夫が必要な上、かなり怠い（というか完成させられるか怪しい）実装になりそうだ。 こういう問題は色々な側面からそれぞれのパターンの特徴が得られないかを観察する。 一番ありがちなのは塗られているマスの数とかである。 今回も数えてみると、$ 7 \times 7 $ の $ A,B,C $ の塗られているマス数はそれぞれ $ 12,16,11 $ だ。 これらの数が正整数の相似比で拡大されるので、任意の正の平方数を掛けてもユニークか確認すると、しっかりユニーク。 パターン同士が重なることはないと制約にあるので $ 8 $ 近傍を接続した連結成分のサイズを確認すればいい。 DFS を用いて実装するのが楽で、 $ O(HW) $ の計算量で計算できる。

パターンから取りやすい特徴を抽出して判別をする問題、ICPC のフィリピン地区大会で出会ったため一生忘れなそう。 あれは $ A $ から $ Z $ まであったので特徴を抽出する段階でまあまあ嫌だったけど。 今回はひとつの特徴で完全に判別がついたけれど、$ 2 $ つ以上の取りやすい特徴の複合キーで判別することの方が多そう。

就寝。

06/30 (WED)

9:30 起床。10:45 分提出のショートレポートを書く。 物理っぽい内容が含まれている講義なので、大分懐かしく感じる。 情報工学をしているとマジでいわゆる理系っぽいことは何もできなくなっていく。 大学受験化学なんて多分 $ 8 $ 割はもう忘れている。

ショートレポートを書き終えて朝食を食べながら、今日の典型を確認する。★6。

https://atcoder.jp/contests/typical90/tasks/typical90_cb

問題概要。$ D $ ビット以内で表現可能な正整数の列 $ A $ が与えられる。$ A $ の全ての要素との AND が $ 0 $ でないような整数 $ x \quad (0 \leq x < 2^{D})$ の数を求めよ、という問題。

制約を見ると $ N \leq 20 $ で $ D \leq 60 $ だ。こんなんもう桁 DP やるだけではないでしょうかとなる。 bit DP との複合だから難しいということなのかなとか思いながら DP を組む。 $ dp[i][S]$ : $ i $ 桁目まで $ x $ を決めて、$ A $ の各要素との共通部分を持っているかどうかの bit vector が $ S $ の時の場合の数。

この DP は状態数が $ O(DN) $ である。愚直に遷移すると $ O(N) $ かかる。 ここで初めてこの出題の意図を理解する。このままでは計算量が $ O(DN^{2}) $ でかなり怪しい。 事前に $ B_i $ : $ x $ の $ i $ 桁目を $ 1 $ にすることで共通部分を持つことの出来る $ A $ の要素の集合、つまり $ i $ 桁目のビットが立っている要素の集合の bit vector を前計算することで、遷移が $ O(1) $ になり計算量は $ O(DN) $ と余裕になる。 よく考えると、昨日の日記で解いたワードサイズ定数倍改善と同じ。 でも定数倍改善かなり頑張ればそのままでも通ったりするかも

典型が解けて安心しながら多少作業をするも、ピアノがあるのでピアノをしばく。 レッスンに行く。下手くそ。以上。頑張ります。

帰ってきてからは、主に競プロをやっていた。作業もちゃんとした。 夕飯を食べたあとはカプリティオチャンネルの動画を見ていた。

www.youtube.com

僕自身は全然競技クイズはやらず、たまにみんはやをプレイするぐらいの一般人だが、クイズを見るのは好きだし、 カプリティオチャンネル等のクイズ系の YouTube チャンネルはしっかり一般人にも楽しめるように作って合って見やすい。 最近ちょっと YouTube でもこうの短い動画以外のものを見る時間がとれていなかったので面白そうなものから消化していった。

ここで slack を確認すると、研究室内で濃厚接触者が出たらしく（感染者というわけではなさそうだが）、 とりあえず二週間ぐらい全てがオンラインで行われて、かつ研究室にもなるべく行かないようにというメッセージが来ていた。 二週間の間、ケイジャンとはお別れの様だ。というか二週間多分地元すら出ないことが確定した。

嘘をついた。3 日にはワクチンを接種しに行く予定である。なんなら、他の外出の予定も既にあった。ショックで一瞬全てを忘れていた。

■■■■■の予定表を入れなければならなくて、これがなかなか自分が微妙に忙しいせいで埋まらなくて困っていた。 正直困り果てていたが、催促のメッセージが来てしまったのでちょっと無理っぽい感じに入れて後でいろんな人にお話をしなきゃだめかも… こういうなんか懸案事項が複数ある状態って死ぬほど嫌いで、耐えがたい。こういう時の精神の持っていき方が $ 23 $ 年ちょい生きてて一ミリもわからねぇ。

あと、書類って何で一意解釈できない項目のオンパレードなんだろう。 本当に助けてほしい。普通の人間がこういうのを普通にこなしていると思うと信じられない。HELP！！！

取り乱したが、明日は朝に大切な用事があるので今日は持参物を確認して寝るか。

寝る前にサボっていた典型を一つ通すか、と 60 を見たら既視感があったので週記を見返したら考察はあった。

右から見て最大値が $ A_i $ になる LIS が欲しくなる。 LIS の DP は $ O(1) $ で revert が可能なので、事前に右からの LIS は計算しておき順次 revert していけば欲しいものが得られそうだ。

週記（2021/06/7-2021/06/13） - むかでの競プロ備忘録

どうでもいいけど、永続配列を使えば revert の必要すらないな。

書き上げた段階で、自分の脳がおかしいことに気が付いた。 普通に revert なんてことをしなくても左右からそれぞれ $ A_1 \cdots A _ {i - 1} $ と $ A _ {i+1} \cdots A_N $ の LIS の長ささえわかれば答えが出るので、左右から DP するだけ問題でした。う～んこの…

07/01 (THU)

7:10 起床。大切な用事があったのでちゃんと起きられて安心した。 雨がしっかりを降っている。

支度と朝食を済ませて目的地に向かう。行きの電車で今日の典型を確認する。★5。

https://atcoder.jp/contests/typical90/tasks/typical90_cc

問題概要。$ N $ 人の生徒がいて、 $ i $ 人目の生徒の身長と体重がそれぞれ $ A_i, B_i $ となっている。 チーム内のどの $ 2 $ 人を取ってきても、その身長の差・体重の差が $ K $ 以下であるようなチームを作りたい。 作れるチームの最大人数を答えよ、という問題。

実は昨日より悩んでしまった…。昨日のは着眼点を間違わなければ処理するだけの問題だったが、今日はどこに目をつけるかが難しいように感じた。 $ A_i, B_i \leq 5000 $ と $ K \leq 5000 $ という制約があることに気づく。 ここに注目すると、生徒を二次元平面上に点としてプロットすることができる。 情報のペアや、区間を二次元平面にプロットするのは典型なのでここに詰まったのは反省の余地がある。 この時に条件がどのように言い換えられるかを考えると、$ K \times K $ の正方形領域に入る点の集合なら条件を満たす。 というわけで、二次元累積和を前計算することで $ O(A _ {max} \cdot B _ {max}) $ で解くことができた。

典型が解けた安心感から、後は到着するまでうとうとしていた。 用事のためとはいえ、東京に行くのが久しぶりでテンションが上がった。

初めて行く場所だったので早めに着くように調整したのだが、やっぱり迷う。都会難しすぎるぜ。 まあそこは時間に余裕があったので結果として問題がなかった。 問題なのは雨がメチャクチャに降っていたことだ。 自分の革靴は大分前から履いていて裏のゴムは大分ヘタってしまっている。 その関係で雨の日に滑りやすい地面をあるくとヌゥルヌゥルしまくって怖いのだ。 朝から何回も転びそうになっていたんだけど、ついに目的地の目前で大ゴケしてしまった。 その際に左手首を負傷した。ピアノにも音ゲーにも支障が出そうで心から嫌だった。 あと結構色々な植物が繁茂している場所でコケたので汚れるし周りに人が居なかったので感情を抑えられず声出た。 雨の日にはもうその革靴を履いて外出しないことを誓った。というかいい加減買い替え時なのかもしれない。

最悪な気分になりながらも予定よりも $ 15 $ 以上早くに到着していた。 汚れたズボンとかカバンとかを拭いていたので詳しい時間はあまり覚えていない。

さて用事を終えて昼飯を食べなければ餓死する時間になってしまった。 とはいえ、全然親しみのない土地で飯を探すのに苦労してしまった。 困り果ててキョロキョロしていたのだが、完全に都会に出てきたての田舎の若者ムーブをしていたので恥ずかしい。 普段都会人と行動を共にして自分も都会人のフリをしているのだが、いざ一人になると無力な田舎者ということが暴かれていく。

ダイバーシティという施設が近くにあることは知っていたので、ここに向かうことにした。

歩いていると、フジテレビくんを発見。

歩いていると、フジテレビくんを発見した。写真を撮っているところを人に見られて恥ずかしかった。 施設に到着すると、ドラえもんが出迎えてくれた（画像無し）。 中に入るとうんこミュージアムなるものまであった。 飯を探しているのにコレに出会ってしまい、もう顔中○まみれや。

施設内でまたしても迷子になる。エレベーターが探せない。やっとの事でエレベーターと施設の案内みたいなのを発見すると、どうやらマクドナルドがあることがわかった。流石にここにきてマックはないなということですんでで思いとどまり、牛カツの店に入る。念のため言っておくと、チーズ要素はない。

牛カツ。ダブルにしたらマジで多かった。おいしかった。

今日は研究室内のミーティングの日なのだが、用事のこともあって帰っても全然間に合わないので開き直ってダブル牛カツ膳を頼む。 シングルだと正直足りないかなと思い上のを頼んだのだが $ 1.5 $ 倍ぐらいのボリュームを想定していたら、しっかり原義ダブルの $ 2 $ 枚きて焦った。ちゃんとメニューを見ろよ。$ 1.5 $ 枚を想像していたので最後の半分は相当苦しかった。

胃の健康のために、施設内のベンチみたいなところで休憩をとってから帰路についた。 胃がいっぱいなのと、東京に対する疲れによって帰りの電車では疲れて爆睡していた。 日本の治安の良さに感謝しながら帰宅。

帰宅してから、作業とかスマホ弄りとかを仕様かと思ったが左手首が痛すぎて横になっていた。 気づいたら寝ていて夕食の前だったのだがワロタで済ませておいた。

食後は今日の典型を書いてきた。二次元累積和で実装するのでその幅は $ K+1 $ でなければならないところを $ K $ にしていて、サンプルが合わなくて $ 5 $ 分ぐらい無駄にした。AC。

C - 高橋君と国家 を解いた。 $ N $ 頂点 $ M $ 辺のグラフが与えられる。頂点 $ v $ を交易所にするのに $ c_v $ のコストがかかり、辺 $ i $ を整備するのに $ r_i $ のコストがかかる。全ての頂点が交易所に到達可能にするのに必要な最小のコストを求めよ、という問題。

交易所にする頂点を確定させたら、交易所を各連結成分に含む最小コストの森みたいなものを求めればいいなとか思う。 制約的に交易所にする頂点を選ぶようなアルゴリズムは無理なので頭を少し捻ると、仮想頂点を置いて、交易所にする操作を仮想頂点から各頂点への辺として考えてしまうと最小全域木問題になることがわかる。あとは書くだけで AC。仮想頂点を置くことで最小全域木になる問題、たまに見るな。

今日もサボり分の典型を処理していく。Deck（★2）

整数の書かれたをデックの上に載せる・下に入れる・上から $ k $ 番目の数字を出力する、の $ 3 $ 種類のクエリに $ Q $ 個答える問題。 マジで std::deque を使うとそのまま。

062 - Paint All（★6）

大分前の典型なので問題概要は省略。 冗談抜きで $ 30 $ 分ぐらいかかってしまった。 初手頂点 $ A_i $ と $ B_i $ を結ぶ辺を張ったグラフを考えたのだが、全然いい筋の解法が浮かばない。 よくよく考えると、$ A_i $ か $ B_i $ のどちらかが白なら $ i $ が黒に塗れるという関係は $ i \rightarrow A_i $ と $ i \rightarrow B_i $ の二辺で表せて、こっちの方が良く特徴の現れたグラフになる。これでも解けなかったので逆操作を考える。全部黒の状態で逆操作を考えると、$ i = A_i $ または $ i = B_i $ のような頂点以外は白く塗れない。これ以外の逆操作は、$ x \rightarrow y $ かつ、頂点 $ x $ は黒、$ y $ は白のような場合に頂点 $ x $ を白く塗ることができる。したがって複数始点の逆辺を辿る DFS/BFS によってすべての頂点へ到達可能なら、問題の条件を満たす。行きがけ順の逆順に出力すれば答え。

速く解けなかった理由は

• 全然うれしくないグラフへの落とし込みをしてしまった。
• 操作の前提条件が緩く、結果が明確な操作は順操作がつらく逆操作が楽がちなことを忘れていた。
  • 「遷移可能な頂点のうち少なくとも $ 1 $ つが白なら黒く塗れる」がこれに相当。
  • よくあるのだと範囲塗りつぶしみたいな操作もこれにあたる。（塗りつぶし前は任意色だが、後は一定）
  • 「$ x $ の倍数なら $ x $ で割れる」みたいなのもこれか。

就寝。ところで、探している漫画が見つからずにもやもやしていた。

07/02 (FRI)

9:30 起床。からの 11:45 起床した。最悪。

トーストを朝ごはんに食べた後、今日の典型を確認する。★3。

https://atcoder.jp/contests/typical90/tasks/typical90_cd

★3 にしては大分怠い見た目をしている。問題概要。$ L < R $ であるような正整数 $ L,R $ が与えられる。$ x \in [L,R] $ の $ x $ を $ x $ 個ずつ黒板に書いたとき、黒板に書かれている数字の数を答えよ、という問題。 数字というのはどうやら桁のようだ。

$ L,R \leq 10^{18} $ なので愚直系は全部アウト。桁ごとにやるしかなさそうだ。例えば $ 1 $ の位の寄与を考えると、 $ 1 $ 以上の整数の和になる。これ難しくないか？ 閉区間 $ [L,R] $ に対して問題を解くのは面倒なので、$ [0,X] $ の問題を解けば $ [0,R] $ の答えから $ [0,L - 1] $ の答えを引いてよし。 なぜかもうジャッジが来ているので提出して AC。

一般の閉区間や半開区間の問題を $ [0,X) $ の問題に落とすことで幾分か楽になるの多いな。

サボり分の消化。063 - Monochromatic Subgrid（★4）

問題概要は省略。こういう問題は片方の軸について固定するともう一つが簡単な問題に落ちることが多い。 制約を見ると $ H \leq 8 $ なので行についてその行を選択するかどうかを決めうつことにする。$ O(2^{H}) $ で決めうてる。 すると、各列に対して取る行について全て同じ数字でない列はそもそも選べない。 また、出現する数字が同じ列のみを同時に選択することができる。 よって std::map などによって、それぞれの出現度数をカウントしてやれば、$ O(2^{H} HW \log{W}) $ とかで解ける。AC。

昼飯を食べる。焼きカレーとかいうの最高にうまい。

064 - Uplift（★3）

問題概要省略。区間加算操作の前後での隣接差の変化は区間の端 $ 2 $ 箇所にしか現れない。これが全てだ。初期状態の「不便さ」と、隣接差（符号付）を計算しておいて、あとは端に関して隣接差と「不便さ」を更新していくだけだ。区間加算が $ 2 $ 箇所に対する操作に言い換えられることは難しめの問題でもよく出る内容な気がする。 区間加算だけじゃなくて区間 xor でも出題がある。

065 - RGB Balls 2（★7）

問題概要省略。★7 はやはり結構難しい。赤・緑・青のボールを取る数をそれぞれ $ r,g,b $ とすることによって立式することができる。

$$ \left\{ \begin{align} &r \leq R, \quad g \leq G, \quad b \leq B \quad \cdots (1) \\ &r+g \leq X, \quad g+b \leq Y, \quad b+r \leq Z \quad \cdots (2) \\ &r+g+b = K \quad \cdots (3) \end{align} \right. $$

見てすぐに $ O(K^{2}) $ の解法は思いついた。これは $ r,g,b $ の内 $ 2 $ つを決めうつことによって、式 $ (3) $ によって残り $ 1 $ つも確定する。その $ r,g,b $ が上の全ての式の条件を満たすかチェックして、満たしていたら $ \binom{R}{r} \binom{G}{g} \binom{B}{b} $ だけ答えに寄与させれば良い。

当然この問題の制約では $ 2 $ 乗は間に合わないので、工夫が必要。 $ 2 $ 色のボールに関する不等式制約がかなり煩わしいと思う。グッと睨むと $ (3) $ を使うと $ 1 $ 色のボールの制約にすることが出来ることに気が付く。これを整理すると、

$$ \left\{ \begin{align} &K - Y \leq r \leq R \quad \cdots (4) \\ &K - Z \leq g \leq G \quad \cdots (5) \\ &K - X \leq b \leq B \quad \cdots (6) \end{align} \right. $$

のような制約が得られて、これはかなり分かり易い。$ r $ を決めうってみる。この時に $ g + b = K - r $ であるような場合の数が高速に求められれば解ける。 式 $ (5),(6) $ に注意しながら、有効な $ b,g $ について、$ \binom{G}{g} $ や $ \binom{B}{b} $ の配列を構成すれば、その畳み込みをすれば欲しいものが手に入る。FFT を使えば $ O(K \log K) $ でできる。結局ボトルネックも FFT なので、この計算量で解けた。AC。

目的意識を持って、一直線に式を変形するの難しいな。今回は $ 2 $ 変数に関する条件を $ 1 $ 変数に関する条件に変形可能。 こういうのはどこまで行っても ad-hoc になってしまうため、変形の目的と実際の変形のパターンの引き出しをたくさん持っておくのが良い気がする。

あといい加減自分の FFT を作ろうかなと思うんだけど、FFT は定数倍が結構センシティブな気がしていてなかなか… ところで 059 - Many Graph Queries（★7） の想定解について触れる。 想定は、隣接行列を更新していくのではなくクエリを $ 64 $ 個ずつ処理するものだった。背景としては、到達可能性の配列は $ bool $ 型の配列なのでワードサイズの $ 64 $ クエリまで重ね合わせることで速くなるというやつだ。こちらは MLE が気にならないので賢い。

066 - Various Arrays（★5）

問題概要は省略。全ての $ i < j $ を満たす $ (i,j) $ について、$ A_i > A_j $ であるような確率を足し上げた者が答え。 いわゆる期待値の線形性とか、主客転倒とか言われているテクニックな気がする。 期待値の問題は期待値の線形性を利用しない問題はほぼないのではなかろうか。 ちなみに上の実装を完全に全探索で行っても $ O(N^{4}) $ で間に合う。ちょっと工夫をすると $ O(N^{3}) $ になって、頑張ると $ O(N^{2}) $ になると思うが、出題側も主客転倒が問いたいだけなので非本質ということなのだろう。

連続して消化作業をやっているように見えるが、途中に TA 業務やゼミが挟まっている。 TA といえば今週は $ 2 $ 人も質問に来た。心なしか他の TA にも普段より質問が来ているように感じた。 今回の Java の講義内容がテストとラムダに関する内容だった。 学部生ということもあって、テストがどういうものかわかっていなくて混乱するみたいなケースが多そうと感じた。 研究室に来るまでにはちゃんとわかっていて欲しいと思うレベルの解説をした。説明うざいと思われていたら立ち直れない。 壊れている素数判定関数の単体テストを書くみたいな課題が出ていて、最低 $ 2 $ つのテストメソッドを書けとのこと。 何をどうテストしていいのかわからず、正しい素数判定をして $ 1 $ から $ 100 $ までの整数で比較するみたいなメソッドを書いて、もう $ 1 $ つ何を書けばいいのかわからない、とかそれに近しい質問が $ 2 $ つだった。 気持ちはわかるが、その「正しい素数判定」が正しいということを保証をしてくれるものがないので、テストとして不適切ということを言って、こういうのはシナリオ別に分けてメソッドを記述するからこの場合最低でも素数と非素数の $ 2 $ つのテストが必要で、その入力と出力に関しては人間が計算・判断したものを入れる、と言ったら納得してくれた（と思う）。まあ正しくはこれはブラックボックステストなのだが、ブラックボックステストとホワイトボックステストの話まで始めたら流石に嫌われると思ったのでやめた。

典型の消化作業続行。067 - Base 8 to 9（★2）

$ 8 $ 進数 $ \rightarrow $ $ 10 $ 進数 $ rightarrow $ $ 9 $ 進数をする関数を定義して、$ K $ 回実行する。 投げると $ 1 $ ケース落ちるのでよく見ると入力に $ 0 $ があるので、$ 0 $ の時に空にならないように直すと通る。 この手のの問題で $ 0 $ があるの本当に不愉快だな。悪口ではなく負け惜しみです。

食後に yukicoder contest 302 - yukicoder があるので出る。

A 問題。最初指数結合法則が足し算だと思っていた（腦）。冷静になると掛け算で、デカいな～と思いながら $ \mod 10^{9}+6 $ を取ってやってから二分累乗をする。

B 問題。この問題難しい！$ (0,0) $ が負け、から遷移を書いたり思い浮かべたりしてガチャガチャ弄っていると証明できそうな構造が見つかる。証明出来て投げる。コーディングミスで 1 WA もらう。

C 問題。最初に与えられた整数の $ \mod 10^{9}+7 $ を求めて $ S $ とする。 $ S $ 以下で $ A^{n} $ 以上の数字の数が $ \left \lfloor \log _ {A} k \right \rfloor \geq n $ を満たす $ k \in [1,S] $ の数。 よって $ 1 \leq n \leq \left \lfloor \log _ {A} B \right \rfloor $ について $ S - A^{n} + 1 $ を足し上げる。

D 問題。一目で $ 2 $ 乗の DP は思いつく。$ dp[i][j] $ : 和が $ i $ で初項 $ j $ の倍数でなければならないような条件を満たす列の数、とする。$ i $ の約数しか遷移が進まないので、遷移を含めた計算量が $ O(M^{2} \log M) $ になる。よく考えると、$ i $ の約数にしか遷移しないので、$ i $ と $ j $ を $ \gcd(i, j) $ で割っても結果が同じことを利用して $ j=1 $ の状態のみを考えることができ、結果状態数が $ O(M) $ になるので、$ O(M \log M) $ で解けた。

E 問題。最初 sample だけを見て、何も考えずに $ 2 $ - 彩色をして少ない方の数を提出した。WA。それはそう。 よくよく考えると解の下界は最小店被覆である。 そして、これは後手が黒く塗りたい頂点以外を優先的に白く塗ることによって達成可能。

FG 問題。前半に時間を使いすぎて考える時間がなかった。復習する。

A はマジで早く解けなきゃいけなかった。というかこれは知っているだろ… B は初手実験を選べなかったのがかなり痛い。これ帰納的じゃなくいい感じに導けるのかな？ C も $ 10 $ 進数ではよく問われる問題なのにまごまごして良くなかった。 D は多分こんなもんだけど、スタックオーバーフローなのか手元では Runtime Error ぽかった。 こんな時、minGW くんはうんともすんとも言わないので本当にゴミ。 WSL 環境にした方が絶対にいいなと思う瞬間である。 E は適当をやっている時間がもったいない。あとはトチ狂って Dinic 法で解いたが木の最大マッチングは 木 DP で高速に書けるようにしたいね。

ここら辺の問題を高速に処理できるかどうかが、今の自分の競プロで大切なことな気がする。 明日はワクチン接種なので早めに就寝。

07/03 (SAT)

9:30 起床。今日はコロナのワクチンを打ちに行く。

典型を確認する。

https://atcoder.jp/contests/typical90/tasks/typical90_ce

問題概要。$ N $ 頂点 $ M $ 辺の単純無向グラフが与えられる。$ Q $ 個の以下のようなクエリが与えられるので順番に答える。

• 頂点 $ x $ の色を出力する。その後頂点 $ x $ とその隣接する頂点を色 $ y $ で塗る。

難しいぜ。クエリ平方分割が脳裏によぎったが面倒すぎるし、かなり計算量が怪しいので実装する気が起きなかった。 途中インキチ解法を思いついたが当然のように嘘だったので、泣いていた。

さて、ワクチン接種の時間が近づいてきたので支度をして三田キャンパスに向かう。 田町駅で降りて、初手方向を間違えた。ちなみに Google Map を見ていたのに間違えたので本当に人間になりたい。

キャンパスに着くと、ワクチン接種の列ができている。 サークルの後輩がすぐ前にいたので退屈しなかった。最も、退屈するほどの時間待つこともなかったが。 長い列のように感じたわりにすぐワクチンを接種できる。筋肉注射は初めてだったので怯えていたんだけど、マジで何も感じなかった。 電車のシートの隣にマッドサイエンティストが居てヤバイウイルスを筋肉注射されても多分気づかないぐらいには何も感じなかった。

↓はめちゃくちゃ焦っている時のツイート。ちなみにしびれはすぐに取れた。

おワクワク摂取終わった
なんか打った腕の前腕が痺れ始めたんやけど…

— むかで (@cloudman_P) July 3, 2021

接種が終わった後に後輩と一緒に三田製麺所で昼食をとった。

三田製麵所。久々につけ麺を食べたのでよう沁みた。

昼食の後は、日吉に行った。ゲームもした。帰宅。 コドフォも今日はあるのだが、接種直後なので遠慮しておいた。 就寝。

07/04 (SUN)

11:00 起床。なんだか、副反応ぽかったので念のためゴロゴロしていた。 散々ゴロゴロした後に、熱っぽかったら一応家族に報告の必要があるなと思って体温計を持ってきて測ったら $ 38.4 $ 度だった。 普通に熱があってワロタ。元気いっぱいだったので。確かに少しボーっとしていたけど、低気圧のせいだと思っていた。

そんなわけで ABC の時間まで本当にゴロゴロしていた。AtCoder Beginner Contest 208 - AtCoder に出る。 後で出たことを後悔することになる。

A 問題。$ A \leq B \leq 6A $ なら "Yes"。

B 問題。こういう場合は大きい硬貨からの貪欲で良い。もっとキツイ条件でも貪欲が適用できるが、まあ今回はいいだろ。

C 問題。満遍なく配る問題。$ a_i $ が小さい順に国民をソートして最初の $ K' $ 人に $ +1 $ 個キャンディを配ればいい。

D 問題。数え上げるものをよく睨む。$ k $ が小さい順に計算して $ 1 $ 頂点ずつ経由点を増やしながら計算することを考える。ワーシャルフロイド法と完全に一致しているので、ワーシャルフロイド法の過程の要素を足し合わせればよい。

E 問題。落とした。今思えば普通に熱のせいで脳が多少不調だったのかもしれない。いや、そうであってくれ。 $ 10 $ 未満の積ということには一瞬で気づく。次の瞬間に $ 2,3,5,7 $ しか素因数がないことに気づく。TDPC のサイコロ？みたいな問題と似たような感じで素因数の数を状態に持っていれば解ける気がする。次元の数がすごいことになる。設計をかなりミスっていて、あれこれやって雑に次元とかを増やしまくった結果、TLE と相成った。結局落とした。最悪。

とは言え、最近方針一瞬だけど実装が結構嫌だなみたいな問題が ABC で出題されるようになってきた気がする。

F 問題。読んでない。

またレーティングをちゃんと下げた。最悪だけど、今回は副反応中に出た自分に責任があり、涙…。

今週は悲しみの内に終了。