2022年に見たアニメ

一応このブログは雑記を書く場所なんだけど、ほとんど競プロの自己満足解説記事になっているので、たまには箸休めとしてこういうのもいいかなと思って。年末だし、後になって読み返すと面白い気もしますしね。ネタバレは書いてません。

それでは行きましょう

2022年より前に放送されてみたアニメ

• ウィッチクラフトワークス★
  • めっちゃよかった。魔法使い最高
• 魔法使いの嫁　★★★
  • これもすごく良かった。魔法と魔術の違いを語るシーンすごい好き
• 無職転生　★★★
  • 王道ファンタジーって感じですごいよかった

2022年に放送されてみたアニメ

このページから探してます。全部見たやつだけ載せます

ja.wikipedia.org

• 悪役令嬢なのでラスボスを飼ってみました
• 阿波連さんははかれない
  • とてもよかった。
• 異世界迷宮でハーレムを
• 異世界薬局
  • 当社比でちゃんと薬局して面白かった
• 宇崎ちゃんは遊びたいω
• うる星やつら
• Engage Kiss
  • 個人的にはリコリコよりこっちの方が熱かった
• かぐや様は告らせたい-ウルトラロマンティック-
• カッコウの許嫁
• からかい上手の高木さん3
  • 最高でした
• 可愛いだけじゃない式守さん
  • OPがめちゃくちゃおしゃれでサイコー
• 古見さんは、コミュ症です。
  • EDが最高でした。
• 最近雇ったメイドが怪しい
• SPY×FAMILY
• その着せ替え人形は恋をする
• それでも歩は寄せてくる
• 盾の勇者の成り上がり
  • これも最高でした
• ダンジョンに出会いを求めるのは間違っているだろうかIV 新章 迷宮篇
• であいもん
  • これも最高でした。京都行きたくなった。関西戻りたい
• デート・ア・ライブIV
• 天才王子の赤字国家再生術★
  • これすごい面白かった。政治とか帝王学とかは全く教養がないけど、主人公がとにかくうまく立ち回っている感じがとてもよかった。
• パリピ孔明
  • これもすごくおもしろかった
• 夫婦以上、恋人未満★
  • 最高。好きなタイプの妄想
• BLEACH 千年血戦編
  • 面白すぎる
• 平家物語★
  • これ本当に最高でした。2022年度TOP5入り。
• ぼっち・ざ・ろっく！
• まちカドまぞく２丁目
  • 毎度平和で大変良かった
• よふかしのうた★
  • これ本当に最高でした。はまりすぎてこの時期は毎日よふかししてた。
• 理系が恋に落ちたので証明してみた　r = 1-sinΘ
  • クラスカル法とプリム法がでてきたのが印象深い
• リコリス・リコイル
• 恋愛フロップス
  • フロップスってそういうこと？

2023年もよろしく！

AtCoderの問題300日続けてみた

はじめに

この記事はNAIST Advent Calendar 2022 の 18日目 AtCoder problemsで300日ストリークを続けてみた　の記事です。

みなさんプログラムを書いてますか？

毎日なにかしらプログラムを書いていたいタイプなんですが、実際のところは調べる時間が必要だったり、そもそもプログラムを書く必要があるのか考える時間も必要だったするもので、毎日エディタに何かを打ち込むことはなかなかなありません。

それでもなんとかしたいなというわけで、とりあえず競プロの問題を1日1問とこうという事になり、なんやかんや300日を超えました。

大学院で修論の炎上を鎮火したあたりから、毎日1問以上競プロの問題をといてます、数字でみるとこんな感じ。

解いた問題のdifficulutyは上の用な感じ。結構灰色で埋めてます。もうちょい緑色とか水色の割合を増やしたいところ。

ストリークのすすめ

名目はすすめとなっていますが、実際のところ万人におすすめできるかというと微妙なところです。誰かにアピール出来るほどの説得力を持たないものだと自分は考えています。

それでも、山のようにある問題を少しずつ埋めていくのは小さな達成感があります。1日1問解くだけなので、言語を縛る必要もありません。ぼくはGoとPythonを少しずつ使い始めています。Pythonは速度をきにしないならサクッとかけていいですね。

