Entries

スポンサーサイト (この記事を編集する[管理者用])

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

COJ 1591 - King's Poker [KPOKER] (この記事を編集する[管理者用])

Source

The 2011 Caribbean Finals of the ACM-ICPC - Real (Open) (2011-11-10)
COJ 1591 [KPOKER]

問題概要

3枚の数字が書かれたカードが与えられる.
カードに書かれた数字は1以上13以下.
以下の基準で強さを判定する.
 定義:3枚とも同じ数字ならsetといい,2枚が同じ数字で残り1枚が異なるならpairといい,その他はその他という.
 任意のsetは任意のsetじゃないものより強い
 任意のpairは任意のその他より強い
 set同士なら,数字が大きい方が強い
 pair同士なら,揃っている数字が大きい方が強い,同じなら残りの数字が大きい方が強い
 その他同士は,全て同じ強さ
与えられた3枚のカードより強くて,最も弱いカードの組を,カード番号が昇順になるように出力する問題.
存在しないなら*を出力する.

解法

やるだけ.

COJ 1590 - Jupiter Attacks! [JUPITER] (この記事を編集する[管理者用])

Source

The 2011 Caribbean Finals of the ACM-ICPC - Real (Open) (2011-11-10)
COJ 1590 [JUPITER]

問題概要

数列 a0, a1, a2, ..., an に対して,以下の形のハッシュを考える.
 a0 * B^n + a1 * B^(n-1) + ... + an * B^0 mod P
Pは与えられた素数で,Bは与えられた整数.
長さL (10^5以下) の数列で,最初は全部0のものがある.
クエリがN個 (10^5) 与えられるのでそれに答える問題.クエリの形式は以下のとおり.
 クエリ1: 数列のある1つの要素を,ある値に変更する
 クエリ2: 数列の連続する部分列を1つ指定して,そのハッシュを求める.

解法

平方分割で解いた.Segment treeでもOKだと思う.

COJ 1589 - In Braille [INBRAILE] (この記事を編集する[管理者用])

Source

The 2011 Caribbean Finals of the ACM-ICPC - Real (Open) (2011-11-10)
COJ 1589 [INBRAILE]

問題概要

0~9までの点字が問題分で与えられている.
点字を数字に直す,また,数字を点字に直す問題.

解法

やるだけ.

COJ 1588 - Hedge Mazes [HEDGEMAZES] (この記事を編集する[管理者用])

Source

The 2011 Caribbean Finals of the ACM-ICPC - Real (Open) (2011-11-10)
COJ 1588 [HEDGEMAZES]

問題概要

ノード数10^4以下,枝数10^5以下の無向グラフが与えられる.
ノードの組が1000個以下与えられる.
各ノードの組に対して,そのノード間のシンプルなパスがちょうど1つだけかを判定する問題.
シンプルなパスとは同じノードを2回以上通らないパス.

解法

橋のみを通っていけるノード間はシンプルなパスがちょうど1つになる.
橋を列挙してあげて,union findでまとめておくと,すべてのクエリに対してすぐ答えれる.
橋の列挙は例えば,Spaghetti Sourceを参照.

COJ 1582 - Ball Stacking [BALLSTACKING] (この記事を編集する[管理者用])

Source

The 2011 Caribbean Finals of the ACM-ICPC - Real (Open) (2011-11-10)
COJ 1582 [BALLSTACKING]

問題概要

図のようにボールが高さN (1000以下) の三角形状に積み重なっている.
ボールには絶対値が10^5以下の整数が書かれている.
あるボールを取ると,その上にあるボールは全て取らなければいけない.
取ったボールに書かれている整数を最大化したい.最大値を求める問題.

解法

取らなかったボールの和を最小にすることを考える.
取らないボールは,ギザギザした山形のような形にならなければいけないことがわかる.
図を反時計回りに45度回転して,各行に対して,どこまでボールを取ったかを状態にDPしていく.

COJ 1581 - Army buddies [ARMYB] (この記事を編集する[管理者用])

Source

The 2011 Caribbean Finals of the ACM-ICPC - Real (Open) (2011-11-10)
COJ 1581 [ARMYB]

問題概要

1番からS番までの人が左から順番に一列に並んでいる.
B回操作を行うので,各操作に対して答えを求める問題.
 各操作では,LとRが与えられ,L以上R以下の全ての整数kに対して,番号kの人はまだ存在する.
 L以上R以下の全ての整数kに対して,番号kの人を削除する.
 各操作を行った後,L番目より左に存在する最も右の人の番号と,R番目より右に存在する最も左の人の番号を求める.存在しないならそれを指摘する.

解法

リスト構造的なのを使って,自分より左の最も右の人,自分より右の最も左の人を計算する.

COJ 1580 - Hailstone Sequences [HAILSTONE] (この記事を編集する[管理者用])

Source

The 2011 Caribbean Finals of the ACM-ICPC - Warmup (2011-11-05)
COJ 1580 [HAILSTONE]

問題概要

初期値x[0] (500以下) が与えられるので,以下の手順によって,(有限の長さの)数列を作る.
 x[k]が1ならばx[k+1]は作らない
 x[k]が偶数ならばx[k+1] = 2*x[k]
 x[k]が3以上の奇数ならばx[k+1] = 3*x[k]+1
数列に登場する最大値を求める問題.

解法

やるだけ.

COJ 1579 - Bakugan [BAKUGAN] (この記事を編集する[管理者用])

Source

The 2011 Caribbean Finals of the ACM-ICPC - Warmup (2011-11-05)
COJ 1579 [BAKUGAN]

問題概要

2人で勝負する.R回戦 (10以下) 行う.得点の高いほうが勝利.勝者を求める問題.
各回,2人が1以上10以下の数字を提出する.(提出する数字は与えられる)
提出した数字が,そのままその人の得点に加わる.
また,3回連続して同じ数字を提出すると30点加わる.これは,最初に3回連続した人に1回のみ加えられ,2人が同時に達成したら2人に加わる.

解法

やるだけ.
少なくても現在は,サンプルインプットが壊れていて,サンプルが使えないので注意深く実装する.

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。