other/

README

Codeforcesの1200~1800の問題

Last Change: 2020-07-01 22:20:13.

math, number theoryタグも結構解いたので、その他の苦手も克服する。

1366C ★ @2020-06-18

1500。考察は簡単だが、実装で迷走したので模範解答を読んだ。

マンハッタン距離でグループ分けしたり、forループも素直にまわすのみだったり、模範コードがかなり勉強になる。 グループ分けという発想は特に汎用的だと思うので、意識して身につけたい。

	// 普通の二重ループでスキャン、グループごとに1/0の数をカウントする
	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			cnts[i+j][A[i][j]]++
		}
	}

1366B ★ @2020-06-18

1300。自力。

セグメントの交差判定は模範解答のものを覚えたほうが良いかもしれない。

「左端の大きい方と、右端の小さい方を比較して、区間が残れば良い。」

for _ in range(int(input())):
    n, x, m = map(int, input().split())
    l, r = x, x
    for _ in range(m):
        L, R = map(int, input().split())
        if max(l, L) <= min(r, R):
            l = min(l, L)
            r = max(r, R)

    print(r - l + 1)

1363C @2020-06-18

1600。ゲーム系では簡単な方だと思うが、解説AC。

終わりの状態をイメージする系だが、DPで全探索するとかではないので、自信を持って詰めるのが難しいと感じた。

1363B @2020-06-18

1400。自力。

AtCoderの企業コンテストで似たようなのがあった気がする。

00..011..1 or 11..100..0 と比較する全探索をするという大方針は模範解答どおりだったが、 自分のACコードだと 10^8 ぐらい計算が必要なはずで、本番ではとても提出できないものになった。

ちゃんとコスト計算の部分も効率化する必要があり、これは累積和っぽいやり方でできる。

1355B @2020-06-18

1200。自力。

ソートして貪欲にグループを作っていけば良い。 あまりは次のグループに持ち越す。

DPでもできるっぽい？

1354B ★ @2020-06-18

1200。自力。

模範解答はエレガントという感じだったが、自分は尺取法でやった。 蟻本の種類数で考える尺取法は時々思い出しておきたい。

	// しゃくとり法により解を求める
	r := 0
	num := 0
	ans := 1 << 60
	count := make(map[int]int) // 事柄->出現数の対応
	for l := 0; l < n; l++ {
		for r < p && (num < n) {
			// sum += A[r]
			// r++
			if count[A[r]] == 0 {
				// 新しい事柄が出現
				num++
			}
			count[A[r]]++
			r++
		}

		// ans += (r - l)
		if num == n {
			ChMin(&ans, r-l)
		}

		if r == l {
			r++
		} else {
			// sum -= A[l]
			if count[A[l]] == 1 {
				// ある事柄の出現数が0になった
				num--
			}
			count[A[l]]--
		}
	}

1351C @2020-06-19

1400。自力。

ちょっと戸惑ったが、移動前と移動後の座標を単純にベクトル和を取るだけで、セグメントをハッシュ化できる。 ハッシュマップで通過判定を管理すればよい。

1353D ★★ @2020-06-19

1600。わからなくてtutorialを読んだ。

基本は実装で立ち向かうことになるが、愚直にやるとすぐ O(N^2) になってしまうので、priority queueを使う。 キューに突っ込むものを構造体にし、比較関数で操作すべきセグメントが取得できるように comparator を定義してやれば良い。

改めてpriority queueのパワーを感じられる良い問題だと思った。

1343C @2020-06-19

1200。自力。

ランレングス圧縮でやった。 実装はそんなに楽ではないと思う（工夫しないとバグりやすそう）。

1343D ★ @2020-06-19

1700。わからず。

ペアに関して「変更なし、1個だけ変更、2個とも変更」までに至ったのは良いが、そこからの全探索パートの効率化がわからず。 それぞれについて個別に条件を考えて数え上げに正しく落とし込むのが大事。 それが明確にできれば「いもす法などが必要」とか必要なデータ構造とアルゴリズムが想起できると思う。

1341B @2020-06-20

1300。自力。

