2016-10-24

CODE FESTIVAL 2016 qual C - B: K個のケーキ

問題

$K$ 個のケーキが $T$ 種類ある。各種類 $a_i$ 個ずつ存在する。毎日1個ずつ食べるとして、全てのケーキを食べ終えたとき、前日と同じケーキを食べる回数の最小値を出力せよ。

$1\le K\le 10000,\ 1\le T\le 100$
$1\le a_i\le 100$
$a_1\ +\ a_2\ +\ ...\ +\ a_T\ =\ K$

2016-10-24

CODE FESTIVAL 2016 qual C - D: Friction

問題

D: Friction - CODE FESTIVAL 2016 qual C | AtCoder

$H\times W$ のブロックがある。各ブロックは赤、緑、青のいずれかである。1度の操作で、一番下の行あるブロックのうち1つを消すことができる。消すときにかかるコストは、消した列の各ブロックの横に隣り合うブロックのうち色が同じ物の数のぶんだけかかる。全てのブロックを消すためのコストを最小化せよ。部分点は $W=3$ の場合である。

$1\le H\le 300$
$2\le W\le 300$

2016-10-18

ICPCOOC2016 E: Infallibly Crack Perplexing Cryptarithm

問題

http://judge.u-aizu.ac.jp/onlinejudge/contest/ICPCOOC2016/E.pdf
以下のような文脈自由文法( $CFG$ )が与えられる。

$Q ::= E=E$
$E ::= T\ |\ E+T\ |\ E-T$
$T ::= F\ |\ T*F$
$F ::= N\ |\ -F\ |\ (E)$
$N ::= 0\ |\ 1B$
$B ::= \epsilon |\ 0B\ |\ 1B$

これに沿って書かれた1つの等式を表す文字列 $S$ がある。各文字は '0', '1', '(', ')', '+', '-', '*', '=' で構成される。等式の一部または全部分は覆面算になっていて、同じ文字は同じアルファベット（大小区別しない）で表される。異なるアルファベットには、必ず異なる文字をあてはめる必要がある。条件を満たす文字のあてはめ方は何通りあるか。

$|S| \le 31$

2016-10-17

ICPCOOC2016 D: Hidden Anagrams

問題

http://judge.u-aizu.ac.jp/onlinejudge/contest/ICPCOOC2016/D.pdf

2つの文字列 $S, T$ がある。一つの部分文字列のアナグラムが、他方の部分文字列に一致するような文字列の最長の長さを求めよ。

$1 \le |S| \le 4000$
$1 \le |T| \le 4000$

2016-10-17

ICPCOOC2016 C: Distribution Center

問題

長いレーンのベルトコンベアが $N$ 列ある。はじめ各ベルトコンベアにはその番号の種類の品物のみが乗っている。隣接するベルトコンベアの間の位置に、 $M$ 個のアームが存在する。これらは上下に隣接するレール間で品物を動かすことができる。レーンを抜けたときにそれぞれのレーンで最大何種類の品物が流れてくるか。

$2 \le N \le 200000$
$1 \le M \lt 100000$

2016-10-17

AOJ2679 Decoding Ancient Messages

問題

Decoding Ancient Messages | Aizu Online Judge

$N * N$ のグリッドの各マスに文字が書かれている。ここから $N$ 文字抽出する。抽出する文字は同一行または同一列に存在してはいけない。任意の順番で抽出して並べたとき、作ることのできる辞書順最小の文字列を求めよ。ただし文字はアルファベットの大文字または小文字であり、 $'A' \lt 'B' \lt ... \lt 'Z' \lt 'a' \lt 'b' \lt ... \lt 'z'$ の順になっている。