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

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

お題箱より。 Problem - D - Codeforces 問題概要 行 列のグリッドが与えられ、各マスには整数（非負とは限らない） が書かれている。 左上のマスからスタートし、隣り合うマスを辿って右下のマスまで移動する経路であって、同じマスを複数回通るものがない…

お題箱より。 Problem - F - Codeforces 問題概要 人のプレイヤーに 枚ずつのカードを配る。 枚のカードそれぞれにかかれている数字 と、プレイヤー が好きな数字 が与えられる。 それぞれのプレイヤーは、配られたカードのうち好きな数字が書かれたものが …

お題箱より。 Problem - D - Codeforces 問題概要 長さ の整数列 が与えられる。この数列に以下の操作を0回以上行ってよい。 ある連続部分列 を選び、それら全てをその中央値で置き換える。ただしこの問題において、 個の値の中央値は小さい方から 番目の値…

CodinGame Spring Challenge 2020に参加して、Legendリーグ57位でした！ 対戦動画をTwitterで見て、何となく面白そうだなと思って参加したらドハマリしました。睡眠時間と休日とCodeforcesのコンテスト2回分が犠牲になりましたが、Legendリーグに進出するこ…

F - . (Single Dot) 解法の理解というよりは実装慣れのほうが重要な問題だと思います。末尾につけているACコード例と対応させながら読んでいくといいかもしれません。 解法 図における座標軸は問題文に従い、北を上にして図示するようにします。一般的なXY平…

E - Colorful Blocks 解法 「隣り合うブロックの組であって同じ色で塗られている組」がちょうど 個あるとして、 についてそれぞれ求めた場合の数を合計することで答えを求めます。 ブロックは全部で 個なので、ブロックが隣り合っている箇所は 箇所です。こ…

F - Bracket Sequencing 解法 「正しい括弧列」について この問題だと単に括弧列という言葉が使われていますが、どちらかと言うと「正しい括弧列」みたいな呼ばれ方をされることが多いです。 正しい括弧列の条件は、言葉で書くと 開き括弧と閉じ括弧の数が等…

No.1051 PQ Permutation - yukicoder ※当初の公開時点での解説およびリンク先コードが誤っていたため、修正しました。 解法 ※以下の解説中で「辞書順で1つ進める」と書いた時には、「もし進められない（既に辞書順最大である）ときには -1 を出力して終了す…

お題箱より。 Problem - G - Codeforces Editorialのコメント欄に色々別解が書かれているのですが、この記事はEditorial本文の解法を扱います。 問題概要 長さ の整数列 が与えられる。この数列に対する操作が 個与えられ、これを順番に施す。 操作 ： であ…

AtCoder Beginner Contest 165 - AtCoder 解法 得点の計算方法が面倒で、賢い解き方はなかなか思い浮かびません。制約が小さいことに注目して全探索の方針を考えます。 制約上の最大値である で考えます。数列 としてあり得るものは、単純に見積もると 以上 …

お題箱より。 Aizu Online Judge 解いてなかったのでこのリクエストを見て解きました。 解法 言い換えを重ねる 全ての点の個数を と表記することにします。 「全ての点集合について、その集合に含まれる三角形を数えて合計する」を、「全ての三角形をなす3点…

お題箱より。 Problem - C - Codeforces 問題概要 頂点の木が与えられる。この木の辺に の値を1つずつ割り振ることを考える。 異なる2頂点 に対して を「 間パスに含まれる辺の値として登場しない最小の非負整数」と定義する。そして値の割り振り方のスコア …

お題箱より。 A - Dividing a String 貪欲とDPどちらを書こうか迷いましたが、貪欲解法のほうで書きたいと思います。 問題概要 文字列 が与えられる。この をできるだけ多くの部分文字列に分割したい。ただし、隣り合う2つの部分文字列が一致してはならない…

