X - Tower 問題概要 N個のブロックがあり，i番目のブロックは重さ$ w_i $，価値$ v_i $であり，そのブロックには重さが計$ s_i $までのブロックを載せることができる． これらのブロックを1列に積み上げてタワーを作るとき，タワーの価値の最大値を求めよ． …

A - Affiches 問題概要 H×W の大きな紙 1 枚と，A×B の小さな紙 2 枚がある． 小さな紙 2 枚を大きな紙の上にはみ出さないように貼る．このとき，小さな紙同士が重なっていても構わない． 小さな紙の左上の座標が [0, H-A]×[0, W-B] 上の独立な一様分布に従…

F - Pass 問題概要 n人のすぬけ君が1列に並んでいて，両手にボールを持っている．両手のボールの色は青2つ，赤2つ，赤青1つずつのいずれかのである． 以下の操作を2n回繰り返した際にできるボール色の列のパターン数を998244353で割った値を求める． 操作: n…

E - 迷路 問題概要 N行M列 ($ N, M \leq 1000$) のグリッド上をロボットがSからGまで移動するのに最短何秒かかるか求める． ただし，1マス上下左右に動くのにかかる時間は1秒で，毎秒動ける方向が決まっている．動ける方向は長さk ($ k \leq 100000$) の文字…

C - Lexicographic constraints 問題概要 $ N \leq 2 \times 10^5 $個の文字列があり，$ i$番目の文字列の長さが$ a_i (\leq 10^9)$であるとき，全ての文字列を辞書順にするために必要な最小の文字の種類数を求める． 解法概要 二分探索で答えの候補を決めて…

E - Negative Doubling 問題概要 N個の正の整数値からなる数列$ A_1, A_2, \cdots, A_N$について，1つの要素を-2倍する操作を繰り返す． このとき，数列が非減少列となる最も少ない操作回数を求める． $ 1 \le N \le 2\times 10^5 $, $ 1 \le A_i \le 10^9 $…

C - LCM 111 問題概要 1をA個並べた数と1をB個並べた数の最小公倍数をMで割った数を求めよ． $ A,B \le 10^{18} $ $ 2 \le M \le 10^9 $ 解法概要 公式解説にならい，1を$ n$個並べた数を$ \mathit{one}(n)$とする． また，以下のメモでは$ M$で割った剰余を…

B - Garbage Collector 問題概要 ゴミ (ゴミの数$ N \leq 2 \times 10^5 $) を拾う・運ぶ・捨てるエネルギーが以下のように定められるとき，全てのゴミを捨てるまでの消費エネルギーを最小化せよ． i番目のゴミはそれぞれ$ x_i (\leq 10^9)$の位置にある． k…

FizzBuzz | Aizu Online Judge 問題概要 FizzBuzzで出力する文字を連結したもの (この問題ではFizzBuzz Stringと呼ぶ) のうち，$ s ( s \leq 10^{18} ) $ 文字目から20文字分を出力する． 解法概要 1からnまでの分のFizzBuzzを出力したときのFizzBuzz String…

G - Mixture Drug 問題概要 N (<=40) ノードM辺の無向グラフについて，最大独立集合を求める． 解法概要 懇切丁寧な解説スライドに頼りきってしまったが，復習のため自分なりにDPの遷移のお気持ちなど噛み砕いてみる．……と思ったが，解説スライドに全部書い…

Problem - E - Codeforces 問題概要 Nノードの無向木が与えられる．辺 (p,q) および辺 (q,r) が存在するようなp,q,rについて，pとrの間に辺を張る． あらゆるノードのペア間の最短距離の総和を求める． ただし辺のコストは全て1とする． 解法概要 辺を追加す…

Problem - C - Codeforces 問題概要 2×nの大きさの配列aが与えられる．0-indexedでi番目にa[y][x]を訪れるとa[y][x]×i点を得る．y=0,x=0からスタートし，配列中のすべての要素をちょうど1回ずつ訪れるときに得られる得点を最大化せよ． 解法概要 わりかし面…

C - Ants on a Circle 問題概要 長さL円周上を，N個の点が速さ1でT秒間移動する．それぞれの点は0秒の地点で円周上の座標X[i]におり，W[i]の方向 (1: 時計回り， 2: 反時計回り) に動く．ただし2つの点が衝突したとき，2つの点は速さを変えず反対方向に動き…

E - Symmetric Grid 問題概要 それぞれのマスにアルファベットの小文字が入った，H×W (H, Wは12以下) のマス目が与えられる． 行の交換と列の交換を繰り返し，このマス目を点対称にできるか判定する． 解法概要 行の交換と列の交換の操作の順番は変えても問…

City Merger | Aizu Online Judge 問題概要 長さ20文字以下の都市の名前が最大14個与えられる．これらのすべてを部分文字列として含むような文字列の長さを求める． 解法概要 与えられた都市の名前の個数をnとする．また，都市の名前の長さの最大値をlとする…

