hogecoder

tsutaj 競技プログラミングの記録

2018-03-01から1ヶ月間の記事一覧

AtCoder Regular Contest 089 D: Checker

問題概要 日本語なので原文参照 → D - Checker 解説 公式解説 が詳しく書かれていますので、そちらもご覧ください。ここでは実装上楽な書き方を中心に書きたいと思います。 考慮すべき領域は以下のような形をしており、 箇所の累積和を求めれば良いです。こ…

CSAcademy Round #72: Spring Cleaning

問題概要 原文 → CS Academy 頂点からなる有向グラフがある。このグラフは各頂点から 本ずつ有向辺が出ており、自己ループがないことが保証されている。 はじめ、全ての頂点に対して駒が 個ずつ置かれている。ここから、以下のルールにしたがって駒を取り除…

CSAcademy Round #72: Beautiful Matrix

問題概要 原文 → CS Academy の行列 から、 の行列 を作る。 (作り方は原文参照) を作る前に、 について行どうし、または列どうしのスワップを合計 回まで行える (何もしなくても良い) とき、 の最大値を求めよ。 解説 ある要素が、 の要素のうちいくつに関…

TopCoder SRM 715 Div1 Med: ClassicTowers

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement ハノイの塔をアレンジしたゲームを考える。 つの棒に、左から 個、 個、 個のディスクが刺さっている (ハノイの塔と同じように、大きさは相異なる)。これらのデ…

TopCoder SRM 715 Div1 Easy: MaximumRange

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement と のみからなる数列が与えられる。 (原文は文字列だけどまあ同じことなので) この数列の (連続とは限らない) 部分列を取ることを考える。部分列の累積和を取っ…

TopCoder SRM 716 Div1 Easy: ConstructLCS

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 以下の条件を全て満たすような '0' と '1' のみからなる文字列 を構成せよ。 と の最長共通部分列 (LCS) が と の LCS が と の LCS が 解説 を仮定すると、次の…

TopCoder SRM 716 Div1 Med (Div2 Hard): JumpDistancesOnTree

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 頂点からなる木がある。頂点 を起点として、いくつかの頂点に移動することを考える。集合 が与えられるので、頂点 の順に移動したときの隣り合う要素どうしの距…

TopCoder SRM 717 Div 2 Hard (Div1 Med): DerangementsStrikeBack

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 長さ の順列 であって、先頭 要素について が成立するようなものの総数を求めよ。 解説 Div2 では制約が小さいため、以下のように解くことができます。 「先頭 …

TopCoder SRM 718 Div2 Hard: ChainCity

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 次元座標上に点が 個並んでいる。ここに新たに点を 個まで追加することを考える。 点 から まで移動するときにかかる時間は、通常は 動くごとに 秒かかるが、新…

TopCoder SRM 718 Div1 Easy (Div2 Med): InterleavingParenthesis

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 括弧列 と が与えられる。 に の各文字を、 の文字間の相対位置関係を変えずに挿入することを考える。このとき、 valid な括弧列になるパターンは何通りあるか?…

蟻本練習問題解説 Part3 (2-3)

蟻本練習問題の解説をします。今回のトピックは動的計画法です! 今回は難易度が割と混在しているため、水色 〜 青 の方でも解きごたえがある (ありそう、完全に主観) な問題に★をつけました。競技プログラミングにある程度慣れている方も、★がついている問…

TopCoder SRM 719 Div1 Easy (Div2 Med): LongMansion

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 行無限列のマス目がある。 行目のマスを踏むとき、どの列においてもコストが かかる。 から まで移動するとき、コスト和の最小値を求めよ。 解説 横方向に移動す…

TopCoder SRM 719 Div2 Hard:TwoDogsOnATree

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 頂点からなる木が与えられる。辺 にはそれぞれ重み が設定されており、パス のコストは、 と の間にある辺の重みの XOR と定義する。 与えられた木から、辺の重…

TopCoder SRM 720 Div1 Easy: SumProduct

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement digit1 桁の数 と、digit2 桁の数 を、以下の条件のもとで作ることを考える。 leading zero を許す の各桁において、登場する の個数の合計は最大で 個 このよう…

TopCoder SRM 720 Div2 Hard: RainbowGraph

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 頂点からなる無向グラフがある。頂点にはそれぞれ色 が付いている。 同じ色の頂点は連続して訪れるように (青 → 赤 → 青 みたいに途中で別の色が入るのはダメ) …

TopCoder SRM 721 Div1 Easy (Div2 Med): RememberWords

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement が与えられるので、以下の条件を満たす数列が構成できるか判定せよ。 数列の長さが であり、各項は非負整数で、隣り合う項との差の絶対値は または 第 項から第 …

TopCoder SRM 721 Div1 Hard (Div2 Hard): Apocalypse

するめうめ tsutaj.hatenablog.com 問題概要 頂点からなる木がある。 このうち 個の相異なる頂点に、ルークと爆弾が つずつ置かれている。ルークは ステップで隣接した頂点に移動させることができる。 ステップを終えた後に爆弾と同じ頂点にいるルークは、爆…