ABC255のA~Fを解くまでの思考過程

ぼくがABC255のA～F (+コンテスト後にEx)を解くまでの思考過程をまとめてみました.

A : 1分39秒
B : 5分04秒
C : 10分29秒 (1ペナ)
D : 13分18秒
E : 38分26秒
F : 64分47秒

で, 163位でした

本当に素の思考過程なので, 自分流の言葉とかふんわりとした気持ちを使ってます
あと, ネタバレを多く含むので展開式になってます

問題のタイトル草
やるだけで, まあ2次元配列をつくる. 全く難しくない.

r,c = map(int,input().split())
a = [list(map(int,input().split())) for i in range(2)]

print(a[r-1][c-1])

ABC255 - B

これは…, 二分探索？嘘？B問題で？
とりあえずそんなことはないだろう. いくらABCとはいえ, Bで二分探索はない.

ああ, 二分探索じゃなくても, 人であって明かりに一番遠いやつを見つければいい.
各人から一番近い明かりが各人に届いた時点で照らされるからok.
その各人の距離のうちの最大値が必要な明かりの強さの最小値になる.
最大値が最小値になるというのは不思議な感覚だが, まあ論理は破綻してないので実装していく.

ユークリッド距離は $\sqrt{(x_1 - x_2)^2 + (y_1 - y_2)^2}$ なのだが, 計算誤差が嫌なのでとりあえず2乗のままで計算していく.
（本来はこれをやる必要がなかったが, いろんな問題で小数の誤差が問題になるので）
最後にsqrtを取ればokというわけだ. できた.

B問題にしてはかなりの難問だった. 今回はむずい回なんだろうか.

n,k = map(int,input().split())
a = list(map(int,input().split()))
dat = []
for i in range(n):
	x, y = map(int,input().split())
	dat.append((x, y))

def dist(x,y):
	return (x[0] - y[0]) * (x[0] - y[0]) + (x[1] - y[1]) * (x[1] - y[1])

ans = 0
for i in range(n):
	tmp = 10**18
	for k in a:
		tmp = min(tmp, dist(dat[i], dat[k-1]))
	ans = max(tmp, ans)

print(ans ** 0.5)

ABC255 - C

CとDでセットになってるな. Cは簡単verということか？
有限の等差数列 $S$ に含まれてるかって問題か.
$S$ の初項は $A$ , 公差は $D$ だから, 末項は $(N-1)D + A$ か.
$x$ が $S$ の外側にいる場合は, $S$ の端に行くしかないから, easy.
$x$ が $S$ の内側にいる場合は, 左右の $S$ の項のどっちにいけばokだから, (N-A)をDで割った余りを考えて, 左側にいくときと右側にいくときでminを取る.
これで実装すればok. できた.

> サンプル2 : 0 0 0 1

公差が0のときがあるのかよ！ $N \geq 1$ だから, まあ場合分けすれば, 絶対値でok.

> サンプル3 : 998244353 -10 -20 30

公差がマイナスのときがあるのかよ！（ry
これはめんどくさい！嫌な問題だ！まあ書いてたらサンプル4通ったから出すぞ！
あっ、出した後に間違いに気付いた.

x,a,d,n = map(int,input().split())
# a -> a + (n-1)d
if d > 0:
	if x < a:
		print(a-x)
	elif x > a + (n-1) * d:
		print(x - (a + (n-1) * d))
	else:
		targ = (x-a) % d
		print(min(targ, d-targ))
elif d < 0:
	if x > a:
		print(x-a)
	elif x < a + (n-1) * d:
		print(- x + (a + (n-1) * d))
	else:
		targ = (x-a) % d
		print(min(targ, d-targ))
else:
	print(abs(x-a))

WA
多分 $D< 0$ のときマイナスで割ってるし, もうダメダメなんだと思う
$D<0$ を考えたくない…　そうだ！ $D<0$ の場合って, 初項と末項を反対にすれば, $D>0$ に帰着できるじゃないか.
つまり初項 $A+ (N-1)D$ , 末項 $A$ の公差 $-D$ の数列を考えれば, ok. というわけで今度こそできた.
ACをお祈りして出す.

