hogecoder

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

TopCoder

TopCoder SRM 764: RectangleHunt

問題概要 原文 → TopCoder Statistics - Problem Statement 個の点が与えられる。 与えられる点から 4 つ選んでできる長方形のうち、面積が最大のものを答えよ。ただし長方形を作ることができなければ -1 と答えよ。なお、長方形は軸に平行でなくてもよい。 …

TCO19 Round3A Med: WaitingForBusAgain

問題概要 原文 → TopCoder Statistics - Problem Statement 種類のバスがあり、 番目のバスは 分おきに停留所に到着することがわかっている。 それぞれのバスについて、来る間隔だけはわかっているがどのタイミングからその間隔で来るかは一様にランダムであ…

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 な括弧列になるパターンは何通りあるか?…

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

TopCoder SRM 722 Div2 Hard: MulticoreProcessingEasy

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement CPU が 個あり、 番目の CPU は ミリ秒につき仕事量 を消化でき、コア数は である。 いま、仕事量 のタスクがある。 個ある CPU のうちどれか つだけ選び、この…

TopCoder SRM 722 Div1 Easy: TCPhoneHome

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement leading zero を許して 桁の数字を作ることを考える。 文字列がいくつか与えられる。作る数字の prefix は、この文字列のいずれとも一致してはならない。 この状…

TopCoder SRM 723 Div1 Easy: TopXorer

するめうめ tsutaj.hatenablog.com 問題概要 個の非負整数列 がある。 から までの範囲で非負整数 を、 から までの範囲で非負整数 を、・・・以下同様に合計 個の非負整数を決め、それらの XOR をとるとき、 XOR 値の最大値を求めよ。 解説 XOR を最大化し…

TopCoder SRM 723 Div2 Hard: SimpleMazeEasy

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement の部屋が十字型に並んでいる。 (詳細は原文をご覧ください) すべての部屋と部屋の間の最短距離の総和を求めよ。 解説 ※ちゃんとした解説は kmjp さんのブログ に…

TopCoder SRM 724 Div1 Easy: OrAndSum

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement ともに長さが の数列 , が与えられる。以下の条件を満たす長さ の数列 が構成できるかを判定せよ。 解説 まず、任意の非負整数 に対して、 が成立します (これは…

TopCoder SRM 724 Div2 Hard: UnfinishedTournamentEasy

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 人のリーグ戦の表が与えられる (引き分けなし)。試合は全て終わっているわけではなく、勝敗がまだ決していない箇所は '?' で表される。 '?' を埋めたとき、勝率…

TopCoder SRM 725 Div1 Med: HiddenTree

するめうめ tsutaj.hatenablog.com 問題概要 原文 → 掲載されてないぽい (unrated だから?) 頂点が 個あり、それぞれの頂点について値 が与えられる。各頂点に という値を適切に決めたとき、以下の条件を満たす DAG がいくつできるか求めよ。なお、 の値が…

TopCoder SRM 725 Div1 Easy: FiveRooks

するめうめ tsutaj.hatenablog.com 問題概要 原文 → 掲載されてないぽい (unrated だから?) の盤面にルークがいくつか置かれている。 行の座標どうしが unique に、列の座標どうしが unique になるようにルークを つ選べ。 解説 なので、適当に全探索したら…

TopCoder SRM 725 Div2 Hard: HiddenTreeDiv2

するめうめ tsutaj.hatenablog.com 問題概要 原文 → 掲載されてないぽい (unrated だから?) 頂点が 個あり、それぞれの頂点について値 が与えられる。以下の条件を満たす DAG が構成できるか判定せよ。 それぞれの頂点について、入次数は高々 頂点 から到達…

TopCoder SRM 726 Div1 Easy: Unpacking

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 個の袋がある。 番目の袋には 個の赤いキャンデーと の青いキャンデーが入っていて、コストは とのことである。 それぞれの袋について、この情報は微妙に間違っ…

TopCoder SRM 726 Div2 Hard: HeroicScheduled2

するめうめ tsutaj.hatenablog.com 問題 原文 → TopCoder Statistics - Problem Statement 個の仕事があり、それぞれについてこなすために の時間がかかり、その仕事を実行できる時間が区間として決まっている。 個の仕事の部分集合であって、適切にこなすこ…

TopCoder SRM 727 Div1 Easy: OnlySanta

するめうめ tsutaj.hatenablog.com 問題概要 文字列 が与えられる。 にいくつか文字を挿入して、"SANTA" を部分列として含み、かつ "SATAN" を部分列として含まないような文字列を構成せよ。 解説 方針は同じ回の Div2 Hard (hogecoder での解説) と全く同じ…

TopCoder SRM 727 Div2 Hard: ManageSubsequences

するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 文字列 が与えられる。 に対して、部分列として を含むが は含まないように、いくつか文字を挿入したい。この条件を満たす文字挿入個数の最小値を求めよ。不可能…

TopCoder SRM 728 Div1 Easy: Halving

するめうめ tsutaj.hatenablog.com 問題概要 自然数が 個与えられる。各数字 に対して、次の操作を何度でも行える。 が偶数のとき、その数字を に変える。 が奇数のとき、その数字を か のどちらかに変える。 操作を何回か行い、 個全てが同じ数字になるよう…

TopCoder SRM 728 Div2 Hard: TrisomorphismEasy

するめうめ 問題概要 原文 → TopCoder Statistics - Problem Statement 頂点の有向グラフがあり、各頂点はそれぞれ から までの番号でラベル付けされている。 ある つの頂点を選び、ラベルをローテーションするという操作を何回か行い、元のグラフのラベリン…