もっと自由にプログラムを書くプロセスを楽しみたい方、ストリークをつなぐのはおすすめです

宣伝

300日を続けてると全く解けない問題と戦うことがあります。WAが10回ぐらい続くと心が折れてきます。しまいには

• この問題のジャッジ壊れてるんじゃないか？
• 俺だけが本当に正しい解を書いていて自分以外が間違ってる可能性かこれ？
• ジャッジサーバーのコンパイラ壊れてませんか？

みたいな気持ちになることがあります。残念ですが上記の可能性はゼロです。あなたが間違っています。

別に間違いたくて間違っているわけじゃないんですよね。全くわからないならまだしも、自分が考え方のどこが間違っているかわからない状態は想像以上に大変です。

僕は上記の沼にハマったときはNAISTプロコンサークルに問題を投げて助けてもらってます。

構文解析が全くわからず1週間ぐらい沼ってときの写真

競プロは一人で黙々と取り組めるものですが、モチベの維持が大変です。特に気分が落ち込んだ時とか、理由もなくやる気が無くなった時に復帰するのが難しいですよね。個人の感想ですが。プロコンサークルはそのあたり定期的にサークル内バチャコンが開かれており、ハートビートに最適です。

NAIST在校生(これから入ろうとしている方も)の方で競プロに関心がある方は、NAISTプロコンサークルの加入をぜひよろしくおねがいします。

僕はすでにOBという立場ですが、わからない問題を投げると誰かが答えてくれます。僕が答えることもありますし、上記の通り僕以外の誰かが答えてくれることもあります。

最後にびっくりニュースですが、NAISTプロコンサークルは現在NAISTの学内公認サークルへと昇格の手続き中です🎉

手続き中なのでまだ時期尚早かもしれませんが、これで(非公式)という文言が消えて就活のときに言い訳する必要もなくなりますね！

上記の手続きは、@koki_ さんがリーダーシップを持って取り組んでくれています。謝謝。

競プロサークルへの参加（と言っても現状Slackに参加するだけです）も彼にお願いするのが最も近道です。もちろん僕のブログ/Github/twitterに直接連絡を取っていただいても構いません。

最後に

AtCoder Problemsは 宇宙ツイッタラーXさんによって運営されているサービスです。

このサービスなしでは、300日のストリークをつなげることは不可能でした。そもそもストリークという概念事態がなくなるのでそれはそうというところです。

きっと競プロも辞めていたことでしょう。末筆にはなりますが、AtCoder ProblemsとAtCoderにに関わっているみなさんに大きな感謝を!!

明日は @izmyonさんの記事で JAXかDiffusion Modelについてです。Diffusionは巷で話題なので、それに関連するものか気になりますね👀

 

E - Through Path

これは好きなタイプの問題でした。かなり。

問題

頂点の木が与えられる。以下のクエリを処理したのち、各頂点の情報を出力せよ。

のとき : 頂点 から辺をたどって頂点 を通らずに到達できるような全ての頂点 に対して、をに書き換える。

のとき : 頂点 から辺をたどって頂点 を通らずに到達できるような全ての頂点 に対して、をに書き換える。

解法

クエリ毎に木を舐めていると当然間に合わない。各クエリを高速に処理するか、工夫して最後にうまく答えるかどちらかを考えてみる。今回は後者になる。LCAも解けそうだけど、今回は使いません（ライブラリ持ってないし…）

クエリには２種類あるがどちらもほとんど同じなので、以下では次のクエリを例として考える。

頂点 から辺をたどって頂点 を通らずに到達できるような全ての頂点 に対して、をに書き換える。

木の性質から、任意の二頂点の最短パスは一意に定まる。これを踏まえてクエリについて考えてみる。
から辺をたどって頂点を通らずに到達できるような頂点とは、直観的には、から見てと同じ側にある頂点、つまり、となる頂点の集合としたとき、となるような頂点集合である。この頂点にだけ値を追加すればよい。どうやって値を追加していくは最後に答えるとして、もう少し詳細を見てみよう。

上記の考察から、クエリ毎に値が変化する頂点の集合が二つに分かれることに気づく。さらに、その分け方は、適当な頂点を根とした木の距離を計算しておけば楽に導出できる。
この部分も少し補足しておこう、を満たすとき、つまり、根から見たときがより深いとき、　となる頂点がとなる。言い換えると、値が追加される頂点の集合は
逆にとなるとき、値が追加される集合()は、と、から親方向にたどってまでに到達するまでに存在する頂点であることがわかる。今回は隣接する頂点なので、値が追加される集合はだけ。

最後に値を追加する方法を考えよう。今までの考察から、どのクエリであっても、根から距離を基準として、その頂点の親と子供を見ればよいことがわかる。発想を変えてみて、クエリによって値を追加するとき、とりあえずすべての頂点に値を追加して、対象外の頂点だけに値を引いてみることを考えよう。

言い換えると、値を追加するとき、全体に追加するのであれば根に、木の子供に追加するなら親に値を追加すればよい。これと同じように、値を引くとき、負の値を親に追加すればよい。クエリをすべて処理した後、一度だけ深さ優先探索を行えば、整合性が取れた木が完成する。遅延評価っぽい戦略が見えると、比較的楽に取り組める。

提出

#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>

using namespace std;
using Int  = long long;

void dfs(vector<vector<int>>&edge, vector<Int>&d, int v, int pv = -1)
{
    for(auto& nv : edge[v])
    {
        if(nv == pv)continue;
        d[nv] = d[v] + 1;
        dfs(edge,d,nv,v);
    }
    
    return;
}

void flush(vector<vector<int>>&edge, vector<Int>&d, vector<Int>&c, int v, int pv = -1)
{
    for(auto& nv : edge[v])
    {
        if( nv == pv) continue;
        c[nv] += c[v];
        flush(edge,d,c,nv,v);
    }
  return;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
  
    int N; cin >> N;
    vector<vector<int>>edge(N);
    vector<pair<int,int>>input;
    
    for(int i = 0; i + 1 < N; ++i)
    {
        int a,b;
        cin >> a >> b;
        --a; --b;
        edge[a].push_back(b);
        edge[b].push_back(a);
        input.emplace_back(a,b);
    }
    
    vector<Int>c(N,0LL);
    vector<Int>d(N,0LL);
    
    dfs(edge,d,0);
    
    int Q; cin >> Q;

    while( Q --> 0)
    {
        int t, e, x;
        cin >> t >> e >> x;

        --e;
        
        int pls, mns;
        
        if( t == 1)
        {
            pls = input[e].first;
            mns = input[e].second;
        }
        else
        {
            mns = input[e].first;
            pls = input[e].second;
        }
        
        if(d[pls] > d[mns])
        {
            c[pls] += x;
        }
        else
        {
            c[mns] -= x;
            c[0] += x;
        }
    }
    
    flush(edge,d,c,0);
    
    for(auto e : c)
        cout <<  e << endl;
    
}

E - Traveler

問題

個のボールが与えられる。ボールは、座標軸上に位置し、その色はである。
座標軸を移動しながらボールの色が広義単調増加となるように回収する時、移動するコストを最小化せよ。
atcoder.jp

考察

色ごとにDPしたくなるが、各色と次の色の間ですべての推移を試すのは容易ではない。これは実際に推移する辺を貼ってみると、辺の数が非常に大きくなることからわかる。

そこで、同じ色のボールを回収する方法について試してみる。同じ色のボールを回収する始点と終点をうまく決めることができれば、推移の数を減らせるだろう。

となる同じ色のボールを考える
　とおく。また、をAからBまでの距離を表すものとする。

まずは始点、終点がともに端点である場合を考えると、　である。

