Mister雑記

競プロやります。

AtCoder

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つ構成せよ。 制約 考察 まずが小さいケースで考えてみる。 のとき、 で最大値が得られ…

ABC126-E 「1 or 2」 (500)

atcoder.jp 問題 からなる長さの数列がある。この数列について個のことが分かっており、番目の情報は以下の通り。 は偶数である。 このとき、の全要素を知るのに必要なの値の数の最小値を求めよ。 なお、与えられる情報には矛盾がないことが保証される。 制…

ABC126-F 「XOR Matching」 (600)

atcoder.jp 問題 以下の条件を満たす長さの数列を、存在するならば1つ構成せよ。 がそれぞれ丁度2回ずつ現れる。 なる任意のについて、。 ここではbitwise xorを表す。 制約 考察 xorは群を成すので、「連続区間のxorは累積xor ()を考えるとよい」という定石…

ARC066-D 「Xor Sum」 (600)

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

ARC080-E 「Young Maids」 (800)

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

AGC003-D 「Anticube」 (1100)

一応自力AC。一応。 atcoder.jp 概要 個の整数が与えられる。ここから以下の条件を満たすようにいくつかの数を選ぶ。 任意の異なる2要素について、その積は立方数でない。 選べる個数の最大値を求めよ。 制約 考察 言い換えをすると、「掛け合わせると立方数…

ARC090-F 「Number of Digits」 (900)

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

7日目 みんなのプロコン2019 予選

atcoder.jp ABCDF5完で久々の橙パフォ。人々、問題を解きすぎ。 D. Ears (600) D - Ears 概要 数直線があり、からの各点には空の箱が置かれている。 すぬけ君はこの数直線上を、以下のルールに従って移動をする。 ]の区間のみを移動する。 始点と終点の座標…

日経コン2019予選 反省

atcoder.jp オンサイト行きならず。 目次 目次 A. Subscribers (100) 概要 制約 解説 実装例 B. Touitsu (200) 概要 制約 解説 実装例 C. Different Strokes (400) 概要 制約 解説 実装例 D. Restore the Tree (500) 概要 制約 本番の考察 解説 実装例 感想 …

ABC116 解説

atcoder.jp 地味に実装が辛かった回。 A. Right Triangle (100) A - Right Triangle 概要 である直角三角形の3辺の長さが与えられる。この直角三角形の面積を求めよ。 制約 入力は全て整数。 面積は整数であることが保障されている。 解説 であることから、…

AGC029-B 「Powers of two」 (600)

atcoder.jp 概要 整数が書かれた個のボールがある。個目のボールにはが書かれている。 これらのボールからいくつかのペアを作り、各ペアに書かれた整数の和が2べきとなるようにしたい。最大でいくつのペアを作れるか求めよ。 制約 補題 まずは後のために、2…

AGC029-A 「Irreversible operation」 (300)

atcoder.jp 概要 個のオセロ石が直線状に並んでいて、左から個目の石の色は最初 (か) である。 このオセロ石に対して、以下の操作を考える。 なるを1つ選び、に置き換える(要は2つの石をひっくり返す)。 この操作を最大何回行えるか求めよ。 制約 解説 「を…

ABC114 解説

※各問題名は表記ミスではありません。 beta.atcoder.jp 目次 目次 A. 753 (100) 概要 制約 解説 実装例 B. 754 (200) 概要 制約 解説 実装例 C. 755 (300) 概要 制約 解説 実装例 D. 756 (400) 概要 制約 解説 実装例 感想 A. 753 (100) beta.atcoder.jp 概…

CODE FESTIVAL 2018本戦 参戦記

11/17、CODE FESTIVAL 2018の本戦へ行ってきました。本記事はその体験記です。 起床〜会場入り 今年のこどふぇすは開場が8時でコンテスト開始が9時半と非常に健康的。正直寝不足でしんどかったです。 会場であるUDXに着くやいなや、ネームパスを貰って早速会…

AGC011-B 「Colorful Creatures」 (400)

beta.atcoder.jp 概要 匹の生き物がいて、色の生き物の大きさはである。 各生き物は大きさが自分の2倍以下の生き物を吸収することができ、吸収後の色はそのままで大きさは2体の合計となる。 具体的には、色の生き物が色の生き物を吸収すると、色で大きさがの…

AGC011-A 「Airport Bus」 (300)

beta.atcoder.jp 概要 空港に人の客がそれぞれ時刻に来る。 これらの客全員を何台かのバスで運ばなければならないが、1台のバスの定員は人で、さらに客を到着からより長く待たせることはできない。 このとき、客全員を運ぶのに必要なバスの台数の最小値を求…

AGC010-B 「Boxes」 (500)

beta.atcoder.jp 概要 個の箱が環状に並んでいて、最初番目の箱には石が個入っている。 ここから以下の操作を繰り返すことで、石を全ての箱から取り除くことが可能か判定せよ。 箱を1つ選ぶ(番目の箱を選んだとする)。 について、番目の箱から石を個取り除く…

AGC010-A 「Addition」 (300)

beta.atcoder.jp 概要 長さの数列が与えられる。このとき、以下の操作を繰り返すことでの長さを1にできるか判定せよ。 の偶奇が一致しているような相違なるを選ぶ。 をから消す。 をの末尾に挿入する。 制約 解説 まず各値で注目すべきはその偶奇のみなので…

ARC098-D 「Xor Sum 2」 (500)

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

ABC113-D 「Number of Amidakuji」 発展解法

問題リンク この問題については先日解説記事を書いたのだが、実はこれより遥かに速い解法が存在する。しかもDPもbit全探索も要らない(代わりにより高度なアルゴリズムと考察を要するが)。 本記事ではその解法の方針と実装例について述べようと思う。 概要 略…

ABC113 解説

A. Discount Fare (100) 問題リンク 概要 A駅からB駅を結ぶ運賃円の電車と、B駅からC駅を結ぶ運賃円のバスがある。 バスの運賃が半額のとき、A駅からC駅まで移動するのにかかる運賃の総額を求めよ。 制約 は偶数 解説 を出力すればいい。 が偶数なので、切り…

AtCoderで黄色になるまでにやったこと

AtCoderを始めてから11ヶ月、ついにレーティングが黄色になりました。年内は厳しいと思っていたので、自分でもとても驚いています。 というわけで恒例の「なるまで記事」を書くことにしました。前回の「青になるまで記事」は自分でもまとまりがないなぁと思…

ARC089-D 「Checker」 (500)

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

ARC089-C 「Traveling」 (300)

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

SoundHound 2018 Masters 本戦-B 「Neutralize」 (400)

B 「Neutralize」 (400) なんか悔しい。 問題リンク 概要 個の要素からなる数列がある。これに以下の操作を好きなだけ行う。 連続した個を選び、それらをすべて0にする。 この操作を行った後の、数列の総和の最大値を求めよ。 制約 解説 まず考えたのが貪欲…

AGC005-B 「Minimum Sum」 (400)

AGC005-B 「Minimum Sum」の解説。

AGC005-A 「STring」 (300)

AGC005-A 「STring」の解説。

ARC101-C 「Candles」 (300)

ARC101-C 「Candles」の解説。