はまやんはまやんはまやん

hamayanhamayan's blog

Parentheses [JAG Practice Contest for ACM-ICPC Asia Regional 2016 : D]

競技プログラミング

問題

http://jag2016autumn.contest.atcoder.jp/tasks/icpc2016autumn_d

「(」と「)」から構成された文字列があり、以下の条件を満たす文字列を答えよ

  • A回隣接する文字をスワップすると括弧の対応が取れた文字列が作れる
  • B(
  • 複数回答があれば、その中で文字列長が最短で、かつ、辞書順最小
  • ちなみに'(' < ')'

1 <= A <= 10^9

続きを読む

Help the Princess! [JAG Practice Contest for ACM-ICPC Asia Regional 2016 : B]

競技プログラミング

問題

http://jag2016autumn.contest.atcoder.jp/tasks/icpc2016autumn_b

縦H,横Wの地図がある。
@ : 姫の初期位置
$ : 兵士の初期位置
% : ゴール
. : 通路
# : 壁
各ステップ、姫と兵士は隣接する通路に1マスだけ進むかその場にとどまるか選択できる。
姫と兵士が同じマスにいると姫は捕まる。
兵士がどんな動きをしても姫が脱出できるなら"Yes"、できないなら"No"

2 <= H, W <= 200

続きを読む

Best Matched Pair [JAG Practice Contest for ACM-ICPC Asia Regional 2016 : A]

競技プログラミング

問題

http://jag2016autumn.contest.atcoder.jp/tasks/icpc2016autumn_a

N個の数列がある。
これから2つ選んで積をとる。
その中で、文字列として見た時に、連続で増加している積の中で最大のものは？
連続で増加している例））2, 23, 56789
連続で増加していない例） 21, 334, 135, 89012

1 <= N <= 10^3
1 <= a[i] <= 10^4

続きを読む

高橋くんとホテル / Tak and Hotels [ARC 060 : E]

競技プログラミング

問題

http://arc060.contest.atcoder.jp/tasks/arc060_c

N軒のホテルがある。
i軒目のホテルはx[i]の位置にある。
以下の条件を満たして移動する。

  • 1日の移動距離はL以下
  • 1日の終わりには必ずホテルにいる

この時、Q個の以下のクエリが与えられる。
a[i]番目のホテルからb[i]番目のホテルに移動するのにかかる最短日数を出力せよ。

2 <= N <= 10^5
1 <= L <= 10^9
1 <= Q <= 10^5

続きを読む

Coloring Trees [Codeforces 369 : Div2 C]

競技プログラミング

問題

http://codeforces.com/contest/711/problem/C

n本の木がある。
これらの木をm種類の色で塗る。
木iは色C[i]で塗られているが、一部(C[i]=0のもの)は色が塗られていない。
塗られていない木に色を塗っていくのだが、木iに色jを塗るときはp[i][j]のインクが必要。
木達の美しさを隣り合う色が同じ木をまとめた成分数と定義する。

2,1,1,1,3,2,2,3,1,3
であれば、隣り合う色が同じ木をまとめると
{2}, {1, 1, 1}, {3}, {2, 2}, {3}, {1}, {3}
となり成分数は7なので、美しさは7

この時塗られていない木を塗って、美しさをkとする時に必要な最小インク総数は？
不可能なときは-1を出力。

1 <= k <= n <= 100
1 <= m <= 100
0 <= c[i] <= m
1 <= p[i][j] <= 10^9

続きを読む