読者です 読者をやめる 読者になる 読者になる

torus711 のアレ

主に競技プログラミングの問題について書きます

TopCoder SRM 681, Division 1, Level 1 : FleetFunding

問題概要

 $1$ から $M $ で番号付けられた $M $ 個のパーツを使って作られる機械がある.一つの機械は,$1$ から $M $ のパーツを一つずつ使って構成される.
 パーツは,$N$ 個の店から買うことができる.各 $i$ ( $1 \leq i \leq N$ ) について,$i$ 番の店では $A_i$ 以上 $B_i$ 以下の番号のパーツを(合計で)最大 $K_i$ 個まで買うことができる.
 作ることのできる機械の最大数を求めよ.

  • $1 \leq N \leq 50$
  • $1 \leq M \leq 10^5$
  • $1 \leq K_i \leq 10^6$
  • $1 \leq A_i \leq B_i \leq M $
続きを読む

TopCoder SRM 674, Division 1, Level 1 : VampireTree

問題概要

 数のリスト $\mathit{ num }$ が与えられる.$| \mathit{ num } | = N$ とする.
 $N$ 頂点の木であって,$i$ 番目の頂点の次数が $\mathit{ num }_i$ であるような木を作るとき,直径(2 点間距離の最大値)の最大値を求めよ.
 木を作れない場合は -1 で示せ.

  • $2 \leq | \mathit{ num } | \leq 20$
  • $1 \leq \mathit{ num }_i \leq N - 1$
続きを読む

TopCoder SRM 671, Division 1, Level 2 : BearDarts

問題概要

 正整数からなる列 $w$ が与えられる.4 要素からなる $w$ の部分列をとって $\{ a, b, c, d \}$ としたとき,$ac = bd$ となっているものの総数を求めよ.

  • $4 \leq |w| \leq 1{,}000$
  • $1 \leq w_i \leq 10^9$
続きを読む

TopCoder SRM 671, Division 1, Level 1 : BearCries

問題概要

 ';' + 1 つ以上の '_' + ';' という文字列を顔文字であるとする.例えば ";_;" や ";____;" は顔文字であるが,";;" や ";_" は顔文字ではない.
 ';' と '_' からなる文字列 $\mathit{ message }$ が与えられる.$\mathit{ message }$ を重複しない複数の部分列に分けたとき,部分列全てが顔文字となっていて,かつ全ての文字が丁度 1 つの部分列に属するような分け方は何通りあるか?
 総数を $X$ として$X \bmod{ 10^9 + 7 }$ を求めよ.

  • $1 \leq \mathit{ message } \leq 200$
続きを読む

TopCoder SRM 670, Division 1, Level 2 ( Division 2, Level 3 ) : Treestrat

問題概要

 $N$ 頂点の木と 2 種類のトークンを使った 2 人ゲームをする.プレイヤーを A, B として,A は赤いトークンを,B は青いトークンを使う.
 木の頂点は $0$ から $N - 1$ で番号付けられている.ゲームの初期状態は 3 つの配列 $\mathit{ tree }$, $A$, $B$ により与えられる.$\mathit{ tree }$ は木の形を表し,$i$ ( $1 \leq i \leq N - 1$ ) について,2 頂点 $i$, $\mathit{ tree }_{ i - 1 }$ 間に辺があることを表す.$A$ は赤いトークンの初期位置を,$B$ は青いトークンの初期位置を表す( $a \in A$ なる頂点 $a$ に赤いトークンがある.$B$ と青いトークンについても同様).
 ゲームは Round と呼ばれる工程の繰り返しからなる.1 回のラウンドは,

  1. A が赤いトークンをいくつか選び,それぞれ隣接する頂点に移動させる
  2. B が青いトークンをいくつか選び,それぞれ隣接する頂点に移動させる

という 2 つのフェーズからなる.
 Round 終了後に,2 種類のトークンが存在する頂点が 1 つでもあれば,B の勝利となる.
 B はできるだけ少ない Round 数で勝ちたいと思っていて,A はできるだけ多くの Round をプレイしたいと思っている.両者が最善を尽くすとき,プレイされる Round 数を求めよ.B が有限の Round 数で勝利できることは保証されている.

  • $2 \leq N \leq 50$
続きを読む