WARushスマートフォン用の表示で見るWARushSRMの結果とか、解けた問題のコードを書いていきますこの広告は、90日以上更新していないブログに表示しています。"History"問題http://community.topcoder.com/stat?c=problem_statement&pm=12692訳N個の古代国家があった。'Z')全ての国家は同じカレンダーを使用していた。それぞれの国家で、同じ日で新しい年が始まっていた。それぞれの国家で、年数は独自のものだった。125年に対応していたりした。それぞれの国家では、その歴史において、幾人かの君主が統治していた。各国家において、君主は年代順に、0から番号付けされている。"C0"は国家Cで一番初めに統治していた君主の時代を表す。各君主は年の最初の日から統治を始めている。各君主が統治をし始めた(その国における)年が、正確に分かっている。マナオはこれらの国々の年代が、互いにどのように対応しているのかを解明したい。これを行うにあたり、彼は歴史上のさまざまな戦争についての情報を集めた。それぞれの戦いは、2つの国家間で行われていた。"C0-D3"と言う情報は、"C0"と"D3"で戦いが起こっていたことを意味する。この戦争があったという情報は、"C0"と"D3"の2つの君主が、同じ年に統治していた事があった、と言う事を物語っている。マナオは複数のクエリに答えなければならない。各クエリは"与えられた情報から、XnとYmの間で戦争が起こった可能性はあるか?"というものである。queriesで表された、上記の情報が与えられる。iの君主の統治をし始めた年数を表す。63"であれば、国家'A'は"A0"が42-46年に、"A1"が47-54年に、"A2"が55-62年に統治をしていたことを表す。battlesを連結して1つの文字列にしたとする。この文字列はスペース区切りで、歴史上起きた戦争の情報を、上記のフォーマットで表したものとなる。queriesの各要素はbattlesと同じフォーマットで、1つの戦争を表す。各クエリにおいて、その2つの国家間で、戦争が起こっていた可能性があるのなら'Y'を、そうでなければ'N'を返せ。国家ABにおける、年のズレの可能性を、プラス方向とマイナス方向でそれぞれ計算する。もらった情報から、まず直接的なズレの範囲を計算し、それからワーシャルフロイドで間接的なもの含めて、ズレの範囲を狭めていく。"ABBADiv1"月別アーカイブリンクはてなブログブログをはじめる(無料)お知らせはてなブログをはじめよう!Ekaingさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。