お題箱より。 Problem - F - Codeforces 問題概要 整数 と、開き括弧・閉じ括弧からなる文字列 が与えられる。長さ の正しい括弧列であって、その連続部分文字列として をどこかに含むものの個数を で求めよ。 制約 解法 DPを立てる 正しい括弧列の問題は、(…

お題箱より。 F - Select Half 前置き リクエストでは「そもそもなぜDPを思いつくのか」を知りたいという声をもらったのですが…この点は非常に難しいと思っています。というのも、私の場合はDPで最終的に解けない問題であっても考察途中で「DPできないか？」…

Problem - F - Codeforces 問題概要 長さ の順列 がある（与えられない）。この順列に対して、 それぞれに対して以下のように計算される 個の数列が与えられる。 各 に対して、 なる を選び、 をソートした数列。 ここで 個の数列は並べ替えられた順番で与え…

F - path pass i 公式解説とは違う方法で、計算量は であまり良くないのですが、私が解いた解法をまとめておきます。 解説 「通らないもの」を数える 頂点数が であるとき、単純パスの総数は 個です。色 について解く時には、この総数から「色 の頂点を通ら…

お題箱より。けっこう難しかった… Problem - G - Codeforces 問題概要 数列 が与えられる。この数列の長さ 以上の部分列が「free from monotone triples」であるということを、「その部分列からさらに長さ の部分列をどのように取っても、広義単調増加にも広…

お題箱より。 No.1029 JJOOII 3 - yukicoder 解法 計算量などの表記のため、 と置きます。この問題の制約では です。 作りたいレベル のJOI文字列を と表記します。文字列のインデックスは0-indexedで表記します。 を前から順に作っていく、以下のようなDPを…

お題箱より。 Problem - F - Codeforces リクエストに沿って、正当性の説明をします。ちゃんと証明を組むとなかなか大変でした… 問題概要 要素の整数列 と整数 が与えられる。 1回の操作で、この数列に以下のいずれか1つを行うことができる。 操作 ： の最小…

Problem - E1 - Codeforces E1しか解けていないので、E1しか通らない解法を書きます…。この他にも色々な解法があるっぽい？ 問題概要 個の非負整数 が与えられる。また非負整数 が与えられ、 である。 から任意個の要素を選ぶ選び方は全部で 通りある。選ん…

Problem - F - Codeforces 問題概要 正整数 が与えられ、集合 と定める。要素数2以上である の部分集合 について、 の値を「 に含まれる相異なる2要素 に対する の最大値」と定める。 に対して、要素数が である の部分集合 についての の最小値を求めよ。 …

F - Division or Substraction 解法 「 が で割り切れる時」「割り切れない時」で操作の種類が変わるので、 を で割った余りに注目してみましょう。 もし を で割った余りが でない場合には、 は 未満になるまで に置き換えられ続けます。つまり、この余りは…

Problem - D - Codeforces 問題概要 英小文字からなる文字列 が与えられる。この に以下の操作を繰り返して空文字列にしたい。 の連続する部分文字列であって、どの隣り合う文字も等しくないものを1箇所選ぶ。それを除去し、残った部分を結合する。 その最小…

この記事は元々ある問題のお題箱リクエストのために書いていたのですが、一般的にテクニックを紹介する記事＋その問題を例題として解説、という流れにすることにしました。 まれによく出題される、「セグメント木に行列を乗せる」とはどういうことか。多くの…

お題箱より。 D - パスタ (Pasta) 解法 ※実装に合わせて、0-indexedでの記述とします。最初の日は 日目です。 日目から順番にパスタの種類を決めていくことにします。ルールは「事前に指定された日のパスタの種類は決まっている」ことと「3日連続で同じパス…

F - Distributing Integers 解法 「頂点に整数を書く」だと少し図示しづらいので、代わりに「頂点番号の書いたボールを処理する順番に並べる」として考えることにします。 最初にボールを置く頂点を根付き木の根とします。まずは根を頂点 に固定して問題を解…

お題箱より。 Problem - D - Codeforces 問題概要 人の子供がいて の番号を持っている。以下の 個の操作についてそれぞれ、実行するかしないかを選ぶことができる。 区間 に属する子供に1個ずつキャンディを与える。 ここで整数 が与えられ、 個を超える操作…