Mister雑記

競プロやります。

TopCoder SRM763 Medium 「RootItRight」

SRM

TopCoder SRM763 Medium 「RootItRight」

TopCoder SRM763 Easy 「CutCutCut」

SRM

問題 の正方形がある。 以下の形式からなる個のクエリに答えよ。 クエリはの2点からなる。 2点は正方形の頂点を除く、異なる辺上にある。 正方形にこの2点を結ぶ線分を加えたとき、正方形がいくつの領域に分割されるか求めよ。 ここで加えられた線分は以降の…

AOJ 1620 「論理式圧縮機」

AOJ

onlinejudge.u-aizu.ac.jp 問題 以下の文法からなる論理式が与えられる。 <E> ::= 0 | 1 | a | b | c | d | -<E> | (<E>*<E>) | (<E>^<E>) ここで-、*、^はそれぞれnot、and、xorに当たる。 与えられた式と同値な論理式で、最短のものの長さを求めよ。 制約 論理式の長さは以下</e></e></e></e></e></e>…

AOJ 1619 「弁当作り」

AOJ

onlinejudge.u-aizu.ac.jp 問題意訳 長さのbit列が個与えられる。 全体のXORがとなるような部分集合の、要素数の最大値を求めよ。 制約 考察 あることに気づけるかが鍵となる問題。 それを言ってしまうと終わりなので、まだちゃんと考えてない人は考えてから…

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

Educational Codeforces Round #66 - E 「Minimal Segment Cover」 [???]

codeforces.com 問題 個の区間]が与えられる。このとき、以下の個のクエリに答えよ。 クエリは]で与えられる。 ]を上の区間で被覆できるか判定せよ。 できるなら被覆するのに必要な区間の数の最小値を出力せよ。 制約 考察 クエリ]を1つ固定して考える。 ま…

Codeforces Round #563 (Div. 2) - E 「Ehab and the Expected GCD Problem」 [2500]

codeforces.com 問題 長さの順列に対して、を以下のように定める。 に出現する整数の個数をとする。 長さの順列のうち、が最大となるようなものの個数を求めよ。 制約 考察 以下の整数で、素因数分解したときに指数の総和が最大となるようなものをとする。 …

Codeforces Round #563 (Div. 2) - D 「Ehab and the Expected XOR Problem」 [1900]

codeforces.com 問題 与えられた整数に対し、以下を満たす数列を構築せよ。 任意の空でない連続部分列について、そのXORはでもでもない。 長さが最長である。 制約 考察 最長の長さ まず解となる数列を1つ取る。この数列は極大である、すなわち1つでも整数を…

AOJ 2438 「YAML」

AOJ

onlinejudge.u-aizu.ac.jp 問題 階層構造をもつオブジェクトを表現する、「YAML」という記法がある。 YAMLの形式に基づいたオブジェクトのデータが与えられるので、それをパースして指定されたプロパティを検索せよ。 今回与えられる入力は、BNF記法で以下の…

AOJ 2297 「Rectangular Stamps」

AOJ

onlinejudge.u-aizu.ac.jp 問題 個の長方形をしたスタンプがあり、個目の大きさはである。 の全てのマスが白いグリッドに、これらのスタンプを押していく。 インクの色はRGBの3種類。 スタンプにインクを付けて押すと、押された部分の色が全て更新される。 …

AOJ 2222 「Alien's Counting」

AOJ

onlinejudge.u-aizu.ac.jp 問題 ※ 強い言い換えをしているので、原文を読みたい方は上のリンクをご参照ください。 頂点辺の有向グラフが与えられる。このグラフの各頂点に黒か白を塗りたいが、以下の制約を満たさなければならない 各辺について、が黒ならも…

AOJ 2306 「Rabbit Party」

AOJ

onlinejudge.u-aizu.ac.jp 問題 頂点辺の重み付き無向グラフが与えられる。頂点集合を1つ取ったとき、そのスコアを以下のように定義する。 頂点集合からなる誘導部分グラフを取る。 各頂点について、接続している辺の重みの最小値を求める。 辺が張られてい…

