atcoder.jp 問題 文字列$S$が与えられるよ 次の操作を1回行った後の文字列として、有り得るものはいくつある？ Sのうち2つの文字を選んで、入れ替える 成約 $2 \leq |S| \leq 10^{6}$ 思考 $O(N^{2})$は通らない… 片方を全探索して、もう片方がサクサクッと…

atcoder.jp 問題 3個の数列$A,B,C$が与えられるよ 長さ$Q$の数列$X$も与えられるよ 各$i=1,...,Q$について、以下の問題に答えてね $A,B,C$から要素を1つずつ選んで、和を$X_{i}$にすることができる？ 成約 $1 \leq |A|,|B|,|C| \leq 100$ $0 \leq A_i, B_i ,…

atcoder.jp 問題 正整数Nが与えられるよ 正整数以下の回文立方数のうち、最大値を教えてね 成約 $1 \leq N \leq 2 \times 10^{18}$ 思考 N以下の回文ではない立方数を考えてみる $10^{6}^{3} = 10^{18}$なので、$10^{6}$まで、順に3乗の値を見ていけば良さそ…

atcoder.jp 問題 長さNの文字列Sが与えられるよ 以下の操作をQ回繰り返すよ 文字$c_i$を$d_i$で置き換える 全部終わったら文字列はどうなる？ 成約 $1 \leq N,Q \leq 2 \times 10^{5}$ 思考 基本的に、クエリを全部舐めて「この文字はこれになって…」を整理…

atcoder.jp 問題 高橋くんがH行W列のグリッド上のどこかのマスに不時着したよ 高橋くんは、LRUDの文字列に沿って移動したよ 高橋くんは移動中に海を通ってないよ 高橋くんが不時着した可能性のあるマスの個数を数えてね 成約 $3 \leq H,W \leq 500$ $1 \leq …

atcoder.jp 問題 整数Nが1つだけ黒板に書かれてるよ 2以上の整数が全てなくなるまで、以下の操作を繰り返すよ 2以上の整数を1つ選んで、$x$とする $x$を1つ消して、$\lfloor \frac{x}{2} \rfloor$と、$\lceil \frac{x}{2} \rceil$を この操作で、お金が$x$円…

atcoder.jp 問題 N組の靴下があったよ i番目の組の靴下は、色iだよ K枚の靴下がなくなってたよ 靴下のペアの奇妙さは、左右の色の差の絶対値だよ 残ってる靴下の組み合わせで、最小の奇妙さはいくつ？ 残ってる靴下の枚数が奇数なら、1枚使わない靴下ができ…

atcoder.jp 問題 バスが走ってるよ N個のバス停で、バスの中の人が$A_i$変化したよ バスの中の人は、最終的に何人？考えうる最小値を答えてね 成約 $1 \leq N \leq 2 \times 10^{5}$ $-10^{9} \leq A_i \leq 10^{9}$ 思考 最初0人からスタートすると、途中の…

atcoder.jp 問題 N種類の食材があります 材料$i$は、$Q_i$あります 料理Aと料理Bがあります 料理Aを作るのに、材料$i$が$A_i$必要です 料理Bを作るのに、材料$i$が$B_i$必要です 料理Aと料理Bをあわせて何人前作れる？ 成約 $ 1 \leq N \leq 10$ $1 \leq Q_i…

atcoder.jp 問題 座標平面上で蛇のおもちゃを動かすから、どのパーツがどこにあるか教えてね 成約 $ 2 \leq N \leq 10^6 $ $ 1 \leq Q \leq 2 \times 10^5 $ 思考 クエリ毎に、愚直にシミュレーション dequeは添字アクセス遅いから、配列で誤魔化そうね 配列…

atcoder.jp 問題 N人が居ます 人$i$は、人$A_i$のすぐ後ろに並んでます 列に並んでる人の番号を順番に出力してね 成約 $ 1 \leq N \leq 3 \times 10^{5}$ 思考 先頭か末尾が分かれば辿れるねぇ 先頭は、$A_i$が-1の人$i$… * じゃあ、先頭の人$i$が分かったら…

atcoder.jp 問題 整数Nが与えられます 0,2,4,6,8だけが登場する整数が良い整数です 小さい方からN番目の整数を求めてね 成約 $ 1 \leq N \leq 10^{12}$ 思考 成約が大きい。やだ。 愚直に小さい方から1個ずつ求めていくわけではない気配 とりあえずサンプル…