atcoder.jp 問題文を言い換えます。""" 最初は頂点１と頂点Nにコマが一つずつ置かれています。一回の行動で、２つのコマを辺を使って同時に移動させます。ただし、どちらも同じアルファベットのかかれた辺を使う必要があります。 """ここがわかればもう解け…

公式の解説に載ってなかったので。atcoder.jp まず、優先度つきキューなどに、配列Aに含まれていない要素（MEXになりうる数）を入れます。優先度つきキューは、入っている要素の中の最小値を高速で取り出すことができるので、これでMEXを高速で求めることが…

F問題あともうひと押し…atcoder.jp A問題 Print 341 1010.....1みたいに出力すればいいです。 n=int(input()) for i in range(n): print("10",end='') print("1") B問題 Foreign Exchange それぞれの国で両替をできるだけ行うという貪欲で解けます。 n=int(i…

Robot Rotation atcoder.jpまず、全探索を考えます。 単純なBit全探索だと、入力が最大の時に計算量が2^80になってしまい、間に合わないので工夫する必要があります。まず、行動をする時に向くことができる方向が右と左の２つだけなので、配列Aのうち、奇数…

重みつきUnionFindは、UnionFind木を理解していればあっという間に実装できます。と、言うのも、UnionFind木で親をたどっていく操作の途中で、重みも一緒に計算すればいいだけだからです。ホントにそれだけです。添字がめんどくさいぐらい。 #include <bits/stdc++.h> using</bits/stdc++.h>…

任意の非負整数Nの約数を求めたい場合、愚直な実装をすると１からNまでの数字すべてがNの約数かどうかを確認することになると思います。 #include <bits/stdc++.h> using namespace std; int main() { int n; cin >> n; vector<int>ans; for (int i=1;i<=n;i++)if(n%i==0)ans.emp</int></bits/stdc++.h>…

atcoder.jp４つに場合分けできる ・町１から町Nまで未定のテレポーターを使わないで行く。 ・町１から近い未定のテレポーターまで行き、町iから未定のテレポーターを使わないで町Nまでいく。 ・町１から町iまで行き、未定のテレポーターにテレポートした後、…

備忘録最小全域木は、重み付きグラフなどにおいて、連結なグラフにするために最小で重みがいくつになるかです（日本語変かも）。大きくクラスカル法とプリム法がありますが、ぼくはプリム法の方で実装しました（一般的にはクラスカル法のほうがシンプルなの…

DFSは、ある頂点が他の頂点と連結してるかどうかを確認するアルゴリズムです（頂点１からスタートした場合、それぞれの頂点が頂点１と連結かどうか確認できる）。BFSの下位互換でしかないので、めったに使わないです。rotti-coder.hatenablog.comまあ、たま…

BFSは幅優先探索と言って、まあだいたいグラフが連結かどうかだったり、ある頂点から初めてその頂点には何通りの行き方があるかとか、最小で何手である頂点からある頂点まで行けるかを確かめたりするのに使います（他にもたくさん使いみちあるけど）。 実装 …

lowlinkの実装 lowlinkというのは、例えば連結なグラフがあった場合、どこの頂点やどこの辺をなくすと連結じゃなくなるかを確認する方法です。 なくなると連結じゃなくなる頂点を関節、辺を橋といいます。備忘録。 まず実装 int lowlink(int n,int m, vector<vector<int></vector<int>…