AOJ 2425 「全探索お姉さんの休日」

AOJ

onlinejudge.u-aizu.ac.jp 問題 あなたと全探索お姉さんは正六角形が敷き詰められた空間のマスにいる。ここから毎分隣接するマスへの移動を繰り返すことで、マスに行きたい。 ただし障害物が置かれているマス、座標の絶対値がより大きい、または座標の絶対値…

AOJ 2742 「選挙活動」

AOJ

onlinejudge.u-aizu.ac.jp 問題 平面上に、個の多角形状の障害物と人の有権者がいる。平面上の適当な位置に立つことで、障害物に遮られることなく見える有権者の数を最大化せよ。 厳密には、あなたと有権者を結ぶ線分で、全ての障害物と交差しないものの数を…

AOJ 2741 「インビジブル」

AOJ

onlinejudge.u-aizu.ac.jp 問題 AさんとBさんがそれぞれ枚、枚のカードの山を使ってゲームを行う。各プレイヤーは自分と相手のカードの山の中身を把握している。 カードには「得点カード」と「妨害カード」があり、得点カードには正の整数が書かれている。ま…

ABC126-E 「1 or 2」 (500)

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

ABC126-F 「XOR Matching」 (600)

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

Codeforces Round #541 (Div. 2) - E 「String Multiplication」 [2200]

codeforces.com 概要 文字列に対して、文字列同士の「掛け算」をと定義する(は文字列の結合)。 そして文字列の「美しさ」を、「1種類の文字からなる最長連続部分列の長さ」として定義する。 個の文字列が与えられるので、文字列の美しさを求めよ。なお、解は…

ARC066-D 「Xor Sum」 (600)

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

ARC080-E 「Young Maids」 (800)

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

Codeforces Round #541 (Div. 2) - D 「Gourmet choice」 [2000]

codeforces.com 概要 とあるグルメがレストランで1日目に種類、2日目に種類の料理を頼んだ。 そしてグルメは各について、1日目の品目と2日目の品目の料理を 1日目の方が美味しかった 2日目の方が美味しかった 同じくらい美味しかった のいずれかで評価した。…

自作問題 「Stone Cleaner」

misteer.hatenablog.com 上の記事を書いている際に、以下のような問題に直面した。 に対して、「異なる2要素からずつ引く」という操作を考える。この操作を繰り返すことでを全てにできるとき、は「良い数列」である。 この問題を一般化したらどうなるか?と…

Codeforces Round #512 (Div2) - E 「Vasya and Good Sequences」 [2100]

codeforces.com 概要 正整数列に以下の操作を何度か施すことで、全てのXORを取った値がになるようにできるとき、を「良い数列」と呼ぶことにする。 要素を任意に選ぶ。 を2進数表記し、任意の2つのbitを交換する。 長さの正整数列の連続部分列で、「良い数列…

Codeforces Round #514 - E 「Split the Tree」 [2400]

codeforces.com 概要 頂点が根であるような頂点根付き木が与えられる。各頂点には重みが割り振られていて、頂点の重みはである。 この木を、以下の条件を満たすいくつかのパスによって分割する。 1つの頂点はちょうど1つのパスに含まれる。 各パスについて、…

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 概要 数直線があり、からの各点には空の箱が置かれている。 すぬけ君はこの数直線上を、以下のルールに従って移動をする。 ]の区間のみを移動する。 始点と終点の座標…

6日目 Codeforces Global Round 1

codeforces.com ABCDEの5完、薄橙に復帰。 D. Jongmah [2200] Problem - D - Codeforces 概要 以下の正整数が書かれた個の牌がある。個目の牌にはと書かれている。 このとき、以下の2種類の3枚組を合わせて最大何組作れるか求めよ。ただし1つの牌は1つの組に…