つまり、同じ色のボールについて、端点(最小の座標軸にある点）から端点までボールを回収する場合は、途中で戻る必要がないため上記の式のようになる。

では、端点以外の点(例えば, )の場合を考えてみよう。を始点して、最初にのボールを回収すると
となる。このような感じで、端点以外の頂点を始点とすると、端点から端点に移動する場合に比べてコストがかかることがわかる。

言い換えると、ボールを回収する最も効率的な動き方端点から端点で、そのコストはである

これより、各色のボールについて、端点から次のボールの色の端点に移動する場合を動的計画法で探索すれば良い。
色として、各端点をとするとを試して最小値を取れば良い。

解法

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>

using Int = long long;
using namespace std;

int main()
{
    cin.tie(nullptr);
    ios_base::sync_with_stdio(false);
    
    int N; cin >> N;
    map<Int,vector<Int>>mp;
    
    for(int i = 0; i < N; ++i)
    {
        Int x,c;
        cin >> x >> c;
        mp[c].push_back(x);
    }

    map<Int,Int>cnt;
    for(auto& itr : mp)
    {
        sort(itr.second.begin(),itr.second.end());
        Int prev = itr.second.front();
        for (const auto e : itr.second)
        {
            cnt[itr.first] += abs(e - prev);
            prev = e;
        }
    }
    vector<vector<Int>>dp(2, vector<Int>(mp.size(), 0LL));
    
    Int l = 0,r = 0;
    int i = 0;
    
    for(auto& itr : mp)
    {
        Int nl = itr.second.front();
        Int nr = itr.second.back();
        
        if(i)
        {
            dp[1][i] = min(dp[0][i - 1] + abs(nl - l), dp[1][i - 1] + abs(nl - r)) + cnt[itr.first];
            dp[0][i] = min(dp[1][i - 1] + abs(nr - r), dp[0][i - 1] + abs(nr - l)) + cnt[itr.first];
        }
        else
        {
            dp[1][i] = min(abs(nl - l), abs(nl - r)) + cnt[itr.first];
            dp[0][i] = min(abs(nr - r), abs(nr - l)) + cnt[itr.first];
        }
        
        l = nl;
        r = nr;
        
        if(i + 1 == mp.size())
        {
            dp[1][i] += abs(itr.second.back());
            dp[0][i] += abs(itr.second.front());
        }
        ++i;
    }
    
    cout << min(dp[0].back(), dp[1].back()) << endl;
}

E - Prefix Equality

11月一度もブログ投稿してないけど、問題自他はこまめに解いてました。
思い出すシリーズです。

問題

長さの2つの数列が与えられる。
個のクエリに答えよ。

: の先頭個の値の集合との先頭個の値の集合が等しいかどうかを答えよ
atcoder.jp

解法

• クエリにオンラインで答える必要は無いので、まずはクエリの内容をの昇順に並び替える。これによって、の状態をクエリごとに求めずにすむ。
• さて、ここからクエリに答える具体的な方法を考察してみる。まずは簡単なところから考えよう。それぞれの値の集合を, とする。もし値の集合が等しいのであれば、明らかにが成り立つ。
• もちろんすべてのクエリに対して集合を計算するのは間に合わないので、累積和を用いて、番目の要素までの集合のサイズを前計算しておけば良い
• さて、ここからが重要になる。集合のサイズが等しくても、集合の要素が等しいことにはならない。もう1つ条件を加えて、集合の要素も判定できるように工夫する。考えるべき点は、内の要素が、 内でどこでは初めて現れるかがである。
• 具体例を用いる。というクエリにおいて、の要素がすべてまでに現れていれば良い。余計なのもが含まれてはならないが、これは先述した集合のサイズの比較で判別できる。
• ここまで考察できれば、答えは近い。Aの集合の要素がまでに現れているかどうかの判定は、に含まれている要素のうち、の中で最も後ろに含まれている添字を更新して管理すればよい。
• 言い換えると、集合のサイズが等しい　かつ　Aの集合の要素の中でB中に最も後に現れる添字を管理することで、集合の要素を判定することができる

• 文字にすると微妙なので具体例も載せよう。 = の時, = とすれば、５番目の添字を覚えて置けば良い。

提出コード

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <queue>
#include <algorithm>
#include <set>

using namespace std;
using Int = long long;

int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N;
    cin >> N ;
    
    vector<int>A(N), B(N);
    
    for(auto& a : A)
        cin >> a;
    
    for(auto& b : B)
        cin >> b;
    
    vector<tuple<int,int,int>>query;
    
    int Q; cin >> Q;
    
    for(int i = 0; i < Q; ++i)
    {
        int x, y;
        cin >> x >> y;
        query.emplace_back(--x,--y, i);
    }
    
    sort(begin(query),end(query));
    
    vector<bool>ans(Q, false);
    
    int cx = 0;
    set<int>S, Sb;
    
    vector<int>bSetSizeCnt(N, 0);
    map<int,int>bKeyIdx;
    
    for(int i = 0; i < N; ++i)
    {
        // 各要素で最初に現れる位置を記録する
        if(bKeyIdx.find(B[i]) == bKeyIdx.end())
            bKeyIdx[B[i]] = i;
         // Bの集合のサイズを記録する 
        if(i)
            bSetSizeCnt[i] += bSetSizeCnt[i - 1];
        
        if(Sb.find(B[i]) == Sb.end())
        {
            bSetSizeCnt[i] += 1;
        }
        
        Sb.insert(B[i]);      
    }
  
    int aIdxMaxi = -1;
    for(const auto&[ x, y, i] : query)
    {
        while(cx <= x && cx < N)
        {
            S.insert(A[cx]);
            // Aにだけある場合はこれ以降すべてのクエリがNo
            if(bKeyIdx.find(A[cx]) == bKeyIdx.end())
                aIdxMaxi = N + 1;
    
            aIdxMaxi = max(aIdxMaxi, bKeyIdx[A[cx]]);
            ++cx;
        }
        if(S.size() == bSetSizeCnt[y])
        {
            if(aIdxMaxi <= y)
                ans[i] = true;
        }
    }
    
    for(const auto b : ans)
        cout << ( b ? "Yes\n" : "No\n");
    
}