問題設定を読み解くのがめんどいのと、単に累積和で全探索するだけだけど、気をつけるポイントは多い。 早くコーディングできることが重要。

1340B ★★ @2020-06-20

1700。詰めきれず解説AC。

dp [2000][2000]string がすぐに思い浮かんだので実装したが、そもそもバグを除去するのが大変だった。 結局別に dpf [2000][2000]bool という情報も作り判定してサンプルは通ったが、MLEしてしまった。

よくよく考えると dp [2000][2000]string 部分が大きすぎる。 情報としては dpf だけで十分で、ここから復元してやる必要がある。 ただし、上の桁から貪欲に大きくする必要があるため、DPする順序を下の桁から考えるなどは注意が必要。

1339B ★ @2020-06-20

1200。だけど全くわからず解説を読んだ。

ソートして真ん中からジグザグして端に寄っていけばよい。 確かにtutorialにある通り、図示すればなんとか自力で解けた可能性はある。。

1340A @2020-06-20

1500。自力。

複雑に見えるが、一様なところからある場所が選ばれると、そこから選べなくなるまで後ろに連続して選ばざるを得なくなる。

チェックするための条件が自分は P[i+1] - P[i] > 1 で十分だと思ったが、 模範解答はもっと面倒なことをやっているので、もしかしたら嘘解法なのかもしれない。

※模範解答では、しゃくとりっぽくイテレータが P を2周するような計算量になっているように見える。 とにかく、愚直に条件をチェックするなら計算量には注意が必要。

1335D @2020-06-20

1300。自力。difficultyの割に難しい。

9箇所いい感じに壊せばOKと思って、いい感じを最初に列挙してインクリメントしたが、 tutorialの通り「すべての1を2に変更すればOK」が簡潔だった。

頭が固い。

1336A ★★ @2020-06-21

1600。貪欲要素で嘘解法に陥ったため解説を読んだが、そもそも解説の理解に時間を要した。

「tourismのノードの祖先にindustryのノードはない」というのは貪欲の交換で考える論法からすぐわかる。 これを踏まえると「 n-k 個のtourismを選ぶ」という風に考えて、各ノードをtourismに選んだときの利得が計算できる。 これを大きい順に n-k 個加算すればよい。

利得自体は 自分を含めた部分木のsize - 根を1とした自分の深さ で計算できるが、これも理解が結構難しい。。 利得加算時とindustryの分布は異なるわけだが、深さを引いたりしている部分でしっかりと帳尻が取れることになる。 償却のイメージをしっかりと持てるようになりたい。

難しい問題だと思う。

1332C ★ @2020-06-21

1500。実装は解説を参考にした。

union findを利用すれば実験はできるので、そこから法則を見つける。 すると、長さ k の回文が n/k 個つながる形になるので、それをもとにあとはすべてのグループに対して すべての文字に変換した場合の全探索を行う。

実装は難しいが、模範解答のものは参考になる。

• 周期性の活用
• 重複を割る2で処理する
• データ構造

1333C ★★ @2020-06-21

1700。早々と解説を読んだ。

まずは各要素を左端とした部分配列の個数を愚直に足し上げていく、素直な方法からスタートする必要があった。 すると、goodな部分配列は連続し、あるところで途切れるとそこからはすべてnot goodになるという性質が見つかる （この時点で単調性が見えてくる）。 また、累積和を使うと「同じ値が登場したところがそのような箇所」であるといえる。

これは愚直にやると O(N^2) なので、単調性を利用して高速化することを考えると、しゃくとり法が設計できる。

しゃくとりの条件部分は、蟻本の例題のようにハッシュマップでカウントを保持するやり方で良いが、 safe conditionの部分やハッシュマップの初期設定は添字に注意して慎重に実装しないと、 サンプルすら通せなくなってしまうので注意。

累積和上で尺取法するときは十分に気をつけること！

※ちゃんと累積和 P 上で尺取法を考えると、自分にとってしっくりするコードが書けた。

1328C @2020-06-21

1200。自力。

問題設定は面白いが、複雑に見えてとても簡単。 大きいほうが出来上がったら、のこりは貪欲に小さい方に押し付けるのがお得。

