Official
必要な発想は同難易度帯の問題の中では比較的少ないです.丁寧に計算式を作るようにしましょう.
Overall Editorial by maspy
ヒント集A - +3 +5 +7
Hint 1
この問題では $3$ 整数の差しか関係がありません.$c$ を定数として,すべての $x_i$ の初期値に定数 $c$ を足したり,$(+3, +5, +7)$ 操作の代わりに $(+3+c, +5+c, +7+c)$ 操作を考えてもよいということです.Hint 2
$(-2, +0, +2)$ 操作の場合が考えやすいと思います.この場合には $x_1+x_2+x_3$ が不変で,目標を達成するときの $x_1,x_2,x_3$ の値が計算できます.解説 → https://atcoder.jp/contests/arc158/editorial/5902
B - Sum-Product Ratio
Hint 1
例えば $x_i, x_j$ の $2$ つを決めたときに,$x_k$ としてどのような値が最適かを考えてみましょう.Hint 2
$x_i, x_j$ の $2$ つを決めると,$(x_i+x_j+x_k)/x_ix_jx_k$ はある定数 $a,b$ に対して $(a+x_k)/bx_k = (a/b)\cdot (1/x_k) + (1/b)$ と書くことができます.Hint 3
最適解で使われる可能性がある整数の候補を十分少ない個数に絞り込めれば,あとは全探索で解くことができます.解説 → https://atcoder.jp/contests/arc158/editorial/5903
C - All Pair Digit Sums
Hint 1
$x+y$ を計算するときの繰り上がりの回数を $k$ とすると,$f(x+y) = f(x) + f(y) - 9k$ となります.Hint 2
Hint 1 より,すべての $A_i+A_j$ を計算したときの繰り上がり回数の総和を計算する問題に帰着できます.この回数を,桁ごとに計算します.解説 → https://atcoder.jp/contests/arc158/editorial/5904
D - Equation
Hint 1
この式の両辺が同次式である,つまりすべての項の次数が等しいという特徴を利用します.Hint 2
$x, y, z$ の比を適当に固定したとき,多くの場合に解がちょうどひとつ存在します.解説 → https://atcoder.jp/contests/arc158/editorial/5905
E - All Pair Shortest Paths
Hint 1
「すべての部分区間 $[L,R)$ に対する計算結果の総和を求めよ」というタイプの問題です.「すべての $L$ に対する答を何らかの形で管理しながら $R$ を増やしていく」「分割統治を利用して中央をまたぐ区間に対する計算に帰着する」といった戦略が基本的で,本問ではどちらの解法も可能です.必要な発想は同難易度帯の問題の中では比較的少ないです.丁寧に計算式を作るようにしましょう.
解説 → https://atcoder.jp/contests/arc158/editorial/5906
F - Random Radix Sort
Hint 1
すべての $i$ に対して $B_{i}$ より右側に $B_{i+1}$ が来ることが必要十分です.各 $i$ に対する条件を整理しましょう.Hint 2
それぞれの位が最後にソートされたタイミングの順序だけが重要です.順列を数えるタイプの問題に帰着されます.
posted:
last update: