F - カード集め
Editorial
/
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
机の上に N 枚のカードがあり、それぞれ 1 から N まで番号付けられています。
これらのカードを用いて 2 人で以下のゲームを行います。
- 先手から交互にカードを 1 枚ずつ机の上から取ります。
- 机の上のカードが全て取られたらゲームは終了します。
その後、以下のルールに従ってスコア計算を行い、勝者を決定します。
- i (1 \leq i \leq N) 番目のカードを取ったプレイヤーがスコア s_i を得る。
- i = 1, 2, ..., M について、a_i 番目のカードと b_i 番目のカードをどちらも取ったプレイヤーがスコア c_i を得る。
その結果、合計スコアが大きいプレイヤーが勝者となり、合計スコアが同じ場合は後手が勝者となります。
勝者となるためにお互いが最適に行動したとき、どちらが勝者となるでしょうか。
制約
- 入力は全て整数である。
- 2 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 1 \leq a_i < b_i \leq N
- 1 \leq s_i, c_i \leq 10^9
入力
入力は以下の形式で標準入力から与えられる。
N M s_1 s_2 ... s_N a_1 b_1 c_1 a_2 b_2 c_2 : a_M b_M c_M
出力
先手が勝者となる場合 First
を、後手が勝者となる場合 Second
を出力せよ。
入力例 1
4 4 1 20 30 10 1 2 40 1 3 30 1 4 50 2 3 100
出力例 1
First
- 先手は初めに 1 番目のカードを取ります。
- 次に、後手が 2 番目のカードを取った場合を考えます。
- このとき、先手は 3 番目のカードを取ります。
- すると、後手は 4 番目のカードを取るしかありません。
そのときの合計スコアは次のようになり、先手が勝者となります。
- 先手は 1 番目と 3 番目のカードを取ったので、先手の合計スコアは 1 + 30 + 30 = 61 です。
- 後手は 2 番目と 4 番目のカードを取ったので、後手の合計スコアは 20 + 10 = 30 です。
他の場合も先手が上手く取ることで、先手が勝者となります。
入力例 2
6 10 16 14 5 2 6 11 1 2 17 1 3 8 1 6 7 2 3 2 2 4 1 2 6 9 3 4 3 3 5 2 4 5 17 5 6 26
出力例 2
Second
入力例 3
10 9 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1 2 1000000000 2 3 1000000000 3 4 1000000000 4 5 1000000000 5 6 1000000000 6 7 1000000000 7 8 1000000000 8 9 1000000000 9 10 1000000000
出力例 3
Second