[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 \) 個の情報に誤りがあるかどうかを調べます。
グラフ各座標をグラフの頂点として、\ ...
[AOJ] No. 0568 パスタ (Pasta)
\( 3 \) 日以上同じパスタを選んではいけないという制約がポイントです。\( i + 1 \) 日目の予定を決めるためには、\( i \) 日目と \( i – 1 \) 日目の予定が影響することを考えて動的計 ...
[AOJ] No. 0567 最高のピザ (Best Pizza)
トッピングを \( k \) 個乗せた時の \( 1 \) ドルあたりのカロリー数を \( f_k \) とし、\( k \) 個のトッピングのカロリーの総和を \( s_k \) とすると、
\
とな ...
[AOJ] No. 0579 暑い日々 (Hot days)
\( i \) 日目に着ることができる服の派手さの最小値を \( v_i \), 最大値を \( w_i \) とします。各日において派手さの最小値または最大値を持つ服を選ぶことが最適なので、次の動的計画法を行います。証明はし ...
[AOJ] No. 0578 看板 (Signboard)
制約が緩いので愚直に文字列を走査していきます。
古い看板から作ることができる看板の例を考えます。例えば、お店の名前の文字列の長さが \( 3 \) であり、古い看板の文字列の長さが \( 7 \) のとき、文字列の ...
[AOJ] No. 0595 部活のスケジュール表 (Schedule)
前日と今日のスケジュールの状態を考えれば良いので、動的計画法を行います。便宜上、与えられた文字列の先頭に ‘J’ を挿入します。ここで、\( d(i, j) \) を \( i \) 日目の参加者の状態 ...
[AOJ] No. 0594 超都観光 (Super Metropolis)
東南方向の斜めの道が無ければ、\( 2 \) 点間の最短距離は、
\
となります。
南西方向観光スポットが南西方向にある場合、東南方向の道を通る必要がないので、最短距離は、
\
[AtCoder] AGC 040 A – ><
条件を満たす整数列を作ります。まず初めに、\( a_i = 0 \ ( 1 \leq i \leq N) \) とします。次に、文字列の先頭から末尾に向かって、\( S_i = \) ‘<‘ なら ...