C - Mandarin Orange

問題

個の数列が与えられる. を求めよ.

atcoder.jp

解法

問題文から上記の言い換えは比較的容易.後はこれを埋めて行けば良い.
これが茶diffと聞いてインフレもここまで来たか…と思ったが、実際は通るらしい.

これでは面白く無いので、解法を考えてみよう.

区間の両端を決めるのは難しい.　区間の片方を固定する　あるいは、数列の値が最小値となる区間を導出するといった方法が考えられる.

今回は後者を使う.

さて、ある値が最小値となる区間を求めようと思うと、　となる を探し出せば良い.も同様なので割愛する.
これを求めるには、をソートしておき、先頭から値を順番に舐めて、その添字の情報を保存しておけば良い.なぜなら、が最小値となる区間は、より小さい値を持つ要素の添字から導出できる.探索済みの配列の添字を高速に探索には、std::setなどの二分探索を用いれば良い.
計算量は.

提出

#include <bits/stdc++.h>

using namespace std;

using Int  = long long;

int main()
{
    Int N; cin >> N;
    vector<pair<Int,Int>>v;
    
    set<Int>rIdx,lIdx;
    
    Int ans = 0;
    
    for(Int i = 0; i < N; ++i)
    {
        Int t; cin >> t;
        v.emplace_back(t,i);
    }
    sort(v.begin(),v.end());
    
    for(int i = 0; i < N; ++i)
    {
        const auto [val,idx] = v[i];
        
        auto itr = rIdx.upper_bound(idx);
        auto it2 = lIdx.upper_bound(-idx);
        
        Int r = -1, l = -1;
        
        if(itr == rIdx.end())
            r = N;
        else
            r = *itr;
        
        if( it2 == lIdx.end())
            l = 0;
        else
            l = abs(*it2) + 1;
        
        ans = max(ans, (r - l) * val);
        
        rIdx.emplace(idx);
        lIdx.emplace(-idx);
    }
    
    cout << ans << endl;
}

F - Well-defined Path Queries on a Namori

問題

