TopCoder SRM 477 (Div 1)
500二回リサブミットして終わったかと（ｒｙ
Easy
問題
正六角形のグリッドで表される国がある。
国の陸地と海が文字列により与えられるとき、この国の海岸線の長さを求めよ。
ただし、グリッドが正六角形であるため、（0から数えて）奇数番目の列は1/2だけ右にずらして考えよ。
試行錯誤
Maja座標系の出番！と思ったら交互に列を半分ずらすタイプのHexだった。
それぞれのマスについて6個の近傍を全てみて、陸-島or島-陸だったら長さを+1する。
それぞれの海岸線は丁度二回ずつ数えられるため、最終的な答えは合計を2で割ったもの。
奇数列の上下を見るときは一個右を見てやればよい。
書いた。答えあわない。ずらすの間違ってるのかなあ。。。
あ、「奇数列の上下」見るときじゃなくて奇数列みるとき全部ずらしてる。
訂正。
あれ、合わないぞ……ってこれじゃ、奇数列の左右見るときだけずらすことになるじゃんorz
訂正。合った。これはサンプル親切だし落とさないだろう。サブミット。
Medium
問題
原始ユークリッド数とは以下のような自然数の組(a,b,c)のことを言う
- a*a+b*b=c*c
- a,b,cの最大公約数は1
自然数のリストが与えられるとき、その中から原始ユークリッド数の(a,b)になるものを最大いくつ取ることができるか求めよ。
試行錯誤
DPか二部マッチング？
えーと、原始ユークリッド数だからa,bの偶奇は異なるはずで、数を奇数と偶数に分けてマッチングさせれば二部グラフの最大マッチングになるから解ける。
書いた。サンプル通った。手拍子で送信ー。
420点で……うおっ、2桁前半順位行くんじゃ！
見直す。
あ、スティックの数が最大50じゃないぞこれ！！vector<string>の要素の数が最大50とか陰険すぎるだろ！
100しか確保してなかったので1000にする。
あ、でも999999^2ってintあふれるじゃん……結局修正しないとダメだ。
修正。送信。340点になった。しょぼーん。
Hard開いて、全く方針が立たないのでもう一度もどってきた。
更に見直す。
……あ、gcd!=1のチェックしてないいいいいいいい！！！
相当なやってしまった感。訂正。更に更に再送信orz
220点とか……終わった。
Hard
問題
n個の都市がいくつかの双方向に通行可能な道路で接続されている。
都市0から、全ての道路を通る（向きは問わない）観光をしたいが、以下のようなショートカットがK回可能である。
- 好きな都市から都市へLの長さで行ける
- 同じショートカットを2度使ってはいけない
- 元から道路がある都市から都市へもショートカットできる
このとき、条件を満たす観光のうち、最小の全長を求めよ。
試行錯誤
わかんね。
Challenge
int桁あふれ、gcd!=1のチェック漏れを探す。
いた。撃墜。
うお、みんなどんどん撃墜してる。僕にも取り分をよこせー。
10分後、もう一個桁あふれを見つける。撃墜。
ソースがスパゲッティすぎて発見されてなかったようだ。
System Test
両方通った！
