Mister雑記

競プロやります。

MisterのJAG夏合宿2019参加記

2019年のJAG夏合宿に行ってきました。

ARC100-E 「Or Plus Max」 (700) 高速ゼータ変換解法

ARC

ARC100-E 「Or Plus Max」 (700) の再実装。

高速ゼータ・メビウス変換

高速ゼータ・メビウス変換の自分なりの解説。

ARC100-E 「Or Plus Max」 (700)

ARC100-E 「Or Plus Max」 (700)

ARC095-E 「Symmetric Grid」 (700)

atcoder.jp 問題 のアルファベットからなるグリッドが与えられる。 この行と列を自由に入れ替えることで、点対称にできるか判定せよ。 制約 考察 脳死でをやりたくなるが、当然それは許されない。 そこで行の並び方だけ全列挙することにする。すると、「互い…

JSC2019予選 - D 「Classified」 (600)

JSC2019予選 - D 「Classified」 (600)

JSC2019予選 - C 「Cell Inversion」 (500)

JSC2019予選 - C 「Cell Inversion」 (500)

AGC036-A 「Triangle」 (400)

AGC

AGC036-A 「Triangle」

TCO2019 Round3B Medium 「PrefixComposite」(450)

SRM

TCO2019 Round3B Medium 「PrefixComposite」

TCO2019 Round3B Easy 「TwoLadders」 (250)

SRM

TCO2019 Round3B Easy 「TwoLadders」 (250)

TopCoder SRM763 Medium 「RootItRight」

SRM

TopCoder SRM763 Medium 「RootItRight」

TopCoder SRM763 Easy 「CutCutCut」

SRM

community.topcoder.com 問題 の正方形がある。 以下の形式からなる個のクエリに答えよ。 クエリはの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種類の文字からなる最長連続部分列の長さ」として定義する。 個の文字列が与えられるので、文字列の美しさを求めよ。なお、解は…