h3mky0's blog

主に競プロについて書きます

AOJ2401 Equation (実装メモ)

問題リンク
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2401

最大11個の変数が含まれる式が与えられるので, 常に式が成立するかチェックする.
常に, の部分は各変数の0/1をbit全探索する. 式については気合で構文解析をする.

AND, OR, IMP等の二項演算はvariableが演算子の前後にくるため, 処理が容易.
一方で, NOT等の前置演算子をどう処理するかが問題.

NOTはvariableの後ろか, 左括弧の後ろに来る. よって, 左括弧が取り除かれるときやvariableが見つかった時にNOTを処理すればよさそう.

IMPの記号('->')とNOTの記号('-')が部分的に一致しているので注意する. (1WA)

AtCoder Regular Contest 105 C - Camels and Bridge

問題リンク
atcoder.jp

問題概要
N頭のラクダがおり, それぞれ重さ w_{i}が決まっている
いま任意の順番にラクダを並べて, M個の橋を渡ろうとしている. 橋には長さ l_{i}と耐久値 v_{i}が決まっており, その橋に乗っているラクダの総体重が耐久値を超えた場合, 崩れてしまう. そのためラクダ間の間隔を十分にとる必要がある.

橋を渡り切れる場合の先頭のラクダと末尾のラクダの距離の最小値を求める.

続きを読む

SPOJ MULTQ3 - Multiple of 3

www.spoj.com

概要
次のいずれかのクエリがQ個与えられるので, クエリ1に対して結果を出力する
クエリ0 区間l, rが与えられるので, その区間の全ての要素に1を足す.
クエリ1 区間l, rが与えられるので, 3で割り切れる要素の数を出力する.

続きを読む

Codeforces Round #605 (Div. 3) F. Two Bracket Sequences

問題リンク
codeforces.com

問題概要
文字"(", ")"からなる文字列 s, tが与えられるので, s, tを（連続でなくてもよい）部分列として含むような最小文字数の正規括弧列を出力する.

正規括弧列の定義は次の通り
1. 空文字
2. ある正規括弧列Aが存在して, '(' A ')' のこの順に連結したもの
3. ある空でない正規括弧列 A, Bが存在して, A Bのこの順に連結したもの

続きを読む

JOI 2008 春合宿 day3-2 「Fraction」

最近ブログを書いてなかったので...

問題リンク
www.ioi-jp.org

問題概要
分母がM以下であるような1未満の分数について小さい方からk番目の分数を出力する. 存在しない場合, -1を出力する.

続きを読む