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

問題文: E - Non-triangular Triplets Writer 解説: https://img.atcoder.jp/nikkei2019-2-qual/editorial.pdf 問題概要 $ 3N (N \leq 10^5)$ 個の整数 $ K, K+1, \cdots, K+3N-2, K+3N-1 (K \leq 10^9)$ から，$ N$個の三つ組$ (a_1, b_1, c_1), \cdots, (a…

問題: No.1001 注文の多い順列 - yukicoder writer 解説: yukicoder 問題概要 $1$ 以上 $N$ 以下の整数の順列 $p_1, p_2, ... p_N$ であって，以下の条件を満たすものの数を $10^9+7$ で割った余りを求めよ。 すべての $i (1 \leq i \leq N)$ について以下を…

問題: https://atcoder.jp/contests/abc156/tasks/abc158_f 公式解説: 解説 pdf 問題概要 $N ( \leq 18)$ 枚のカードがあり，左から $i$ 枚目のカードは表に $A_i (\leq 100)$，裏に$B_i (\leq 100)$ が書いてある。次の操作のみを行い，カードが左から右に…

問題: https://codeforces.com/contest/1272/problem/E 公式解説: https://codeforces.com/blog/entry/72132 問題概要 長さ $n (\leq 2 \times 10^5) $ の数列 $a_1, a_2, \cdots, a_n (1 \leq a_i \leq n) $ がある． この数列を使って，ある要素から別の要…

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

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

問題: https://codeforces.com/contest/962/problem/E 公式解説: https://codeforces.com/blog/entry/58869 問題概要 1次元の座標軸の上に n 個の街が並んでいる．街の座標は整数で，昇順に与えられる．街は 3 つの種類があり，それぞれ Byteland の街 (B) B…

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

問題文: No.801 エレベーター - yukicoder Writer 解説: https://yukicoder.me/problems/no/801/editorial 問題概要 ある$ N (\leq 3000)$階建てビルに$ M (\leq 3000) $台のエレベーターがあり，それぞれ$ L_i $階から$ R_i $階まで各階に移動することがで…

W - Intervals 問題概要 長さ $ N (\leq 2 \times 10^5) $ の '0' と '1' のみからなる文字列を考える． 各 $ i (1 \leq i \leq M) $ について，$ l_i $ 文字目から $ r_i $ 文字目までに '1' が ひとつでも含まれるならば，スコアに $ a_i $ を加算するとき…

問題文: C - Division by Two with Something Writer 解説: https://img.atcoder.jp/agc039/editorial.pdf 問題概要 整数 $ N (\leq 2 \times 10^5)$，$ X (\lt 2^N)$ が与えられる．0以上X 以下のすべての整数 k (leading-zero あり) に対し次の操作を繰り…

問題: https://codeforces.com/contest/660/problem/F 公式解説: https://codeforces.com/blog/entry/44259 問題概要 えびちゃんのお気に入り問題の一つなので人々に解いてみてほしいhttps://t.co/mflgdhqEVH pic.twitter.com/aVVI23MM3R — えびちゃん (@rsk…

問題: Problem - E - Codeforces 公式解説: Codeforces Round #620 (Div. 2) Editorial - Codeforces 問題概要 $n (3 \leq n \leq 10^5)$ 頂点の無向木が与えられる。次のクエリに $q (1 \leq n \leq 10^5)$ 回答えよ。 頂点 $x$ と頂点 $y$ の間に辺を追加…

問題: B - Joker 公式解説: 解説 pdf 問題概要 $N \times N$ の正方形の座席を持つ劇場に $N^2$ 人の客が座っている。客が席を立つ順番が与えられるので，以下を求めよ。 客が自席から外周へと出るまでに通る，人の座っている座席の数の，すべての客について…

問題: F - Intervals on Tree 公式解説: 解説 pdf 問題概要 $N (\leq 2 \times 10^5)$ 頂点の無向木がある。整数 $1 \leq L \leq R \leq N$ について，関数 $f(L, R)$ を次のように定義する。 $S$ を$L$ 以上 $R$ 以下の番号のついた頂点からなる集合とする…

問題概要 整数 長さは 上記2条件を満たす文字列中で，同じ文字のみからなる部分文字列のうち最長のものの長さが最も短い． 上記3条件を満たす文字列中で辞書順最小である． 解法概要 "同じ文字が続いても良い数" ABB…B(Bがk個) ABB…B ABB…B…のprefix AA…A(A…

問題概要 高橋くんと青木くんが Nim (石取りゲーム) をする．ただし先攻は高橋くんで，それぞれの山から1回に取れる石の数に以下のような制約がある． $ N $個の山があり，$ i $番目の山は最初$ A_i $個の石がある． ある地点で$ i $番目の山にある石の数を$…

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

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

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

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

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

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

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$で割った剰余を…

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

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

D - K-th K 問題概要 長さ $ N (\leq 500) $ の数列 $ x$ が与えられるとき，次の 2 つの条件を満たす数列 $ a$ が与えられるか判定し，与えられるならば 1 つ構成せよ． $ a$ の長さは $ N^2$であり，整数 $ 1, 2, \cdots, N$をちょうど $ N$ 個ずつ含む． …

問題 / 公式解説: https://codingcompetitions.withgoogle.com/codejam/round/0000000000051706/0000000000122837 問題概要 (インタラクティブ問題) "X-day ring" ( $ 1 \leq X \leq 6 $ ) というものがある．X-day ring は X 日ごとにもう 1 つの X-day rin…

問題: http://codeforces.com/contest/1174/problem/D 公式解説: https://codeforces.com/blog/entry/67388 問題概要 2つの正の整数 $ n (\le 18) $ と $ x (\lt 2^n) $ が与えられる．次の 3 つの条件を満たす数列 $ a $ を構成せよ． $ a $ の要素 $ a_i $…