x, a, d, n = map(int, input().split())

if d < 0:
	a = a + (n-1) * d
	d = -d

# a -> a + (n-1)d
if d == 0:
	print(abs(a-x))
else:
	if x < a:
		print(a-x)
	elif x > a+(n-1)*d:
		print(x-(a+(n-1)*d))
	else:
		targ = (x-a)%d
		print(min(targ, d-targ))

AC!! いやな問題だった. C++だと, マイナス%dは変になるのでその人はもっときつかったと思う.
Diffは500くらいだろうか. まあやるだけといえばやるだけだが, きつい.

ABC255 - D

もうC問題みたいなのはやめてくれ. ぼくの精神が削れていく.
今度はクエリか. クエリは, $A_i$ を全部 $X$ に変える操作回数を求めるのね.
まあC問題で考えたけど, この操作の回数って $\text{abs}(A_i - X)$ なんだよね
つまり, $\sum^{N}_{i=1} \text{abs}(A_i - X)$ をたくさん求める問題ってことか.

上の灰色の面積を求めればいいってことね. 操作は可換だから $A_i$ はソートしてもよくて…今度こそ二分探索だ！
$X = A_i$ の場合は…　まあどっちでも変わらないからbisect_leftでもbisect_rightでもどっちでもok.
で, この面積は $A_i$ の累積和を使えば速く求められると…

具体的に $t = \text{bisect_left}(A, X)$ とすると,
水+桃は長方形だから $X \times t$
桃は累積和だから $\text{pfix}(t) - \text{pfix}(0)$
これの差を求めれば水はok.

青+黄は累積和だから $\text{pfix}(N) - \text{pfix}(t)$
黄は長方形だから $X \times (N-t)$
この差を求めれば青はok.

水＋青が答え.

これで解けた！
なんだ、B問題やC問題より簡単じゃないか. 最近茶色もみんな強いから, Diff 600くらいになりそうだぞ.

import bisect
n,q = map(int,input().split())
a = list(map(int,input().split()))
a.sort()

pfix = [0] * (n+1)
for i in range(n):
	pfix[i+1] = pfix[i] + a[i]

for i in range(q):
	x = int(input())
	tmp = bisect.bisect_left(a, x)
	ret = tmp * x - (pfix[tmp] - pfix[0]) + (pfix[n] - pfix[tmp]) - (n-tmp) * x
	print(ret)

ABC255 - E

1ペナはしたけど, 13分でDまで解けたから非常に順調だ！
次はE. うーん, 問題文を読んだだけじゃパッとしない.
$M \leq 10$ だから, bit DPでも使うんだろうか. bit全探索？
また二分探索でも使うんだろうか.
とりあえずサンプル1を見てみよう.
このサンプルで円周率が最適か. きれいな例を作ったもんだ.

うーん, まったく検討もつかない.
あれ？ $A_i + A_{i+1} = S_i$ ということは, サンプル1の第1項を $3$ にしたら第2項もただ1つに定まっちゃうじゃないか. そして第3項も, その次も, 全部決まってしまう.
つまり第1項を決めれば数列全体が決まるということか.

ここから0-indexedで考える.
具体的に数列はどうなるんだ. $A_1 = S_0 - A_0$ , $A_2 = S_1 - A_1 = S_1 - S_0 + A_0$ .
$A_3 = S_2 - S_1 + S_0 - A_0$ . うん. わかった.
$S$ の符号がプラスマイナス…ってなって, 最後の $A_0$ もプラスマイナス～って決まっている. $A_0 = x$ と置こう.
よく見たら, 式も典型90問のこの問題で見たやつと同じだったな. このときも同じ考察をした.