1328B @2020-06-21

1300。自力だが、サンプル通すまでに時間がかかった上に、オーバーフロー周りのペナも2回踏んでしまった。 掛け算がでたら int64 ！

等差数列の和を考えて、二分探索と組み合わせながらやった。 が、添字部分で頭がこんがらがり、えらい目に合った。

模範解答のコードは二分探索などせずシンプルだが、結局は添字の部分で同じような辛さがあると思った。

1327C @2020-06-22

1600。自力。

構築に分類されると思う。 この手の操作回数の上限が与えられるタイプは十分なことが多い。 なので、シンプルかつ愚直な方法を考案し、その回数が足りていることを証明できれば良い。

今回は n*m - (n+m) + 3 > 0 となる（はず）。

1325D ★★★ @2020-06-22

1700。全然わからず。

tutorialの理解もしんどかったが、この方のブログ がかなりわかりやすかった。

自分の中で抜けてたXORの性質は以下の2つ。

• a+b = a^b + 2*a&b
• 偶奇性

2つ目については、XORを考えるときは偶奇性やmod 2を考えるとヒントが掴めることがある、ということ。

1327B @2020-06-22

1200。自力。

ReadForces。無意味。素直に全探索するシミュレーションをすればよい。

1326C @2020-06-22

1300。自力。

AtCoderっぽい数え上げ。

1324D @2020-06-22

1400。自力。

zero sum rangesとかじょえちゃんねるであったような変数分離の数え上げ。 二分探索の練習に。

1323B ★★ @2020-06-22

1500。詰めきれずにtutorialを読んだ。

基本は自分の考えであっていたが、個数をメモして高速に数え上げる詰めの部分ができていなかった。 ある意味愚直で良い部分があるが、二重ループになってしまうため直感的にはTLEしてしまうように見えてしまい、難しい。 実際には、連続する1の部分を各イテレータがそれぞれ一周だけするイメージであっているはずで、 2*N 回の計算で済む。

掛け算が絡むと不安なのでちゃんと int64 でやること！！

1322A @2020-06-23

1300。自力。

カッコ列のprefix balanceなるものを考える初歩的な問題だと思う。

閉じカッコが先行する部分は必ずreorderする必要があるので、貪欲に。

実装がちょっとバグりやすそうで怖い気がしたが、これぐらいは慎重にやって一発で通したい（一発で通せたので良し）。

1321C ★ @2020-06-23

1600。証明が微妙だったので最初からtutorialを読んだ。

「現時点で消せるもののうち、文字型として最大のものを選択する」という貪欲法でよい。 適当に実装しても O(n^2) にはなる。

「ある文字 r を消すとき何らかの s が消えなくなることが懸念される」 わけだが、何かが間に入って邪魔する場合は、その邪魔なものを消すことができない（ので、消してしまって良い）ことが証明できる、 というのが鍵になると思う。 これは素直に場合分けすれば証明できると思うが、なんとなく感覚的にすっと納得するのが難しい気がする。

1320A @2020-06-23

1400。自力。

DPから入って O(n^2) から抜け出せず迷走してしまった。

よくよく見ると変数分離が正解。

1369D ★★ @2020-06-24

1900。コンテスト参加中にかなり考えたが全くわからなかった。

再帰的な構造を見出してDPをする必要があった。

よくよく観察すると（※定義からも見いだせる可能性はある）、左と右に i-2 レベルのものが、真ん中に i-1 のものが 連なった形になっている。

これを踏まえると dp[i] := level iにおける答え によって dp[i] = dp[i-2]*2 + dp[i-1] で行けそうに見える。 ただし、 dp[x] において、その答え（すなわち最大数）が、根を塗ることでしか達成できない場合と、根を塗らなくてもよい場合で分けて考える必要がある。

i-2, i-1 のものともに根を塗らなくて良い場合は、根本の4つをさらに塗ることができるため、 +4 できることになる。 そして、その場合は「根を塗らなければ最大数を達成できない場合」に該当する。 よって、次の2レベルに関しては根を塗らずとも達成でき、3レベル先でまた同様となる。

