TopCoder SRM 399 DIV 2
| Problem | Check | Points |
| 250 | o | 221.74 |
| 500 | o | 452.09 |
| 1000 | - | 330.03 |
500を過去最高のスピードで解けたので良かった。
Problem 250 CircularLine
There's a circular subway line that contains n stations numbered 0 through n-1. The time to travel between stations 0 and 1 is t[0], the time to travel between stations 1 and 2 is t[1], ..., the time to travel between stations n-1 and 0 is t[n-1]. You can travel between stations in either direction, so there are always two ways to get from one station to another without visiting the same station more than once. For example, if there are 4 stations, the two ways of getting from station 1 to station 3 are 1-2-3 and 1-0-3. The total travel time in the first case is t[1] + t[2], and in the second case, it is t[0] + t[3]. When a person needs to get from one station to another, she always chooses the faster of the two ways.
You are given a int[] t. Find two stations such that the fastest travel time between them is the maximal possible. Return this time.
はじめに路線全部の合計を計算しておくと、2通りの距離を計算するのが楽。
Problem 500 MaximalProduct
You are given an integer s and an integer k. Find k positive integers a1, a2, ..., ak such that their sum is equal to s and their product is the maximal possible. Return their product.
グラフ理論をやったときに、こんな話があったのですぐ書けた。
TopCoder SRM 399 DIV2 Problem500 MaximalProduct
Problem 1000 AvoidingProduct
You are given a set A of integers and a positive integer n. You must find positive integers x, y and z such that their product is as close to n as possible (minimize |n - x * y * z|), and none of them belongs to A. If there are several such triples, find the one with the smallest x. If there are still several such triples, minimize y. If there is still a tie, minimize z.
You are given the elements of A as a int a. Return a int with exactly three elements: x, y and z, in this order.
for文の範囲をnまでとしていて間違えた。nの値が1000まででも、x*y*zが1000までとは限らない。x=1, y=1, z=1001 が解になる場合がありえる。