数列 $\text{sp}$ を, $\text{sp}(0) = 0$ , $\text{sp}(i) = S_i - S_{i-1} + \cdots + (-1)^{i} S_0$ としよう. $A_i = \text{sp}(i) \pm x$ で $A_i$ が決まる.
$\text{sp}(i)$ は $\text{sp}(i) = S_i - \text{sp}(i-1)$ として計算できるな.
ここで, $i=0$ のとき $A_0 = 0+x$ だから,
$i$ が偶数のときには $A_i = \text{sp}(i) + x$
$i$ が奇数のときには $A_i = \text{sp}(i) - x$ となる. 偶数・奇数で分割しよう.

あとは, ラッキーナンバーが多くなるようにラッキーナンバーを平行移動させればいい. 決め打ち二分探索？どうやって？
数列の値がでかい… ラッキーナンバーの覆面を平行移動させてやるとか？これは厳しい.
しかし, このE問題は解かなければレートが下がってしまう. なんとかして思いつかなければ.
$-x$ のところは, ラッキーナンバーを全部マイナスにすれば, $A_i \mapsto -\text{sp}(i) + x, M_i \mapsto -M_i$ となるから, $+x$ にできる.
しかし, ラッキーナンバーが違ってくるのだからこれでも平行移動できない.

よくわからない, どうやって解くのか.
$A_i$ で一番被ってる項をラッキーナンバーにするのか？非常に怪しい. これで最適解が得られるとは思えない.
$A_i$ を無理やりラッキーナンバーにするように $x$ を調整するのはどうだろう. そうして, どのくらい $A_i$ にラッキーナンバーが含まれるのか調査する. $M \leq 10$ だから, Counterを使って前処理すればカウントは $O(M)$ で済む. 全探索しても考慮すべきパターンは $O(NM)$ .
同じ値を検索しないようにsetを使って高速化する必要はあるんだろうか？最悪パターンでは逆に計算量が増える気がする. 工夫せずやったらどうなるんだろう.
$N\times M \times M \leq 10^7$ だから, これは間に合う！
しかも, 最適解は必ず1個以上ラッキーナンバーを含むから, これで全部網羅できる！（全射）これだ！！！絶対これ！！！
というわけで, 奇数偶数にわけて探索していく. ちょっと実装に手こずったができた！！
しかしサンプルがいつもの如く貧弱. 大丈夫なのだろうか.

from collections import Counter

n,m = map(int,input().split())
s = list(map(int,input().split()))
x = list(map(int,input().split()))
xinv = [-i for i in x]

#a[0]に完全に依存する

#a[1] = s[0] - a[0]
#a[2] = s[1] - a[1] = s[1] - s[0] + a[0]

sp = [0] * n
for i in range(n-1):
	sp[i+1] = s[i] - sp[i]

# 2 * 10^5 * 10 *

#print(*sp)

v = []
for i in range(0, n, 2):
	v.append(sp[i])

w = []
for i in range(1, n, 2):
	w.append(-sp[i])

vc = Counter(v)
wc = Counter(w)

ans = 0
for i in v:
	for j in x:
		targ = j - i
		tmp = 0
		for k in x:
			tmp += vc[k - targ]
		for k in xinv:
			tmp += wc[k - targ]
		ans = max(tmp, ans)

for i in w:
	for j in xinv:
		targ = j - i
		tmp = 0
		for k in x:
			tmp += vc[k - targ]
		for k in xinv:
			tmp += wc[k - targ]
		ans = max(tmp, ans)

print(ans)

AC！やったああああああ！！！！！！実装がちょっと複雑だが, 解けた！
これはおそらくDiff 1600あたりになるんじゃないかと思う. 難しい.

ABC255 - F

E問題は少々遅れてしまった. それでもまあまあ速い方のようだ.
順位表を見た. F問題も, E問題かそれ以上に難しいっぽい.
Fが解けなくても耐えになるから, ここからは挑戦枠ということだな.

