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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

D - Knapsack Queries on a tree Editorialと同じ解法で解いたのでそっちを書きます。クエリごとに独立に解く方法もあって、そっちで解いた人のほうが多そうな印象です。 解法 が十分大きいという前提で解説をします。また扱う重みの最大値を 、最大深さの半…

Problem - F - Codeforces 問題概要 頂点 辺の重み付き無向グラフが与えられる。グラフは単純かつ連結である。 正整数 について を「頂点 から始まってちょうど 回移動する経路の、通った辺の重み合計の最大値」と定める。この経路では同じ辺や頂点を複数回…

C - Range Set 解法 必要十分条件への言い換え ある01文字列が与えられた時に、それが操作によって生成可能であるかを判定することを考えます。 ここで今回のように「塗り潰す」系の操作の場合、「判定したい文字列から逆順で操作を行い、初期状態に戻せるか…

Problem - F1 - Codeforces 問題概要 ※解説の都合上、0-indexedで表記します。 正整数 が与えられる。長さ の非負整数列 が以下の性質を満たす時、これを「良い数列」であると呼ぶ。 に1つ以上含まれる任意の正整数 について、 かつ かつ であるインデックス…

お題箱より。 D - 大ジャンプ 解法 まずは計算しやすいようにいくつか前処理をします。 ゴールまでの 軸方向それぞれの距離を で割ることで「正の方向にジャンプ○回分」という値に変換します。ここで割り切れない場合、答えは です。今後は で割った後の値を…

Topcoder 初めてのTopCoderマラソンマッチ。34位/68人とちょうど真ん中の成績でした。 問題概要 のグリッドの各マスが 色のうちいずれかで塗られている。 人のダンサーがいて、 単位時間かけてグリッド上を移動する。このとき各マスが1回踏まれるたびに、周…

Problem - F - Codeforces 問題概要 長さがともに の数列 が与えられる。数列 に対して、以下の操作を 回以上好きな順番で行って に一致させたい。 数列 を反転する。 数列 を、 の先頭からの累積和を並べた数列に置き換える。 これが可能かどうか判定し、可…

A - Pay to Win 公式解説、丁寧だけど英語なんですよね…だいたいそのまま訳す感じの解説になってしまいそうですが許してください。 解法 操作を限定できる形に持ち込む いきなりですが、操作を逆から考えます。 気持ちとしては、 からの操作を考えるとどの遷…