2017-10

Latest Entries

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

ZOJ

登録した.
可能な限り,ICPC World Finals 2011 の優勝者を追っかけてみる.

ZOJ 1001: A + B Problem


a と b が与えられるので a + b を出力する.

int で通った.
余分な改行を入れたら PE と言われた.

ZOJ 1002: Fire Net


いくつかのマスがふさがれた N * N のマス目がある.縦横に攻撃する駒を,互いに攻撃し合わないように最大いくつおけるか.間にふさがれているマスがあれば攻撃しない.
N <= 4.

恐らく全探索すれば通るけれど,フローの練習にした.縦に繋がったの極大成分と横に繋がった極大成分の二部マッチング.

ZOJ 1003: Crashing Balloon


1 から 100 までの風船を 2 人で取り合って,取った風船の数の積が得点となるゲーム.得点を報告し合った.
・得点が低い人が報告した得点があり得ないならば得点の高い人の勝ち
・そうでなくて,2 人の得点があり得ないならば得点の低い人の勝ち
・そうでなければ得点の高い人が勝ち
で勝敗を判定する.

int に収まった.
DFS で全探索した.同じ数を割っている場合は最後に使った約数も引数に持たせる.

得点が低い人があり得ないケースを正しく判定できていなかった.グローバルにフラグをおいて得点が高い方を割り始めるときにフラグを立てる,という方法で判定した.

POJ 1078 が同じ問題.

ZOJ 1004: Anagrams by Stack


文字列 S, T が与えられる.S の文字が先頭から 1 個ずつやってくると考えて,スタックを 1 個用いて,T を出力させたい.push を i,pop を o と書いて,可能な手順の列を辞書順ですべて出力する.

(S[a .. b], T[c .. d]) に対して解くことを考えると,S[a] == T[i] なる各 i に対して,(S[a+1 .. a+1-i-c], T[c .. i]) の解と (S[a+1+i-c .. b], T[i+1 .. d]) の解を組み合わせたものが解なので,再帰的に呼べばよい.

サイズが書いていないがこれで通った.解の最大値は長さに対してカタラン数なのですぐ爆発する.

出力の行末にも空白がいることに注意 (PE した).

ZOJ 1005: Jugs


容量 A, B の瓶がある.空にしたり満たしたり一方からもう一方へ注いだりできる.どちらかの瓶にちょうど N 入っている状態を作る操作列を出力せよ.
1 <= A <= B <= 1,000,A, B は互いに素な整数,N <= B.

ひたすら A から B に注いだ.実装上は,
・B が満杯なら空にする
・そうでなければ A が空なら満たす
・そうでなければ A から B に注ぐ
を繰り返した.

ZOJ 1006: Do the Untwist


可逆な暗号を解読する.使う文字は 0-27 にエンコードされる.
ciphercode[i] = (plaincode[ki mod n] - i) mod 28
による.n は文字列の長さ,k は与えられる.
n <= 70,k <= 300,n と k は互いに素.

与えられた式を plaincode の部分について解いて,i を回して全部埋める.

memset(T, 0, sizeof(N)); というのを書いて WA した (前のケースの答を消せていない).

コメント

コメントの投稿


管理者にだけ表示を許可する

トラックバック

http://hos0lyric.blog89.fc2.com/tb.php/9-23f348b3

この記事にトラックバックする(FC2ブログユーザー)

«  | ホーム |  »

プロフィール

hos.lyric

Author:hos.lyric

 

最新記事

最新コメント

 

最新トラックバック

 

月別アーカイブ

カテゴリ

検索フォーム

 

 

RSSリンクの表示

リンク

ブロとも申請フォーム

QRコード

 

QR

 

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。