行きがけ順, 通りがけ順？wikipediaへのリンクが貼ってある.
この前, Codeforcesでもwikipediaへのリンクが貼ってあったな.
行きがけ順はそれはそうって感じだ.
通りがけ順…が分からない. 説明を読んでもさっぱり分からない.
なんでG, I, Hって見てるのに通りがけ順はG, H, I なんだよ.
…ああ, 右側にあるからか… なるほどね. 左～真ん中～右って感じなのか. でも行きがけ順と雰囲気は似てるな.

で, 何をするんだ. サンプル1を見てみよう.

6
1 3 5 6 4 2
3 5 1 4 6 2

うん. 分からん. いや, 分かる. 行きがけ順で先頭が1なのだから, 1は根っこに来る.
次は3だ. う～ん, どういうことだ？通りがけ順で1より左にあるということは, 1の左側の子に3が来るということで確定するということか.
そういう意味では, 当初 $I$ の区間 $[0, 6)$ で放たれた我々は, $I$ の(0-indexedで) 2番目にある $1$ によって $[0, 2)$ と $[3, 6)$ に分裂したというわけだ.

次は $[0, 2)$ を考える番だ. $3$ で $[0, 0)$ と $[1,2)$ に帰着され, 前者は存在しない, 後者は存在する.

あとは, $6$ で1の右側（ $[3, 6)$ ）にいくということか. これは, もしかして再帰？pypyで再帰は嫌だな…
いや, $P$ を順に見ていけば, 区間をスタックで管理できるな. 右側にappendして, 右側からpopして実装できる.
そこで矛盾が発生すれば, （正確には, 今見ている $I$ の区間の中に, 今の頂点の $I$ の位置が適さなかったら） -1を出力してexitする.

一回人力でアルゴリズムを試してみよう. お, できた. サンプル1の出力例と一緒だ！これだろ！
子孫を出力するから, 親も考慮しないとな. 親も（左側と右側の情報と番号を入れて）同じくスタックに入れればokか.（コードのnsh）
$x$ が $I$ の何番目に来るかは, 前処理しとけば $O(1)$ で出来る.（コードのbinv）だから, 結局 $O(N)$ か. 速いね.

実装した. サンプル1を試してみよう.
うーん、だめ！（ここはしょうもない実装ミスだったが, 15分くらい詰む）

お、よし！できた！時間がかかった…

サンプル2を試してみよう.
あれ？-1を出力しない. どういうことだ？なぜ-1じゃない？
根っこに制限があるのか？もう一度問題文を見てみよう.
あ、「頂点1を根とする二分木」って書いてあるな. じゃあ, 根っこに1以外が来る場合-1を出力するように場合分けして、と…

サンプルがいつものように貧弱. でも実装は良い感じなので, 行けてほしい.
これで提出！！お願いします！！！！！

n = int(input())
a = list(map(int,input().split()))
b = list(map(int,input().split()))

binv = [0] * (n+1)
for i in range(n):
	binv[b[i]] = i+1

#真ん中がa[i], ←に分割

lf = [0] * (n+1)
rg = [0] * (n+1)
constl = [1]
constr = [n+1]
nsh = [0]
for i in range(n):
	#a[i]にいく
	#0～1に制限される. [l, r)
	x = constl.pop()
	y = constr.pop()
	targ = binv[a[i]]
	#print(x,targ,y)
	if not x <= targ < y:
		print(-1)
		exit()
	k = nsh.pop()
	if k >= 0:
		lf[k] = a[i]
		if k == 0 and a[i] != 1:
			print(-1)
			exit()
	else:
		k = ~k
		rg[k] = a[i]
	if y - (targ+1) > 0:
		constl.append(targ+1)
		constr.append(y)
		nsh.append(~a[i])
	if targ - x > 0:
		constl.append(x)
		constr.append(targ)
		nsh.append(a[i])


for i in range(1, n+1):
	print(lf[i], rg[i])

AC！！！やったあああああああああああああ！！！！！！！！！！！！！！G,Exは難しそうだが, 一応挑戦してみよう.

