[AtCoder] CODE FESTIVAL 2018 Final (Parallel) A – 2540
問題方針与えられたグラフにおいて、\( 2 \) 回の移動で距離が \( 2540 \) となるパスの合計を求めたいので、ある頂点に接続している辺の距離の本数を数えます。
例えば、\(G \) を頂点 \( i \) から延び ...
[AtCoder] ABC 122 D – We Like AGC
問題方針どのような文字列を除くか
どのような部分文字列を取り除くかを考えます。
長さが \( 3 \) の文字列では、”AGC”, “ACG”, “GAC̶ ...
[AtCoder] ABC 061 D – Score Attack
問題方針
グラフの問題では最短距離を答える問題が多いと思いますが、今回は違います。このような問題では、重みの符号を反転させ、最短経路問題に帰着させます。これは、\( y = f(x) \) の最大化問題を \( y = -f(x) \) ...
[AtCoder] AtCoder Petrozavodsk Contest 001 B – Two Arrays
問題方針\( a_i \leq b_i\) のとき\( b_i – a_i \) 回 \( a_i \) と \( b_i \) に操作を施します。\( b_i < a_i\) のとき\( a_i – b_i ...
[AtCoder] CADDi 2018 for Beginners C – Product and GCD
問題方針\( P \) は \( N \) 個の整数の積で表現したときに、その整数の最大公約数です。どのような整数の組み合わせと \(P\) が最大公約数を最大化することを考えると、\であることが分かります。このとき、\( a = a_i ...
[AtCoder] ABC 051 D – Candidates of No Shortest Paths
問題方針全点間の最短距離を求めます。これはワーシャルフロイドなどで求めることができます。点 \( (i, j) \) 間の最短距離を \( d(i, j) \) とします。辺 \( a, b\) がこの最短経路に含まれる場合、辺 \( a, ...
[CSA] Round #4 Odd Divisors
問題ある区間における数字を割り切ることできる奇数の最大値の和を求める問題です。当然、奇数ならばその値が最大値です。方針区間の分割
区間 \( \) における数字を割り切る奇数の最大値の和を \( f(A, B) \) とすると、 ...
[CSA] Round #2 Online Gcd
問題方針ず初めに \( N \) 個の整数の配列を \( a \) とし、この配列の最大公約数を \( g \) とします。そのあとの \( M \) 回の操作は、整数 \( i, k \) が与えられ、配列の要素を\として更新します。この ...
[AtCoder] ABC 126 E – 1 or 2
問題方針与えられた情報から番号を当てられるか?
\( A_{X_i} + A_{Y_i} + Z_{i}\) が偶数という情報から番号を当てられることができるかを考えます。
例えば、\( A_1 + A_2 + 3 \mod ...
[AtCoder] AISing Programming Contest 2019 C – Alternating Path
問題方針各マスに番号を割り振る
\( H \) 行 \( W \) 列のマスを持つグリッドにおける \( i \) 行 \( j \) 列目のマスの番号を \( i \times W + j \) とします。このようにマスの番号を割り当 ...