[AtCoder] ABC 160 C – Traveling Salesman around Lake
\( e_i \) を家 \( i \) と \( i + 1 \) との距離とすると、\( e_i = A_{i + 1} – A_i \) となります。ただし、\( e_N = K – A_N + ...
[AtCoder] ABC 159 D – Banned K
\( k \) 番目のボールを除いたときに整数が等しいような異なる \( 2 \) つのボールを選び出す方法の数が変化する整数は、\( A_k \) だけなので、全体の組み合わせから \( A_k \) の値を引くような方針で ...
[AtCoder] ABC 159 C – Maximum Volume
縦、横、高さの長さをそれぞれ、\( x, y, z\) とすると、\( x + y + z = L \) となります。体積を \( f(x, y) \) とすると、
\
となります。\( f(x, y) ...
[AtCoder] パナソニックプログラミングコンテスト2020 D – String Equivalence
深さ優先探索を使うらしい。
コード#include <bits/stdc++.h>using namespace std;typedef long long ll;int N;void dfs(string s) ...
[AtCoder] パナソニックプログラミングコンテスト2020 C – Sqrt Inequality
実際に平方根の計算をすると誤差が怖いので、整数で比較する方法を考えます。
\
ここで、\( c – a – b < 0\) ならば上記の不等式は正しくありません。よって、\ ...
[AtCoder] ABC 158 D – String Formation
文字列 \( S \) を前後を反転してできる文字列を \( S^* \) とします。\( S \) の先頭に追加された文字列を \( L \) とし、末尾に追加された文字列を \( R \) とすると、最終的な文字列は、\( ...
[AtCoder] ABC 158 C – Tax Increase
消費税を題材にした問題ですね。全探索をするのが楽ですが、ここでは別の解き方をしようと思います。
\( A \) に着目\( A \) に着目すると、
\
を満たす \( x \) を求めれば ...
[AtCoder] ABC 157 E – Simple String Queries
区間和のような情報が必要なので、セグメント木を使います。\( 1 \) 文字目から \( i \) 文字目までの文字の種類を \( 2 \) 進数を用いて表現します。これは、\( 26 \) ビットで表現できます。これをセグメ ...
[AtCoder] ABC 157 D – Friend Suggestions
まず初めに、友達関係の Union-Find を作成します。このとき、人 \( i \) の友達の数を \( f_i \) として数えます。次に、人 \( i \) のブロック人数を \( b_i \) と、人 \( i \) ...
[AtCoder] ABC 157 C – Guess The Number
\( d_i \) を上位から \( i \) 桁目の数字とします。\( d \) を \( -1 \) で初期化し、条件を満たすように数字を決めた時、\( d_i \) が異なる数字を取るときは整数が存在しません。また、\( ...