Mister雑記

競プロやります。

ARC

Diverta 2019 2 - E 「Balanced Piles」(800)

atcoder.jp 問題 個の何も置かれていないマスがある。 以下の操作を繰り返すことで、全てのマスに個のブロックが 積まれているようにしたい。 積まれているブロック数の最大値を、最小値をとする。 個のブロックが積まれているマスを1つ選び、個以上個以下に…

Diverta 2019 2 - D「Squirrel Merchant」 (600)

atcoder.jp 問題 リスは今家にいて、個のどんぐりを持っている。 これを増やすために、今から換金所へ行こうとしている。 換金所は2つあり、番目の換金所ではについて 以下の操作ができる。 どんぐり個と1gの金属を交換する。 この交換は双方向で行うことが…

Diverta 2019 2 - C「Successive Subtraction」 (500)

atcoder.jp 問題 長さの整数列に対して、以下の操作を長さが1になるまで繰り返す。 を消し、末尾にを追加する。 最終的に残る値の最大値を求め、それを実現する操作列を1つ構成せよ。 制約 考察 まずが小さいケースで考えてみる。 のとき、 で最大値が得られ…

ARC066-D 「Xor Sum」 (600)

atcoder.jp 概要 正の整数が与えられる。このとき、 なる非負整数の組が存在し、かつを満たすようなの組の個数をで割った余りを求めよ。 制約 考察 まず、との間には以下のような性質がある。 = ここからという関係がわかる。よってをからの間で固定して、そ…

ARC080-E 「Young Maids」 (800)

atcoder.jp 概要 長さの順列が与えられる。ここでは偶数である。 以下の操作をが空になるまで繰り返すことで、長さの順列を作る。 の隣り合う2要素を選ぶ。これを順にとする。 をこの順を保ったままの先頭に挿入する。 こうして得られるで、辞書順最小のもの…

ARC090-F 「Number of Digits」 (900)

死ぬほどバグらせた。 atcoder.jp 概要 正整数に対し、「を10進数表記したときの桁数」と定義する。 整数が与えられる。正整数の組で、を満たすものの数をで割った値を求めよ。 制約 考察 ※今回は考察が随分と遠回りだったので、解法だけ読みたい方は飛ばし…

ARC098-D 「Xor Sum 2」 (500)

beta.atcoder.jp 概要 長さの数列が与えられる。このとき、 を満たすの組の数を求めよ。 制約 解説 この問題で鍵となるのは、以下の和とxorの間に成立する等式である。 右辺は分解すると、 は繰り上がりを無視した値 は繰り上がりのみを考えた値 と解釈でき…

ARC089-D 「Checker」 (500)

beta.atcoder.jp 概要 二次元グリッド上の個のマスについて、白と黒のいずれかの色が指定される。 二次元グリッド全体を白と黒からなる幅の一松模様で一様に塗ったとき、上で指定された通りに色が塗られるマスの数の最大値を求めよ。 制約 解説 条件の持ち方…

ARC089-C 「Traveling」 (300)

beta.atcoder.jp 概要 AtCoDeerくんは二次元グリッド上に存在し、単位時間毎に隣接する4マスのいずれかに移動できる。ただしその場に留まることはできない。 時刻0にてAtCoDeerくんがマスに存在するとき、各について時刻にてマスに存在するような、一連移動…

ARC101-C 「Candles」 (300)

ARC101-C 「Candles」の解説。

ARC098-C 「Attention」 (300)

ARC098-C 「Attention」の解説。 ちゃんと図を描いて整理しましょう。

ARC102-D 「All Your Paths are Different Lengths」 (700)

ARC102-D 「All Your Paths are Different Lengths」の解説。 頑張って実装しよう。

ARC094-D 「Worst Case」 (700) 別解

ARC094-D「Worst Case」の別解解説。 この解法を思いついたおかげでこの問題が好きになった。

ARC074-D 「3N Numbers」 (500)

ARC074-D 「3N Numbers」の解説。 水〜青なら絶対解くべき数列系の良問。

ARC074-C 「Chocolate Bar」 (400)

ARC074-C「Chocolate Bar」の解説。 もっとコンピュータを頼ってあげましょう。

ARC100-D 「Equal Cut」 (600)

ARC100-D「Equal Cut」の解説。 王道を往く数列系問題って感じ。

ARC100-C 「Linear Approximation」(300)

ARC100-C「Linear Approximation」の解説。 数列だけどグラフを書くとわかりやすいかも。

ARC099-D 「Snuke Numbers」 (500)

ARC099-D「Snuke Numbers」の解説。 トラウマ問題。相変わらず難しい。

ARC099-C 「Minimization」 (300)

ARC099-C「Minimization」の解説。 一見複雑そうな操作だが、実は......?

ARC/AGC

ARC-AGC記事のリンクまとめページ。 気長に埋めていきます。

ARC088-E 「Papple Sort」 (800)

Q. 高速に転倒数を求めるアルゴリズムは?

ARC100 (ABC102) 解説

ABC102/ARC100の解説です(A〜Dまで)。 数列がいっぱい、頭もいっぱいいっぱい。

ARC099(ABC101) 解説

ARC099といいつつ実質ABC101の解説。 D問題の解説がキツい。

ARC096-D「Static Sushi」(500)

ABC095-D「Static Sushi」の解説記事。 若干実装重めな問題でした。