WARushスマートフォン用の表示で見るWARushSRMの結果とか、解けた問題のコードを書いていきますこの広告は、90日以上更新していないブログに表示しています。新入生であるウサギ達はウナギクラブに入った。このグループには誰一人、知り合いはいなかった。昨日、初めてウサギ達はクラブに参加した。あなたはintのsとtが与えられる。s[i]はi番目のウサギがクラブに顔を出した時間であり、t[i]はi番目のウサギがクラブを立ち去った時間である。それぞれのウサギのペアは、同じ時間にクラブにいれば、お互いを知る事になり、彼らは"Shoutter"というソーシャルネットワークサービスで友達登録をする。瞬間に一緒にいることになったケースでもこれは当てはまる。(例えば、一匹がクラブに入り、一匹がその瞬間クラブを出た場合でも)"Shoutter"にて、そのユーザーは短いメッセージをいつでも叫ぶことができる。その叫びは友達であれば読むことができる。友達は叫びを再投稿する事ができ、再投稿した人の友達は叫んだ人の友達でなくとも、その叫びを読むことができる。その時、彼らはさらに再投稿する事ができ、それは続いていく。叫びは好きなだけ再投稿する事ができる。ウサギが叫びを複数回再投稿したいときは、別々に行わなくてはならない。今日、ウサギたちは各自、"Shoutter"で自己紹介を投稿した。各ウサギは他全てのウサギ(現在友達でないものも含め)の自己紹介を読みたい。最小何回の再投稿が必要なのかを計算し、返せ。不可能であれば-1を返せ。全てのs1000を連結し、S1000とせよ。i番目の文字はi番目のウサギに対応する。S1[i]と連結しそれを整数に変換する。t1についても同じようにせよ。9999考えた事(アホゥ)ウサギが50匹か~。ワーシャルフロイドしてそれの一番最長のやつ-1でいいんじゃないかなぁ(マジ謎)。あれ?ウサギは実は2500匹か~。全員が!Receiveするまで!僕は!叫ぶのを!やめ!ない!というわけで、Receiveする人を左右に伸ばしていく感じになります。同じかさらに右のtを持つものが叫べばそれぞれよい事になります。Receiveした人が下図のような時に一体誰に叫ばせればいいのでしょうか?答えはこんな感じで最も左または右に伸ばせる人に頼めばよいのです。よって、あらかじめ次誰に頼むよリストを作っておいてから、それぞれの人で叫ぶ回数を数えていけばよいです。誰に頼むよリスト(左判)誰に頼むよリスト(右判)ところで、まだ目標に届いていないのに、一番左へ(または右へ)伸ばせるのが自分自身だった場合、これは全員にReceiveさせることが無理なので、-1を返せばよいです。これでOKかと思いきや下図の場合を考えてみてください。上の人に頼めば1発でやってくれる訳です。自分自身をすっぽり覆う人がいた場合、説明したセオリーが通じない可能性がでてきます。最初の一回だけ、すっぽり覆う人を試して、後はセオリー通りやればよいです。自分自身以外をすっぽり覆っているやつがあっても、それはソイツがただ単により左に(または右に)伸ばせる人になるだけだからです。自分を含んで入れ子になっていたら、範囲を大きいほうをとればいいだけです。最初に一回だけ、自分をすっぽり含んでるやつを全部試せば良いと言う事です。セオリー通りに全員試しておいて、すっぽり含んでいるやつを試すときはそれに+1すればよいです。それらの最小値をとっていけば答えとなります。"ABBADiv1"月別アーカイブリンクはてなブログブログをはじめる(無料)お知らせはてなブログをはじめよう!Ekaingさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。