torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

TopCoder, SRM 666, Division 2, Level 1 : DevuAndGame

問題概要

 全ての頂点の出次数が高々 1 であるような,$N$ 頂点の有向グラフが与えられる.このグラフにおいて頂点 0 から辺に沿って移動したとき,出次数 0 の頂点に到達可能か?

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

Codeforces 323, Division 1, B ( Division 2, D ) : Once Again...

問題概要

 $n$ 項の数列を $T$ 回繰り返した,$nT$ 要素の数列 $a$ が与えられる(与えられるのは最初の $n$ 要素のみ).$a$ の単調非減少な部分列の内,最長のものの長さを求めよ.

  • $1 \leq n \leq 100$
  • $1 \leq T \leq 10^7$
  • $1 \leq a_i \leq 300$
続きを読む

Codeforces 323, Division 1, A ( Division 2, C ) - GCD Table

問題概要

 $n$ 要素の数列 $a$ から生成されるGCD Table を,$$g_{ ij } = \mathrm{ gcd }( a_i, a_j )$$ なる $n \times n$ 行列とする.
 今,$g$ の要素を適当に並び替えた $n \times n$ 個の整数が与えられるので,$a$ として妥当なものを 1 つ復元せよ.解の存在は保証される.
 $1 \leq n \leq 500$

続きを読む

TopCoder, Single Round Match 667, Division 1, Level 1 : OrderOfOperations

問題概要

 問題設定は Division 2, Level 2 と同一だが制約が異なる.
 $1 \leq N \leq 50$
 $1 \leq M \leq 20$

続きを読む

TopCoder, Single Round Match 669, Division 2, Level 2 : CombiningSlimes

問題概要

 初めに正整数の多重集合 $a$ がある.$|a| > 1$ である間,以下の操作をする.

  1. $a$ から要素を 2 つ取り除き,それらを $x, y$ とする.
  2. $a$ に $x + y$ を加える
  3. $xy$ のスコアを得る

 得られる累計スコアの最大値を求めよ.
 $2 \leq |a| \leq 100$

続きを読む