つまりは i を1-indexとすると i%3 == 0 のときだけ +4 すればよいことになる。

わかるとスッキリできて面白い問題だと思う。

1316B @2020-06-25

1400。自力。1500ぐらいあってほしい難易度に感じたが。。

後ろのほうがそのままの形で前に来るのはわかったが、前半部分がどのように変化するのかに気づくのに時間がかかった。 毎回反転しながら後ろにずれていく形になるので、偶奇性で判定できる。

後は全部の k について試すわけだが、雑に全部保持してソートとかしたらMLEになった。 こどふぉではMLEにも十分に注意したい。

1320B ★@2020-06-25

1700。わずかに届かず。

逆向きのグラフを貼ってゴールからの最短路を求めるのはわかる。 つじつま合わせの部分で元のグラフが必要なことに気づけず、迷走してしまった。 また、チェックの際計算量を見誤り、変に効率化しようとしたせいで間違った方法を選択してしまった。

グラフではしばしば全探索の計算量を見誤るので、ひときわ注意を払おう。

※ダイクストラでなくてよいので、BFSのライブラリチェックなどするのも良い。

1315C @2020-06-26

1200。自力。

大きいものを残すほうが構築仕切る上では有利なので、選べる最小のものを愚直に探す。 N<=100 に騙されずに O(N^2) でよい。

1315B @2020-06-26

1300。自力。

連長符号化で簡単になるタイプかと思いきや、結構厄介。 冷静にコーナーケースを排除するだけでよいのだろうか？

一発で通してしまっただけに、ちょっと反省がしづらい。

1312D ★★ @2020-06-26

1700。全くわからずに解説AC。

解法は非常に明快だった。

まず、題意から 1 ~ m から異なる数値を n-1 個選ぶ必要がある。 ここから、最大値を除いた n-2 個の中から、唯一のかぶる数値を選ぶ。 最後に、↑の3個を除いた n-3 個について、最大値を中心に左右どちらに振るかを選ぶため、 2^(n-3) 通り乗算する。 左右に振った後は、自動的にソートされる形で決定するので、これでおしまい。

このような構築っぽい雰囲気のある数え上げ方法は勉強になる。

1328D @2020-06-26

1800。difficultyはDiv3なので少し高めに出ていると思う。ほぼ自力（面倒になってテストケースを見た）。

構築。注意力が必要。 実装はかなり綺麗にできたと思う。

1329A @2020-06-26

1800。Div1Aを一発で通せたのはヨシ。

駄目な条件を先に祓っておくと、いろいろな方法が考えられるのだと思う。 自分は、前の方から以前の色が残るように塗る方針で、はみ出さないように先に余分な数値を削るような方法をとった。 こうすると、まだ塗られていないタイルの先頭を選べば良いようになり、塗り方の構築部分が簡単になる。

tutorialでは累積和を活用しているっぽい。

※本問題の解説は構築問題へのアプローチ方法が割と丁寧に書かれているので、 これも理解したいかもしれない。

1368D @2020-06-26

1700。自力。

ビットは他方に移動したりするものの、数は保存される。 (a+b)^2 = a^2 + b^2 + 2*a*b より、できるだけビットは1つの要素に寄せるほうが、 2乗和は大きくなるはず。

よって、各要素の各ビットの立っているものの数をカウントしておき、 貪欲に要素を構築していく。

1368C @2020-06-26

1500。自力。

純粋な図形の構築問題。 無理だと思ったが、お絵かきをしているうちに拡張性のある n=1 のケースがひらめいて一般化できた。

自分が思いついたものはコーディングも割と楽。

1367C @2020-06-26

1300。自力。

禁止区間を最初から除外してしまって、自由に配置できるところを貪欲に考える。 自分は切り上げ演算を考えたが、tutorialでは切り捨てでやっていた。

連長符号化してシンプルな実装を心がける。

1368B @2020-06-27

1500。自力。

文字列の構築。 cccooodddeee... みたいな感じで1文字ずつ追加して、掛け算の結果が k を超えるかを考えれば良い。

tutorialを読んだ感じ、証明は結構難しいのかもしれない。。

1367D ★ @2020-06-27

