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
続きを読む

ICPCOOC2016 C: Distribution Center

問題

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

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

続きを読む

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' の順になっている。

N \le 50

続きを読む

ABC041 D: 徒競走

問題

D: 徒競走 - AtCoder Beginner Contest 041 | AtCoder
1〜Nの順列を考える。数 x_i は、数 y_i の前にあるという情報が M 個与えられる。条件を満たす順列の総数を求めよ。

  • 2 \le N \le 16
  • (x_i, y_i) のペアはすべて相異なる。
  • 全ての情報に合致する並びが少なくとも1つ存在する。
続きを読む

AOJ1079 Cosmic Market

問題

Cosmic Market | Aizu Online Judge
R * C のグリッドがある。各マスには人がいて、はじめ全員が座っている。指定された行、または列に対して「立つ」または「座る」というクエリがQ回与えられる。最後に立っている人の数を答えよ。
1 \le R, C, Q \le 50,000

続きを読む

D - アンバランス / Unbalanced

問題
D: アンバランス / Unbalanced - AtCoder Beginner Contest 043 | AtCoder

文字列について、過半数を超えている文字があれば、その文字列はアンバランスであるという。
文字列Sが与えられる。Sの部分文字列について、アンバランスなものがあれば、その始点と終点を1-indexedで出力せよ。そのような部分文字列がなければ、代わりに"-1 -1"を出力せよ。
N \le 10^5

続きを読む