問題: https://codeforces.com/contest/1167/problem/E 公式解説: https://codeforces.com/blog/entry/67017 問題概要 長さが $ n (\leq 10^6) $ の数列 $ a = a_1, a_2, \cdots a_n (1 \leq a_i \leq 10^6) $ がある．このとき， $ f(l, r) = $ $ a $ から …
W - Intervals 問題概要 長さ $ N (\leq 2 \times 10^5) $ の '0' と '1' のみからなる文字列を考える． 各 $ i (1 \leq i \leq M) $ について，$ l_i $ 文字目から $ r_i $ 文字目までに '1' が ひとつでも含まれるならば，スコアに $ a_i $ を加算するとき…
問題 / 公式解説: https://codingcompetitions.withgoogle.com/codejam/round/0000000000051706/0000000000122837 問題概要 (インタラクティブ問題) "X-day ring" ( $ 1 \leq X \leq 6 $ ) というものがある．X-day ring は X 日ごとにもう 1 つの X-day rin…
問題: D - Three Colors 公式解説: https://img.atcoder.jp/tenka1-2019/editorial.pdf 問題概要 N 個の整数 $ a_1, a_2, \cdots a_N $ が与えられる．これらの整数を赤，緑，青で塗り分ける． 赤，緑，青で塗られた整数の和を R, G, B とするとき， 3辺の長…
D - K-th K 問題概要 長さ $ N (\leq 500) $ の数列 $ x$ が与えられるとき，次の 2 つの条件を満たす数列 $ a$ が与えられるか判定し，与えられるならば 1 つ構成せよ． $ a$ の長さは $ N^2$であり，整数 $ 1, 2, \cdots, N$をちょうど $ N$ 個ずつ含む． …
問題: https://codeforces.com/contest/962/problem/E 公式解説: https://codeforces.com/blog/entry/58869 問題概要 1次元の座標軸の上に n 個の街が並んでいる．街の座標は整数で，昇順に与えられる．街は 3 つの種類があり，それぞれ Byteland の街 (B) B…
問題: https://codeforces.com/contest/964/problem/D 公式解説: https://codeforces.com/blog/entry/58991 問題概要 n ノードの木が与えられる．木の中で，次数が偶数の頂点を destroy できる．頂点を destroy すると，その頂点につながっている辺は全て消…
問題文: D - Nearest Card Game Writer 解説: https://img.atcoder.jp/aising2019/editorial.pdf 問題概要 $ N (\leq 10^5)$枚の数字が書かれたカード $ A_1 \lt A_2 \lt \cdots \lt A_N$ を高橋くんと青木くんが交互に，カードがなくなるまで取っていく．先…
問題文: No.802 だいたい等差数列 - yukicoder Writer 解説: https://yukicoder.me/problems/no/802/editorial 問題概要 長さ$ N (\leq 3 \times 10^5)$の整数列$ A_1, A_2, \cdots, A_N$で，次の 2 つの条件の両方を満たすものの数をを$ 10^9+7 $で割ったも…
問題文: No.801 エレベーター - yukicoder Writer 解説: https://yukicoder.me/problems/no/801/editorial 問題概要 ある$ N (\leq 3000)$階建てビルに$ M (\leq 3000) $台のエレベーターがあり，それぞれ$ L_i $階から$ R_i $階まで各階に移動することがで…
問題文: TopCoder Statistics - Problem Statement 公式解説: SRM 752 Editorial - Topcoder 問題概要 ある n+1 ($ n \leq 2000 $) 桁以下の数値について，隣あった桁の数字の大小関係が "=!><" の文字を含む長さ n の文字列で与えられる． このとき，「ある…
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$) の文字…
DDCC2019 本戦に参加してきました．DDCC は2年ぶり2回目． 〜前夜祭 DDCC3日前 (実質2日前？) にこのようなツイートをしたところ，意外に人が集まりました． DDCC前夜 (今週の金曜夜) に何人かでご飯食べませんかって言ったら興味ある方いませんか？場所は会…
C - Lexicographic constraints 問題概要 $ N \leq 2 \times 10^5 $個の文字列があり，$ i$番目の文字列の長さが$ a_i (\leq 10^9)$であるとき，全ての文字列を辞書順にするために必要な最小の文字の種類数を求める． 解法概要 二分探索で答えの候補を決めて…
少し早いですが，2018年の目標の達成度合いを振り返りつつ2019年の目標を立てます． 0. 目標達成度合いの目安 1. 2018年の目標振り返り 1.1. 競プロ ACM-ICPCアジア地区大会出場★★ 総AC数800突破★★★ AtCoder 1800★ Codeforces 1750★★★ TopCoder SRM 1350★ 複…
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$で割った剰余を…
この記事はCompetitive Programming (2) Advent Calendar 2018 14日目の記事です． adventar.org お急ぎの方はこの目次だけ読んでいただければOKです． この記事の対象読者 解説を書くのは有意義 解説を書くのは大変 Scrapboxで解法メモを取ろう おすすめす…
B - Garbage Collector 問題概要 ゴミ (ゴミの数$ N \leq 2 \times 10^5 $) を拾う・運ぶ・捨てるエネルギーが以下のように定められるとき，全てのゴミを捨てるまでの消費エネルギーを最小化せよ． i番目のゴミはそれぞれ$ x_i (\leq 10^9)$の位置にある． k…
Anarise (PC推奨, Chrome と Firefox で動作確認済み) というメタ自己分析ツールを作りました．ソースコードはGitHub - noimin0610/anarise: メタ自己分析ツールで公開しています． Analyze + Summarize + Arise で "Anarise" です． 開発のきっかけ 今まで…
この記事はAtCoder関連サービス Advent Calendar 2018 3日目の記事です． adventar.org 開発秘話というほど大した話はありませんが，サービスの概要とグラフ付きツイート機能の実現方法について雑に述べます． 私が1人で開発した旧 AtCoder Performances と…
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つの点は速さを変えず反対方向に動き…
