ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

プログラミング

AtCoder LibraryのLazy Segtreeのチートシート

AtCoder LibraryのLazy Segtreeの使い方 - ARMERIA こちらの記事でAtCoder LibraryのLazy Segtreeの使い方を説明しましたが、コンテスト中に読んでられっか!みたいな時のためにコピペで使えるチートシートをまとめます。整数列に対する、以下の組み合わせ6…

AtCoder LibraryのLazy Segtreeの使い方

AtCoder Libraryが遅延伝播機能を持つセグメント木 atcoder::lazy_segtree を提供しているものの、何か渡すものいっぱいあるしドキュメントは数学用語だらけだしよく分からん!みたいな人向けの記事です。 問題を解いていて、セグメント木に必要な機能(区間…

Educational Codeforces Round 11 E. Different Subsets For All Tuples

お題箱より。 Problem - E - Codeforces 公式解説より楽な解法があるのでそっちを紹介します。記事最後に、リクエストにあった公式解説の補足についても説明します。 問題概要 整数列 に対して、 を「 の部分列(連続でなくても良い)として登場する長さ 以…

キーエンス プログラミング コンテスト 2020 D - Swap and Flip

お題箱より。 D - Swap and Flip 解法 この問題のように「操作する場所を選んで、決められたルールに従って操作する」ということを繰り返す問題では、1回目の操作の選択、2回目の操作の選択…といった分岐パターンを直接探索していくのは非常に大変です。操作…

AtCoder Beginner Contest 178 F - Contrast

F - Contrast 解法が色々ある問題。シンプルで実装も楽な解法1と、私が本番で解いた解法2を証明付きで紹介します。前者のほうが断然オススメ。 解法1 まず 合計で 個を超える値が存在する場合、どのように並べても となる箇所が存在してしまいます。この場合…

Codeforces Round #670 (Div. 2) E. Deleting Numbers

Problem - E - Codeforces 問題概要 インタラクティブ問題である。 まず正整数 が与えられる。ジャッジは 以上 以下の整数 を持っている。また集合 があり、初期状態では である。 以下のクエリを合計 回まで投げることができる。 の値を特定し、Cクエリで解…

Codeforces Round #669 (Div. 2) D. Discrete Centrifugal Jumps

お題箱より。 Problem - D - Codeforces 問題概要 本のビルがあり、 番目のビルの高さは である。 ビル からビル へは、 かつ以下の3条件のいずれか1つを満たす場合にジャンプして移動することができる。 :ビル は隣り合っている。 :間にあるビルが全て、…

POJ NO.3686 The Windy's

お題箱より。蟻本に載っている問題です。 3686 -- The Windy's ※ライブラリをC++98に対応させる気になれなかったのでACコードはありません。蟻本に載っているのでそちらを… 問題概要 個のおもちゃ工場があり、 個のおもちゃの注文を受けた。おもちゃ を工場 …

AtCoder Library Practice Contest I - Number of Substrings

お題箱より。 I - Number of Substrings 解法 ※この問題における文字列 の部分文字列とは、 の連続な部分を取り出した文字列であることに注意してください。慣習的に、「部分列」と書くと連続とは限らない取り出し方、「部分文字列」と書くと連続な取り出し…

AtCoder Regular Contest 092 C - 2D Plane 2N Points

お題箱より。 C - 2D Plane 2N Points 以前の自分が解法の正当性を理解するのにすごく悩んだ問題で、印象深いです。 解法 考察 2次元の座標点を扱う際には「平面走査」というテクニックがよく使われます。これは座標点をある一方の座標、例えば 座標でソート…

Educational Codeforces Round 94 F. x-prime Substrings

Problem - F - Codeforces 自分の解法が非想定解っぽいので書き残しておきます。 問題概要 を正整数とする。 の数字からなる文字列が -primeであることを、以下の2つをともに満たすことと定義する。 全ての数字の和が である。 任意の連続部分列について、そ…

DDCC 2016 本選 C - 特別講演「括弧列と塗り分け」

お題箱より。 C - 特別講演「括弧列と塗り分け」 解法 この問題を考えるにあたって重要なのが、正しい括弧列を根付き木と対応づけることです。 それぞれの括弧1組ずつを頂点とみなします。そしてその括弧の1つ外側を囲っている括弧を親とみなすように辺を張…

yukicoder No.1067 #いろいろな色 / Red and Blue and more various colors (Middle)

お題箱より。 No.1067 #いろいろな色 / Red and Blue and more various colors (Middle) - yukicoder 解法 箱を並び替えても答えが変わることはないので、 の昇順に並べておきます。 各箱から玉を1個ずつ取り出し、ある1つの色 の玉がちょうど 個選ばれる場…

University of Aizu Programming Contest 2014 (AOJ 1548) Yu-kun Likes a Directed Graph

お題箱より。 Aizu Online Judge 解法 重み の負辺を足してできるだけ重み合計が大きい( に近い)負閉路を作りたいので、与えられたDAGについて「1本以上の辺で構成されるパスであって、重み合計が 未満であるもののうち一番大きいものの重み」が分かれば良…

University of Aizu Programming Contest 2012(AOJ 1508)RMQ

お題箱より。 Aizu Online Judge 解法 1点更新と区間最小値取得ならセグメント木でできますが、シフト操作が厄介です。シフト操作は「数列から要素を1つ削除する」「その要素を数列の別の場所に挿入する」とみなすことができますが、この操作によって間に存…

AtCoder Beginner Contest 170 E - Smart Infants

お題箱より。実装方法に関するリクエストだったので実装中心で書きます。 E - Smart Infants 解法 解法としてはシミュレーションです。園児が移動したときに、どのようなデータを管理しておけば効率的に答えを更新できるかを考えます。 今回は以下のようなデ…

CPSCO2019 Session3 F - Flexible Permutation O(N^2)解法

お題箱より。 解法が知りたいというリクエストだったので考えてみました。 F - Flexible Permutation 解法 後に扱うDPの都合上、個人的にはインデックスよりも値に注目したほうが理解しやすいので、条件を値中心の言葉に言い換えます。 であるような値 を「…

Educational Codeforces Round 92 F. Bicolored Segments

お題箱より。 Problem - F - Codeforces 問題概要 個の閉区間 が与えられ、それぞれは赤または青のいずれか1色に塗られている。 「異なる色の2つの区間が共有点を持ってはいけない」という条件のもとで、これらのうちできるだけ多くの区間を選びたい。選ぶ個…

エイシング プログラミング コンテスト 2020 F - Two Snuke

F - Two Snuke 公式解説とは違う解法です。 解法 のときは答えは なので、 とします。 まずは 解法を まず答えを で求める方法を考えます。 の値を として、これを全通り試しましょう。そうすると、この を つに分ける分け方が 通りあります。 個並んだボー…

Codeforces Round #654 (Div. 2) E2. Asterism (Hard Version)

Problem - E2 - Codeforces 問題概要 長さ の数列 と素数 が与えられる。まず、以下の問題を考える。 整数 が与えられる。 を並び替えた順列 であって、全ての について が成り立つようなものは何通りか? この問題の答えが の倍数とならないような を全て列…

Codeforces Global Round 9 E. Inversion SwapSort

Problem - E - Codeforces 問題概要 長さ の数列 が与えられる。この数列についてインデックスのペア が かつ を満たすとき、このペアは転倒していると呼ぶ。 与えられた について転倒している全てのペアを並べた列であって、「列に並んでいる順に、ペアが示…

AtCoder Grand Contest 043 C - Giant Graph

お題箱より。 C - Giant Graph この問題は数ヶ月前に「なぜこの発想を思いつけるのか分からない」というリクエストをもらっていて、私にも分からなかったので記事を書けずにいました。でしたが、(同じ人が違う人かは分かりませんが)2つ目のリクエストをも…

Introduction to Heuristics Contest 参加記録

Introduction to Heuristics Contest - AtCoder 33位でした。 戦略 焼きなまし法を選択しました。 理由は、問題の性質として解の局所改善がやりやすく、スコアの差分計算を高速化して大量に回せそうだと考えたからです。対して、1手の変更がその後の展開を大…

Codeforces Round #653 (Div. 3) E2. Reading Books (hard version)

Problem - E2 - Codeforces 問題概要 冊の本があり、本 は読むための所要時間 、アリスがその本を好きかどうか 、ボブがその本を好きかどうか で特徴付けられる。 冊の本からちょうど 冊の本を以下の条件を満たすように選ぶとき、その合計所要時間の最小値と…

yukicoder No.1100 Boxes

No.1100 Boxes - yukicoder 解法 まずボールが1つも入っていない箱の数を固定します。これを とすると、その選び方は 通りです。 その上で、残りの 個の箱全てにボールが入るような場合の数を求めます。これは包除原理を用いて と求めることができます。 先…

AtCoder Beginner Contest 171 F - Strivore

F - Strivore 解法 文字列 の長さを とします。また最終的に出来上がる文字列を と表記します。 の長さは になります。そのうち元々あった文字と追加した文字の場所の割り当て方が 通りで、追加した文字の種類が 通りで…とやりたくなりますが、これでは最終…

AtCoder Grand Contest 046 C - Shift

C - Shift 解法 に含まれる 0 の個数を 、1 の個数を と書くことにします。 を、0 で区切られた 個のエリアに分割します。 図に示すように、エリア に含まれる 1 の個数を とし、エリア を含むそれ以前に含まれる 1 の個数を とします。 本問題の操作は、1 …

AtCoder Grand Contest 046 B - Extension

B - Extension 解法 まず以下のようなDPを考えてみましょう。 本問題の操作によって、縦 行、横 列になるまで操作してできる盤面の数 このDPで「上側に行を足し、その1つを黒く塗る」遷移と「右側に列を足し、その1つを黒く塗る」遷移をすれば良さそうですが…

Educational Codeforces Round 58 G. (Zero XOR Subset)-less

お題箱より。 Problem - G - Codeforces 問題概要 長さ の数列 が与えられる。これをいくつかの区間(連続部分列)に分割する。この分割は以下の条件を満たす必要がある。 全ての要素はちょうど1つの区間に属する。 区間のうち1つ以上のものをどのように選ん…

AtCoder Beginner Contest 170 F - Pond Skater

F - Pond Skater 解法 1ターンに1マスの移動であればグリッド上のBFSで解けますが、今回は1ターンに マスまで動くことができます。これをそのままBFSで処理すると1つのマスから遷移可能なマスが最大 個になり、全体計算量 になって間に合いません。 具体的に…