Flipping Parentheses | Aizu Online Judge セグ木の練習がしたい + 括弧列の問題がすきということで難しい問題にチャレンジ． 問題概要 長さNのバランスの取れた括弧列が与えられる．これに対し，Q個のクエリが与えられる．クエリは以下の内容である． 括弧…

B - Neutralize 問題概要 N個の整数値からなる数列$ b = \{ b_1, b_2, \cdots b_n \} $について，連続するK個の要素を全て0にするという操作を好きなだけ繰り返して良いとき，数列に含まれる値の和を最大化する． ($ 1 \leq K \leq N \leq 10^5$) 解法概要 …

Discrete Speed | Aizu Online Judge 問題概要 N$ ( N\leq 30)$ノードMエッジの多重辺のない無向グラフ上を移動してスタートノードSからゴールノードGを目指す．SからGに行くまでの最短時間を求めたい． エッジにはそれぞれ制限速度c$ ( c\leq 30)$と距離d$ …

Carrot Tour | Aizu Online Judge 問題概要 合計移動距離がr以下(0 < r < $ 10^4$)になるように20個以下の都市を回る． 都市を訪れる回数を最大化せよ． ただし，進む向きを一度に$ \theta$度より大きく変えることはできない． 解法概要 都市が20個以下とい…

問題概要 通路が"."，壁が"#"で表される最大50×50の迷路がある．スタート地点$ (r_1, c_1) $からゴール地点$ (r_2, c_2) $に行くまでの所要時間を求める． ただし，"."のある地点から4近傍の"."に移動するのに1秒かかる．また，今いる"."と同じ行または同じ…

問題文原文 問題概要 ミサイル保有国がn国ある．それぞれの国はm個のミサイルを保有している．各ミサイルはcapability cをもつ． 各国のミサイルのcapabilityの和の差をd以下に保ったまま，全てのミサイルを廃棄できるかを答えよ． ただし，各国はミサイルを…

E - Meaningful Mean 問題概要 長さNの整数列$ a=\{a_1, a_2, \cdots, a_N \} $の空でない連続する部分列について，算術平均がK以上のものの数を求める． 解法概要 「算術平均がK以上の部分列」が満たす条件を変形してみる． $$ \begin{align} \frac{1}{r-l+…

E - Range Minimum Queries 問題概要 長さNの数列Aに対して，長さKの連続する部分を選びK個の要素の中で最小のものを削除する操作をQ回繰り返す． 削除される値の最大値と最小値の差を最小化する． 解法概要 Nはたかだか2000なので，最小値を決めうちしても…

E - Sorted and Sorted 問題概要 1からNまでの数字が書かれた，黒・白のボールがある． この2N個のボールを，それぞれの色について数字が昇順になるように並べ替える． 隣同士のボールの交換を繰り返して並べ替えを行うとき，最小の交換回数を求める． 解法…

A - アナログ時計 問題概要 $ h $時$ m $分$ s $秒からスタートして，分針と秒針，時針と分針が重なった回数がそれぞれ$ C_1 $回，$ C_2 $回であるときの最小・最大の経過秒数を求める． 解法概要 $ C_1 \leq 10000 $なので，愚直に針の動きをシミュレートし…

codeforces.com 問題概要 二次元座標上に直線 解法概要 点と点が1回遭遇するたびに2つの点の経験値が1ずつ増えるので，全体の経験値の和は2増える．すなわち，求めるべき全ての経験値の和は点同士の遭遇回数の2倍の値である．また，全ての点は等速直線運動し…

問題概要 ちょっとまとめるのが面倒なので，問題文原文を見てください (手抜き) 解法概要 長方形の領域になっている部分を貪欲に取り除いていく．取り除かれた長方形の領域は，次の長方形を探す際に長方形の領域として使って良い (使わなくても良い)． 長方…

問題概要 駅$ 1 $から駅$ N $までの$ N $個の駅に対し，$ M $個の路線が存在する． $ i $番目の路線は駅$ p_i $と駅$ q_i $を相互に結び，会社$ c_i $によって運営されている． 駅$ 1 $を出発地，駅$ N $を目的地とするとき，異なる会社の路線への最小の乗り…

問題概要 $ n $要素からなる数列$ a = \{ a_1, a_2, \cdots, a_n \} $が与えられる．$ a_i $は，テレビシリーズのシーズン$ i $のエピソードが第$ a_i $エピソードまで存在することを表す． シーズン$ i $のエピソード$ j $とシーズン$ j $のエピソード$ i $…

ブログ記事に書くと定着度が高まることがわかったので，これからは解いた問題を積極的に記事にしていこうと思う． 問題概要 $ N $要素からなる数列$ a = \{ a_1, a_2, \cdots, a_n \} $，$ b = \{ b_1, b_2, \cdots, b_n \} $に対し，以下の操作を行う． あ…