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

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

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

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つの部分文字列が一致してはならない…