1800。わからずに解説AC。

解法は非常に明快。 まず、「最大の文字」というのは絶対に存在するのだから、そこの B[i] は0で確定する。 そこが決まれば、他はすべて減算されるので、再び小さな問題が出来上がるので、再帰的に処理していけば良い。

実装も結構大変かつ落とし穴もあり、3WAしてしまった。 もうちょっとサブルーチンをキレイにしてバグる可能性を減らしたかった。

数列があれば、必ずその中には最大値が存在する（それはそう）。

1325C ★ @2020-06-27

1500。解説AC。

木の直径とかが絡むのかと思った（もしかしたらそれでも通るのかもしれない）が、 MEXとやらの性質的に、次数が3以上のところのノードから伸びる枝に、 0, 1, 2 を振ってしまえば、MEXは2で抑えられる、とのこと。

一直線のときだけコーナーケースなので注意。

1324E @2020-06-27

1700。自力。

かなり初歩的なDP。 sleep after x hours という英文が「x時間眠る」かと思って大混乱してしまった。

また、DP部分で変な実装をしてしまい1WAしてしまったので、多少冗長になろうともわかりやすいコーディングを心がけること。

1327E ★★ @2020-06-27

1800。肝の部分がわからずに解説AC。

prefix, suffix, それ以外の3つのパートでそれぞれの長さのものを排他的に考えて数え上げる。 AtCoderに出ていてもおかしくないような問題に見える。

※以下はtutorialのコアとなる考え方（多分）。

3つのパートに分けて、各長さのブロックを数えようとしているが、 おそらくその過程で、考慮される数値全体で見ると、ある数値が複数回登場しているはず。 しかしながら、その中で肝心のブロックの個数については、今注目しているパートのもののみをもれなく数えようとしている。 そのため、ブロックの数え上げについては他とかぶることがない。

1311C @2020-06-27

1300。自力。

26文字分累積和を作っておく。 区間和を計算する必要はないので、実装は比較的簡単。

1311B ★ @2020-06-27

1200。自信がなかったので解説AC。

当初思い浮かんだ「移動可能なセグメントをそれぞれソートして、最後に正しいソート列と一致するかチェック」 でもOKとのこと。 ただし、実装が煩雑そうだったので、もう一つの「バブルソートのシミュレーション」を考えた。

バブルソートの手法では、交換が必要なのに交換操作が許されていない場合にNOとし、 最後まで引っかからなかった場合はソートが保証される。

バブルソートの実装を振り返るのにいい問題。

1373D ★★ @2020-06-28

1600。解説のDPを実装してみた。

おそらく耳DPと呼ばれるようなDPに該当する。 応用幅は広いので実装に慣れたい。

※以下はDPの実装を見た雑な感想。

反転状態のときは i -> i+2 としているのが非常に賢い。 これによって、反転するセグメントが偶数長であることを保証している（ということであっているはず、多分）。 このような遷移はトリッキーにも見えるが、「このような遷移をした次は i+2 を遷移元とした場合をイメージする」 と考えると、多少は考えやすくなるかもしれない。

1305B @2020-06-29

1200。自力。

端から貪欲にカッコが成立するように消していくと、一回以内で済む。 感覚的な証明は、そのように交換すると飛ばしたカッコはペアになりえない、、とかそういう感じでいいと思う。

diffの割に考察も実装も難しいと思った。

1307B @2020-06-29

1300。自力。

算数、整数、苦手なやつ。 最後の方で帳尻を合わせるわけだが、場合分けが必要。

tutorial見ると、Aのうち最大の値だけを使えばいいっぽい。

1307C @2020-07-01

1500。自力。

arithmetic progressionは等差数列のこと（多分）。 少し考えると部分列の長さは1, 2で十分（3以上を考えるときは2のものを切り出せるから）。

自分は累積和を利用したzero sum ranges的なカウントの計算をしたが、 tutorialの素直な cnts [26][26]int を用いたDPのほうが、計算量の観点からも安全だった。

※都度文字列を生成する自分の手法は、定数倍が思いようで600msecぐらいかかってしまったので、ちょっと危険。