Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
長さN の整数列 A_{0}, …, A_{N-1} が与えられます。この数列は小さい値から順番に並ぶようにソートされています。
また、整数 K が与えられます。A_{i} \geq K であるようなインデックス i のうち、最小のものを出力してください。ただし、そのような i が存在しない場合は -1 を出力してください。
制約
- 1 \leq N \leq 10^5
- 1 \leq K \leq 10^9
- 1 \leq A_{0} \leq \cdots \leq A_{N-1} \leq 10^9
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N K
A_{0} A_{1} \cdots A_{N-1}
出力
A_{i} \geq K であるようなインデックス i のうち、最小のものを出力してください。ただし、そのような i が存在しない場合は -1 を出力してください。（問題文のインデックスが 0 始まりである点に注意してください）
入力例 1
8 4 1 3 5 7 9 11 13 15
出力例 1
2
入力例 2
5 1000000000 1 2 3 4 5
出力例 2
-1
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
N 個のタスクがあります。i 個目のタスクは A_{i} 日目の朝に始まり、B_{i} 日目の夜に終わります。その間の日は全てそのタスクに専念する必要があります。
あなたはこれらのタスクを自由に選んで実行することができます。ただし、同じ日に複数のタスクを行うことはできません。実行可能なタスクの個数の最大値を求めてください。
制約
- 1 \leq N \leq 2\times 10^5
- 1 \leq A_{i} \leq B_{i} \leq 10^9
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N
A_{1} B_{1}
A_{2} B_{2}
:
A_{N} B_{N}
出力
実行可能なタスクの個数の最大値を出力せよ。
入力例 1
3 1 5 4 6 6 8
出力例 1
2
1 番目と3 番目のタスクを実行することができます。3 つのタスクを全て行うことはできないので、2 が最大値となります。
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
N 個の都市があり、0, 1, …, N-1 と番号付けられている。全ての異なる 2 都市の間には道が存在し、都市 i から都市 j に移動するときのコストはA_{i,j} である。
あなたは今都市 0 にいる。ここから都市 0 以外の都市をちょうど 1 回ずつ訪れ、都市 0 に戻ってくる経路を作りたい。そのような経路における合計コストの最小値を求めよ。
制約
- 2 \leq N \leq 13
- i \neq j のとき、1 \leq A_{i, j} \leq 10^9
- A_{i, i} = 0
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N
A_{0, 0} A_{0, 1} ... A_{0, N-1}
A_{1, 0} A_{1, 1} ... A_{1, N-1}
:
A_{N-1, 0} A_{N-1, 1} ... A_{N-1, N-1}
出力
都市 0 からスタートし、都市 0 以外の都市をちょうど 1 回ずつ訪れ、都市 0 に戻ってくる経路における合計コストの最小値を求めよ。
入力例 1
4 0 3 1 4 1 0 5 9 2 6 0 5 3 5 8 0
出力例 1
12
都市 0 \to 2 \to 3 \to 1 \to 0 と移動すると、合計コストは 1+5+5+1=12 となり、これが最小である。
Time Limit: 2 sec / Memory Limit: 1024 MiB
問題文
N個の街があり、0, 1, 2, ..., N-1と番号がついています。また、M本の道があり、0, 1, 2, ..., M-1と番号がついています。
道iは街u_iから街v_iへの一方通行の道で、通るのにc_i分かかります。街0から1本以上の道を通って街N-1に到達できることがわかっています。
街0から街N-1まで移動するとき、必要な時間の最小値を出力してください。
制約
- 入力は全て整数である
- 2 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 0 \leq u_i, v_i \lt N (0 \leq i \lt M)
- u_i \neq v_i (0 \leq i \lt M)
- 0 \leq c_i \leq 10^9 (0 \leq i \lt M)
- 街0から1本以上の道を通って街N-1に到達できる
入力
入力は以下の形式で標準入力から与えられる。
N M
u_0 v_0 c_0
u_1 v_1 c_1
:
u_{M-1} v_{M-1} c_{M-1}
出力
街0から街N-1まで移動するために必要な時間の最小値を出力せよ。
入力例 1
3 4 0 1 1 1 0 2 1 2 3 2 0 4
出力例 1
4
与えられる入力は下図のようになっています。
街0から街1へ道0を使って1分で移動し、街1から街2へ道2を使って3分で移動することで、合計4分で移動できます。
Time Limit: 2 sec / Memory Limit: 1024 MiB
問題文
N個の街があり、0, 1, 2, ..., N-1と番号がついています。また、M本の道があり、0, 1, 2, ..., M-1と番号がついています。
道iは街u_iから街v_iへの一方通行の道で、通るのにc_i分かかります。どの街からも、他の任意の街へ到達できることがわかっています。
全ての (i, j) (0 \leq i, j \lt N) の組について、街iから街jまで移動するのに必要な時間の最小値を求め、その合計値を出力してください。
制約
- 入力は全て整数である
- 2 \leq N \leq 100
- 1 \leq M \leq 10^5
- 0 \leq u_i, v_i \lt N (0 \leq i \lt M)
- u_i \neq v_i (0 \leq i \lt M)
- (u_i,v_i)\neq (u_j, v_j) (i \neq j)
- 0 \leq c_i \leq 10^9 (0 \leq i \lt M)
- どの街からも他の任意の街へ到達できる
入力
入力は以下の形式で標準入力から与えられる。
N M
u_0 v_0 c_0
u_1 v_1 c_1
:
u_{M-1} v_{M-1} c_{M-1}
出力
街iから街jまで移動するために必要な時間の最小値を、全ての (i, j) (0 \leq i, j \lt N) の組について求め、その合計値を出力せよ。
入力例 1
3 4 0 1 1 1 0 2 1 2 3 2 0 4
出力例 1
19
与えられる入力は下図のようになっています。
- 街0から街1へは1分で移動できます。
- 街0から街2へは4分で移動できます。
- 街1から街0へは2分で移動できます。
- 街1から街2へは3分で移動できます。
- 街2から街0へは4分で移動できます。
- 街2から街0へは5分で移動できます。
よって合計で19分となります。
Time Limit: 2 sec / Memory Limit: 1024 MiB
問題文
N個の街があり、0, 1, 2, ..., N-1と番号がついています。最初、これらの街の間に道はなく、街と街を行き来することはできません。
道の候補がM個あります。i番目の道を建設するには建設費がc_i円かかりますが、建設すると街u_iと街v_iを双方向に結ぶ道ができ、行き来できるようになります。
M個の道の候補からいくつか選んで建設し、ある街から別の任意の街へ道をたどって到達できるようにしたいです。そのように道を選んで建設するために必要な建設費の最小値を求めてください。
制約
- 入力は全て整数である
- 1 \leq N \leq 10^5
- 0 \leq M \leq 10^5
- 0 \leq u_i, v_i \lt N (0 \leq i \lt M)
- u_i \neq v_i (0 \leq i \lt M)
- 0 \leq c_i \leq 10^9 (0 \leq i \lt M)
- ある街から別の任意の街へ道をたどって到達できるようにする道の選び方が必ず存在する
入力
入力は以下の形式で標準入力から与えられる。
N M
u_0 v_0 c_0
u_1 v_1 c_1
:
u_{M-1} v_{M-1} c_{M-1}
出力
ある街から別の任意の街へ道をたどって到達できるようするための、必要な建設費の最小値を出力せよ。
入力例 1
5 7 0 1 10 0 4 30 1 2 10 1 4 20 2 3 30 4 2 20 4 3 10
出力例 1
50