頂点辺の連結な単純無効グラフが与えられる。グラフ上の頂点に向かう単純パスが一意に定まるか判定せよ

atcoder.jp

解法

頂点辺というのがポイント。辺の数がだった場合、任意の二つの頂点を結ぶ単純パスは一意に定まる。言い換えると、この場合は木になる。

これより、今回の辺の数では、ちょうど一つの閉路が存在することがわかる。

このままでは考えにくいので、閉路を一つの頂点とみなして考えてみる。このグラフをとする。
は木なので、上の二つの頂点を結ぶ単純パスは一意に定まる。

ただし、単純パス内に閉路を一つにまとめた頂点（縮約してできた頂点）を経由した場合は、元のグラフで一意に定まらない場合がある。
便宜上、この頂点をとする。

これに注意して考察を進めると、以下の場合分けが必要になる。
1. がを経由しないとき、一意に定まる
2. がの頂点をただ一つだけ経由するとき、一意に定まる
3. がの頂点を二つ以上経由するとき、一意に定まらない.

実装では、　上の各頂点を親として、閉路内に含まれない各頂点を探索し記録することで、経由するかしないかを判定している。あえてサイクル上の頂点から探索することで、経由しない場合でもうまく対応しているのがポイント。

以下公式の解説より

今回の問題は N 頂点, N 辺の連結グラフでしたが, 実は一般のグラフ (非連結, 非単純の場合も含む) の場合でも N 頂点 M 辺のグラフにおいて 前計算 O(N+M) 時間, 1クエリあたり O(1) 時間で判定できる必要十分条件がわかっています. 私が作成した問題ですが, 興味のあるかたはぜひ解いてみてください.

すごい。

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <numeric>

using namespace std;
using Int = long long;

vector<int> cycle;
bool valid = true;

void dfs(vector<vector<int>>&edge, vector<int>&in,vector<int>&path, int v, int prev = -1)
{
    if( not valid) return;
    in[v] += 1;
    path.push_back(v);
    
    if(in[v] == 2)
    {
        cycle.push_back(v);
        
        for(auto itr = next( path.rbegin() ); itr != path.rend() && *itr != v; ++itr)
        {
            cycle.push_back(*itr);
        }
        reverse(cycle.begin(),cycle.end());
        valid = false;
        return;
    }
    for (auto nv : edge[v])
    {
        if ( nv == prev) continue;
        dfs(edge,in,path,nv, v);
    }
    
    in[v] -= 1;
    path.pop_back();
    return;
}
class unionfind {
    vector<int> par, rank, size_;
public:
    unionfind(int n) :par(n), rank(n), size_(n, 1) {
        iota(par.begin(),par.end(), 0);
    }
    int find(int x) {
        if (par[x] == x)return x;
        return par[x] = find(par[x]);
    }
    void unite(int x, int y) {
        x = find(x), y = find(y);
        if (x == y)return;
        if (rank[x] < rank[y])swap(x, y);
        par[y] = x;
        size_[x] += size_[y];
        if (rank[x] == rank[y])rank[x]++;
    }
    bool same(int x, int y) {
        return find(x) == find(y);
    }
    int size(int x) {
        return size_[find(x)];
    }
};



int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int N; cin >> N;
    vector<vector<int>>edge(N);
    
    for ( int i = 0; i < N; ++i)
    {
        int u,v; cin >> u >> v;
        --u; --v;
        edge[u].push_back(v);
        edge[v].push_back(u);
    }
    vector<int>in(N,0),path;
  
    dfs(edge,in,path,0);
    
    unionfind uf( N + 1 );
    map<int,int>inCycle;
    
    for(auto v : cycle)
        inCycle[v]  += 1;
    
    for(int v = 0; v < N; ++v)
    {
        for(auto nv : edge[v])
        {
            if( inCycle[nv]) continue;
            uf.unite(v,nv);
        }
    }
    
    
    
    int Q; cin >> Q;

    while (Q --> 0)
    {
        int x,y; cin >> x >> y;
        --x; --y;
        cout <<  (uf.same(x,y) ? "Yes" : "No") << endl;
        
    }
}