少し早いですが，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つの点は速さを変えず反対方向に動き…

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$) 解法概要 …

昨日7/6 (金)，チーム KatsuT0shiのメンバーとしてICPCの国内予選に出場しました．参加者の皆さん，関係者の皆さん，お疲れ様でした． KatsuT0shiは情報系のM1 3人で構成されるチームです．3人のうち私を含む2人は95年生まれでこのチームで出られるICPCは最…

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以下に保ったまま，全てのミサイルを廃棄できるかを答えよ． ただし，各国はミサイルを…

クックパッドさんの 1day インターンシップに参加しました． 「技巧を駆使した実用性のないプログラムを作成する『超絶技巧プログラミング』を習得する」という，インターンシップらしからぬテーマ (偏見) に惹かれて参加を決めました． はじめに軽く自己紹…

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 $を目的地とするとき，異なる会社の路線への最小の乗り…