【Topcoder】Rookie SRM 6 のはなし
全体12位になってました。全体的に早解き回でした。
問題概要のところは日本語に雑に訳しました。一部、簡単のために少し変えたところがありますが許してください><
Easy - BiggestDuplicate (250 pts.)
問題概要
長さ の数列が与えられる。数列内に重複して存在する数のうち、最大の数を求めよ。そのような数が存在しない場合は -1 を返せ。
解法
と制約が小さいのでびっくり。降順にソートすれば、重複して存在する数どうしは隣り合うはずなので、1 番目から順にみていき、 番目と 番目の数が同じであるときは、 番目の数を返して終了すればよい。最後まで行って値を返さなかった時、重複する数が存在しないので、-1 を返して終了すればよい。
得点
249.33 pts. でした。なんか、もっと早く実装できた気がします。
Medium - LinearSignals (500 pts.)
問題概要
直線の道路があり、路上にいくつか信号が並んでいる。あなたは、左から の距離のところにいるとき、区間 ] 内の信号を全て一度に受け取ることができる。このとき、あなたは最大でいくつの信号を一度に受け取ることができるか?
解法
またも制約が小さいので、全部の位置でうまいこと全探索できる。添え字の限界を超えないよう注意するだけ。
得点
490.06 pts. でした。なぜかクソバグを繰り返したのでめっちゃ遅くなってしまいました。
Hard - SlowTerrain (1000 pts.)
問題概要
マップ上を歩く。'S' のマスから 'D' のマスまで行き、辺で隣り合う都市へ移動することができる。各都市のマスには 0 ~ 9 までの数字がどれか 1 つ書かれており、各都市内を移動するのにその数字だけ時間がかかることを示す。この時、'S' から 'D' まで到達できる最短時間を求めよ。
解法
基本的には dijkstra法でいける。各都市内の移動に時間はかからないと考えてよくて、各マスの数字は「隣接するマスからその都市へ行くのにその数字だけ時間がかかる」ことを示していると捉えてよい。こうすれば、頂点数もあまり多くならないので、全頂点について辺を張って、dijkstra 法を単純に回せば解ける。
得点
906.80 pts. でした。実装が遅すぎる!!!!!
全体を通して
早解きをもっと鍛えようね
東京海上日動プロコン(ARC122) A - Many Formulae
公式解説の解法とわたしがコンテスト中に思いついた解法が違ったので、解説をしてみます。たぶん、嘘解法ではなさそうです。
一応、解法は丁寧に解説しているつもりですが、お急ぎの方もいらっしゃるかと思い、最後の方に "解法まとめ" として、簡単に解法を書きましたので、そちらをご覧いただくだけでもかまいません。
問題
これをご覧ください
重要な事実
結論から言えば、私はコンテスト中にフィボナッチ数を用いた解法で通しました。フィボナッチ数には、この問題にかかわる次のような重要な事実があります:
'A' と 'B' を合計で 個、横一列に並べる。この時、'B' が隣り合わないように並べる方法は 通りある。( フィボナッチ数列の第 項)
なぜそうなるか、を証明した論文みたいなのはちょっと調べてないんですが(おい)、まあそうなるっぽいです。
解法
では、本題の方に移っていきましょう。
まず、作る式に項は 個あります。つまり、並べる符号の数は、合計で 個ですので、作ることができる良い式は全部で 通りです。なので、 として、 という値で初期化しておきます。( の値は、ちゃんと の値をとっておきます)
ここでは、 であるとします。
ここからどんな操作をしていくかというと、各項の値を、ある分だけ から引いていくという操作を全ての に対して行っていきます。とはいっても、 の符号は正から変えられないので、ここに対しては特に操作をする必要はありません。
ある分だけ引く、とはどういうことかというと、 の符号を負にした時に作れる良い式を としたとき、 回だけ を から引くということです。
なぜこの回数引くかというと、最終的にはありうるすべての良い式を足し合わせるわけで、そうすると各項の和は、次のように表されるからです:
これを式変形すれば、 となりますから、先ほどの回数だけ引くことが正しいと言えます。
さて、あとはこの の値が求まればいいわけですが、これは、先ほどのフィボナッチ数の性質を使えば、 の値は で求められます。
次のように、6 個の項の、3 番目の演算子が '-' になった場合を考えてみましょう。
赤の部分は演算子が '+' が確定しますが、青の部分は演算子が確定しません。この時、良い式は何通り作れるでしょうか。
正解は、4 通りです。当てはめてみれば、それはそうなんですが、左側の青の部分は演算子が 1 つ、右側の青の部分は演算子が 1 つ入るので、それぞれ演算子の入れ方は 通りずつになります。 ですから、良い式は より、4 通り作れる!となるわけです。
一般化してみましょう。第 項の符号を負にした時、上で言う左側の青の部分は、 個の演算子を並べることになります。そして、上で言う右側の青の部分は、 個の演算子を並べることになります。 ですから、 という計算をすればいいことになります。フィボナッチ数を前計算しておけば、各 は、 で求めることができます。
結果として、全体で でこの問題を解くことができました。
解法まとめ
- フィボナッチ数を、 として前計算しておく。
- 各 の値の総和と の積の値で、 を初期化する。
- の各 について、 を計算し、 から、 を引く。
- 3. を全ての について行った後の の値が、求める値である。
AC コード
解説用に、一応 1-indexed で書いてみました。
最後に
なにか疑問点があれば、Twitter の @Kanten4205 まで教えてください。
長くなってしまいましたが、最後までお読みいただき、ありがとうございました。
自己紹介みたいなやつ
AtCoder : Kanten4205
Codeforces : shunhattori2005
Topcoder : Kanten-4205
Codechef : kanten4205
Twitter :
Kanten4205 (@Kanten4205) | Twitter
こんにちは Kanten4205です
前のブログ、ログインできなくなっちゃってパスワード復元とかめんどくさいのでこっちに移りました これからはこっち使います よろしくです~
昔のブログ -> Kanten4205の競プロ精進ブログ (theblog.me)