TopCoder
問題概要 原文 → TopCoder Statistics - Problem Statement 個の点が与えられる。 与えられる点から 4 つ選んでできる長方形のうち、面積が最大のものを答えよ。ただし長方形を作ることができなければ -1 と答えよ。なお、長方形は軸に平行でなくてもよい。 …
問題概要 原文 → TopCoder Statistics - Problem Statement 種類のバスがあり、 番目のバスは 分おきに停留所に到着することがわかっている。 それぞれのバスについて、来る間隔だけはわかっているがどのタイミングからその間隔で来るかは一様にランダムであ…
するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement ハノイの塔をアレンジしたゲームを考える。 つの棒に、左から 個、 個、 個のディスクが刺さっている (ハノイの塔と同じように、大きさは相異なる)。これらのデ…
するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement と のみからなる数列が与えられる。 (原文は文字列だけどまあ同じことなので) この数列の (連続とは限らない) 部分列を取ることを考える。部分列の累積和を取っ…
するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 以下の条件を全て満たすような '0' と '1' のみからなる文字列 を構成せよ。 と の最長共通部分列 (LCS) が と の LCS が と の LCS が 解説 を仮定すると、次の…
するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 頂点からなる木がある。頂点 を起点として、いくつかの頂点に移動することを考える。集合 が与えられるので、頂点 の順に移動したときの隣り合う要素どうしの距…
するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 長さ の順列 であって、先頭 要素について が成立するようなものの総数を求めよ。 解説 Div2 では制約が小さいため、以下のように解くことができます。 「先頭 …
するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 次元座標上に点が 個並んでいる。ここに新たに点を 個まで追加することを考える。 点 から まで移動するときにかかる時間は、通常は 動くごとに 秒かかるが、新…
するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 括弧列 と が与えられる。 に の各文字を、 の文字間の相対位置関係を変えずに挿入することを考える。このとき、 valid な括弧列になるパターンは何通りあるか?…
するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 行無限列のマス目がある。 行目のマスを踏むとき、どの列においてもコストが かかる。 から まで移動するとき、コスト和の最小値を求めよ。 解説 横方向に移動す…
するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 頂点からなる木が与えられる。辺 にはそれぞれ重み が設定されており、パス のコストは、 と の間にある辺の重みの XOR と定義する。 与えられた木から、辺の重…
するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement digit1 桁の数 と、digit2 桁の数 を、以下の条件のもとで作ることを考える。 leading zero を許す の各桁において、登場する の個数の合計は最大で 個 このよう…
するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 頂点からなる無向グラフがある。頂点にはそれぞれ色 が付いている。 同じ色の頂点は連続して訪れるように (青 → 赤 → 青 みたいに途中で別の色が入るのはダメ) …
するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement が与えられるので、以下の条件を満たす数列が構成できるか判定せよ。 数列の長さが であり、各項は非負整数で、隣り合う項との差の絶対値は または 第 項から第 …
するめうめ tsutaj.hatenablog.com 問題概要 頂点からなる木がある。 このうち 個の相異なる頂点に、ルークと爆弾が つずつ置かれている。ルークは ステップで隣接した頂点に移動させることができる。 ステップを終えた後に爆弾と同じ頂点にいるルークは、爆…
するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement CPU が 個あり、 番目の CPU は ミリ秒につき仕事量 を消化でき、コア数は である。 いま、仕事量 のタスクがある。 個ある CPU のうちどれか つだけ選び、この…
するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement leading zero を許して 桁の数字を作ることを考える。 文字列がいくつか与えられる。作る数字の prefix は、この文字列のいずれとも一致してはならない。 この状…
するめうめ tsutaj.hatenablog.com 問題概要 個の非負整数列 がある。 から までの範囲で非負整数 を、 から までの範囲で非負整数 を、・・・以下同様に合計 個の非負整数を決め、それらの XOR をとるとき、 XOR 値の最大値を求めよ。 解説 XOR を最大化し…
するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement の部屋が十字型に並んでいる。 (詳細は原文をご覧ください) すべての部屋と部屋の間の最短距離の総和を求めよ。 解説 ※ちゃんとした解説は kmjp さんのブログ に…
するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement ともに長さが の数列 , が与えられる。以下の条件を満たす長さ の数列 が構成できるかを判定せよ。 解説 まず、任意の非負整数 に対して、 が成立します (これは…
するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 人のリーグ戦の表が与えられる (引き分けなし)。試合は全て終わっているわけではなく、勝敗がまだ決していない箇所は '?' で表される。 '?' を埋めたとき、勝率…
するめうめ tsutaj.hatenablog.com 問題概要 原文 → 掲載されてないぽい (unrated だから?) 頂点が 個あり、それぞれの頂点について値 が与えられる。各頂点に という値を適切に決めたとき、以下の条件を満たす DAG がいくつできるか求めよ。なお、 の値が…
するめうめ tsutaj.hatenablog.com 問題概要 原文 → 掲載されてないぽい (unrated だから?) の盤面にルークがいくつか置かれている。 行の座標どうしが unique に、列の座標どうしが unique になるようにルークを つ選べ。 解説 なので、適当に全探索したら…
するめうめ tsutaj.hatenablog.com 問題概要 原文 → 掲載されてないぽい (unrated だから?) 頂点が 個あり、それぞれの頂点について値 が与えられる。以下の条件を満たす DAG が構成できるか判定せよ。 それぞれの頂点について、入次数は高々 頂点 から到達…
するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 個の袋がある。 番目の袋には 個の赤いキャンデーと の青いキャンデーが入っていて、コストは とのことである。 それぞれの袋について、この情報は微妙に間違っ…
するめうめ tsutaj.hatenablog.com 問題 原文 → TopCoder Statistics - Problem Statement 個の仕事があり、それぞれについてこなすために の時間がかかり、その仕事を実行できる時間が区間として決まっている。 個の仕事の部分集合であって、適切にこなすこ…
するめうめ tsutaj.hatenablog.com 問題概要 文字列 が与えられる。 にいくつか文字を挿入して、"SANTA" を部分列として含み、かつ "SATAN" を部分列として含まないような文字列を構成せよ。 解説 方針は同じ回の Div2 Hard (hogecoder での解説) と全く同じ…
するめうめ tsutaj.hatenablog.com 問題概要 原文 → TopCoder Statistics - Problem Statement 文字列 が与えられる。 に対して、部分列として を含むが は含まないように、いくつか文字を挿入したい。この条件を満たす文字挿入個数の最小値を求めよ。不可能…
するめうめ tsutaj.hatenablog.com 問題概要 自然数が 個与えられる。各数字 に対して、次の操作を何度でも行える。 が偶数のとき、その数字を に変える。 が奇数のとき、その数字を か のどちらかに変える。 操作を何回か行い、 個全てが同じ数字になるよう…
するめうめ 問題概要 原文 → TopCoder Statistics - Problem Statement 頂点の有向グラフがあり、各頂点はそれぞれ から までの番号でラベル付けされている。 ある つの頂点を選び、ラベルをローテーションするという操作を何回か行い、元のグラフのラベリン…