2016-04-15

九州大学プログラミングコンテスト2014 F. 設備移転

DP AtCoder

問題

F: 設備移転 - 九州大学プログラミングコンテスト2014 | AtCoder

2016-04-15

九州大学プログラミングコンテスト2014 D. 切符分割

Dijkstra AtCoder

研究室のプロコンでQUPC2014を1時間で解こうとしたら、3問しか解けなかった。

問題

D: 切符分割 - 九州大学プログラミングコンテスト2014 | AtCoder
電車の路線図が重み付き無向グラフG=(V, E)としてが与えられる。駅vから駅uまでの距離がd_vuであるとする。このとき駅v-u間の切符の値段は、要素数Kの数列x, fについて、1=x[0] <= d_vu < x[1]ならf[0]円, x[1] <= d_vu < x[2]ならf[1]円, ..., x[K-2] <= d_vu < x[K-1]ならf[K-2]円, x[K-1] <= d_vuならf[K-1]円とする。
このとき、2枚まで切符を使って良いとすると、スタート地点Sからゴール地点Gまで最小何円でたどり着けるか？

制約

2 <= |V| <= 30000
1 <= |E| <= 60000
1 <= K <= 100
x[i] < x[i+1] ならばf[i] < f[i+1]

2016-04-09

SRM540 div.1 250 ImportantSequence

topcoder

久しぶりに練習会に参加して、1完だった

問題

数列A = [a_1, a_2, ..., a_n]に対して、+と-のどちらかを間に挿入し、数列 B = [a_1 op_1 a_2, a_2 op_2 a_3, ..., a_(n-1) op_(n-1) a_n]とする。
(例) A = [1, 7, 5, 3]で、op = [-, +, +]とするとB = [-6, 12, 8]となる。
Aの各要素が正の整数であるとして、opとBが与えられたときに、もとの数列Aは何通りありうるか？(無数にある場合は-1と答えよ)

制約

Bの要素数は50以下

10^9 <= B_i <= 10^9

2016-04-09

SRM687 div.1 250 AlmostFibonacciKnapsack

topcoder

本番は参加できなかったので、ラボのプロコン*1で解いたけど、0完だった

問題

A[1]=2, A[2]=3, A[i+2]=A[i+1]+A[i]-1 となる数列を考える。このとき、あるxが数列Aの異なる要素の和で構成することができるか？
できる場合は、使った要素のインデックスを答えよ。

制約

xは2以上10^18以下

*1:今回は2人だけだった。少ない...

2016-03-09

Codeforces Round #345 Div.2 E / Div.1 C - Table Compression

強連結成分分解 DP codeforces

久し振りにRatedなコンテストに出て、div1で2問なんとか解いたけど、遅かったのでレートは微減した
div1は厳しい

問題

Codeforces Round #345 Div.1 C - Table Compression
要素が全て正のN行M列の行列Aが与えられる。これを各行・列の相対的な大小関係が等しい行列のうち、最大の要素が最小となるような行列A'を求めよ。
ここで行列AとA'の各行の相対的な大小関係が等しいとは、Aの要素a_{i,j}と行が同じ要素a_{i,k}と、それに対応するA'の要素a'_{i,j}とa'_{i,k}について、a_{i,j} < a_{i,k} ならば a'_{i,j} < a'_{i,k}、a_{i,j} = a_{i,k}ならば a'_{i,j} = a'_{i,k}、a_{i,j} > a_{i,k} ならば a'_{i,j} > a'_{i,k} が成立することである。(列に関しても同様)

制約

1<= N*M <= 10^6
1<= a_{i,j} <= 10^9

2016-02-17

AOJ2067 Flame of Nucleus

最大フロー AOJ

問題

Flame of Nucleus | Aizu Online Judge
頂点数N、枝数Mの重み付き単純無向グラフが与えられる。枝i(i=1, ..., M)の重みD_iは頂点間を移動する日数を表す。
現在の頂点i(i=1, ..., N)に滞在している人数P_iが与えられる。頂点i(i=1, ..., N)にL日後にK_i人以上住んでいる場合、K_i人以外は死ぬとする。
最適に移動した場合、最大何人生き残れるか？

制約

$1 \le N \le 100\\ 1 \le L, D_i \le 10^4\\ 1 \le P_i, K_i \le 10^6$

2016-01-11

SRM528 div.1 500 SPartition

DP topcoder

問題

SRM528 div.1 500 SPartition
偶数長の文字列sが与えられる。ここからsの各文字を、前から順番にX,Yのどちらかに振り分けていったとき、XとYが一致するような振り分け方は何通りか？

制約

$2 \le |s| \le 40$

2016-01-04

SRM659 div.1 250 ApplesAndOrangesEasy

尺取法 topcoder

問題

SRM659 div.1 250 ApplesAndOrangesEasy
各要素がリンゴかミカンである、要素数がNの列を考える。ここで、[i, i+K-1]の区間で列に含まれるリンゴの数を $\lfloor K/2 \rfloor$ 個以下に制限することとする。列において、要素が必ずリンゴであるインデックスの情報infoが与えられるので、制限を満たす列でリンゴは最大何個列に含まれうるか？