ABC255 - Ex （あとから解いた）

Gよりこっちの方がたくさん解かれてる.
またクエリか… $N, D$ がデカすぎませんか？
これはきつい… しかしやることは遅延セグメント木でできそう.（もしかしたら平方分割かもしれないが）
各点に重さがついてるのか. じゃあ, 2次元配列を用意して, 1次元目は実の個数, 2次元目は重みを付加させればよいか.
重みは, 座標圧縮でまとめられるな. つまり, 座標圧縮すれば, 遅延セグ木の要素数は $4\times 10^5$ で, これはいけそう. コストも, 和の公式を使えば求められる.
遅延セグ木にどういう操作をすればよいのだろう. まずは, 時間経過で実をならせること. 各頂点の実は「コスト×時間経過」だけ増加して, これは遅延セグ木でいけるね.
収穫は…　収穫は何？　コスト×時間経過では無理.　0にするにしたってmodで考えてるし, 無理やり単位元にするのもできない.
うーん困った. ん？よく考えれば, これは $a_i \mapsto 0 a_i + 0$ だ. あ！これは, ライブラリチェッカーのK - Range Affine Range Sumで見た問題とほとんど一緒ですね. 区間の長さ→コストとしても操作は一緒で, コスト依存の定数upも $a_i \mapsto 1 a_i + 時間経過$ で可能だ.
ライブラリチェッカーの軽いやつから適当にコピペして…（おい）pypy3で提出！！！
WA（これは原因がわかった）で, コンテスト終了…
あとでやってもTLE…　でも計算量的には良い感じなはずなんだよなあ.
C++でやってみると, ACできた. pypy3が遅いだけだった！（これはデマ？で, pypyの遅延セグ木でACした人もいます）

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
typedef long long ll;
using namespace atcoder;
using mop=modint998244353;
const int mod = 998244353;
struct A{
	mop sum,len;
};
struct B{
	mop al,be;
};
A gam(A a,A b){
	return {a.sum+b.sum,a.len+b.len};
}
A zee(){
	return {0,0};
}
A ome(B a,A b){
	return {a.al*b.sum+a.be*b.len,b.len};
}
B acc(B a,B b){
	return {a.al*b.al,a.al*b.be+a.be};
}
B mem(){
	return {1,0};
}

int main(){
	ll n, q;
	cin >> n >> q;
	vector<ll> date(q);
	vector<ll> event(2*q);
	vector<ll> ecl(2*q);
	ll d, l, r;
	for (int i=0; i<q; i++){
		cin >> d >> l >> r;
		event[2*i] = l;
		event[2*i+1] = r + 1;
		ecl[2*i] = l;
		ecl[2*i+1] = r + 1;
		date[i] = d;
	}
	vector<ll> necl;
	unordered_map<ll, ll> e_c;
	ll tmp = 0;
	ll v = 0;
	sort(ecl.begin(), ecl.end());
	for (int i=0; i<2*q; i++){
		if (tmp < ecl[i]){
			tmp = ecl[i];
			necl.push_back(tmp);
			e_c[tmp] = v;
			v++;
		}
	}
	vector<A> ts(v-1);
	mop x, y;
	for (int i=0; i<v-1; i++){
		x = necl[i+1];
		y = necl[i];
		ts[i] = {0, x * (x-1) / 2 - y * (y-1) / 2};
	}
	lazy_segtree<A, gam, zee, B, ome, acc, mem> ls(ts);
	mop nd = 0;
	for (int i=0; i<q; i++){
		int l = e_c[event[2*i]];
		int r = e_c[event[2*i+1]];
		mop d = date[i];
		ls.apply(0, v-1, {1, d-nd});
		nd = d;
		cout << ls.prod(l, r).sum.val() << endl;
		ls.apply(l, r, {0, 0});
	}
}

しょぼんブログ

数学の色々とか様々とか

ABC255のA~Fを解くまでの思考過程