[AtCoder] 三井住友信託銀行プログラミングコンテスト2019 C – 100 to 105
動的計画法を行い、\( X \) を作れるかどうかを調べます。\( i \) 円が作れるとき、\( i + 100 \) 円も作れるというような方針で実装します。
コード#include <bits/stdc++. ...
[AtCoder] Educational DP Contest G – Longest Path
トポロジカルソートを利用するみたいです。
コード#include <bits/stdc++.h>using namespace std;typedef long long ll;int main() { in ...
[AtCoder] Educational DP Contest F – LCS
いわゆる最長共通部分列問題ですね。有名なアルゴリズムなので、ググりましょう。
コード#include <bits/stdc++.h>using namespace std;typedef long long ...
[AtCoder] GigaCode 2019 D – 家の建設
二次元の累積和を利用して解きます。二次元の累積和を利用することで長方形の領域で表される土地の地価の和を \( O(1) \) で計算することができます。よって、全てのマスを全探索して求めます。計算量は、\( O(H^2W^2) ...
[AtCoder] ABC 146 C – Buy an Integer
\( f(N) = AN + Bd(N)\) とすると、\( f(N) \) は増加関数なので、二分探索を行います。整数の桁数は、対数を使うよりも、数値を文字列に変換してから長さを得る方が良いと思います。
コード#inc ...
[AtCoder] ABC 145 D – Knight
マス \( i, j \) から \( (i + 1, j + 2) \) に移動するような動き方の回数を \( a \), マス \( i, j \) から \( (i + 2, j + 1) \) に移動するような動き方の ...
[AtCoder] ABC 145 C – Average Length
順列を生成して距離を計算します。
コード#include <bits/stdc++.h>using namespace std;typedef long long ll;int a;bool flag;dou ...
[AtCoder] ABC 087 D – People on a Line
座標間の距離が与えられるので、相対的な位置が分かります。したがって、ある座標の値を \( x_i = 0 \) として、\( M \) 個の情報に誤りがあるかどうかを調べます。
グラフ各座標をグラフの頂点として、\ ...
[AtCoder] AGC 040 A – ><
条件を満たす整数列を作ります。まず初めに、\( a_i = 0 \ ( 1 \leq i \leq N) \) とします。次に、文字列の先頭から末尾に向かって、\( S_i = \) ‘<‘ なら ...
[AtCoder] 第二回全国統一プログラミング王決定戦予選 B – Counting of Trees
一見難しそうに見えますが、\( 300 \) 点の問題なので解法は簡単であることが予想できます。
実現不可能な整数列頂点 \( 1 \) からの距離について頂点 \( 1 \) からの距離が与えられるので、 ...