プチコン 非公式コミュニティ
トピック
こういち
◆ou0jbJnEJ0Kb
2020/6/14 23:08
2020/6/14 23:08
コンテスト
問題
光遺血ちゃんは、ある建物を破壊する任務を受けました。
建物は非常に頑丈で、専用の爆弾を使わないと破壊できません。
爆弾は建物のある場所に到達すると自動的に爆発し、建物を破壊しますが、爆弾は非常に重く、非力な光遺血ちゃんにとって運ぶのは大変です。
偶然にもあちこちに大砲が設置されており、これを使えば楽に運べそうです。
光遺血ちゃん、建物、N個の砲台は一直線上に並んでおり、始点から距離がLの地点に建物があります。
また、始点からD_iの距離に砲台iがあり、射程がR_iです。
光遺血ちゃんは、以下の2つの行動を繰り返し、建物に爆弾を運びたいです。
・距離1ごとに1のエネルギーを消費し、前方に歩いて爆弾を運ぶ。
・砲台がある場所に居る場合、1のエネルギーを消費し、大砲を使用することが出来る。使用する場合、前方に射程の距離だけ爆弾を移動させる。
光遺血ちゃんが建物に爆弾を運ぶのに最低でどれだけのエネルギーが必要か答えなさい。
建物は非常に頑丈で、専用の爆弾を使わないと破壊できません。
爆弾は建物のある場所に到達すると自動的に爆発し、建物を破壊しますが、爆弾は非常に重く、非力な光遺血ちゃんにとって運ぶのは大変です。
偶然にもあちこちに大砲が設置されており、これを使えば楽に運べそうです。
光遺血ちゃん、建物、N個の砲台は一直線上に並んでおり、始点から距離がLの地点に建物があります。
また、始点からD_iの距離に砲台iがあり、射程がR_iです。
光遺血ちゃんは、以下の2つの行動を繰り返し、建物に爆弾を運びたいです。
・距離1ごとに1のエネルギーを消費し、前方に歩いて爆弾を運ぶ。
・砲台がある場所に居る場合、1のエネルギーを消費し、大砲を使用することが出来る。使用する場合、前方に射程の距離だけ爆弾を移動させる。
光遺血ちゃんが建物に爆弾を運ぶのに最低でどれだけのエネルギーが必要か答えなさい。
コメント
こういち
2020/6/14 23:09
◆ou0jbJnEJ0Kb
入力は以下の形式で与えられる。
N,L
D_0,R_0
D_1,R_1
…
D_(N-1),R_(N-1)
制約
1<N<1000
1<L<10000
0<=D_i<=L
0<=R_i<=L-D_i
入力は全て整数で与えられる。
N,L
D_0,R_0
D_1,R_1
…
D_(N-1),R_(N-1)
制約
1<N<1000
1<L<10000
0<=D_i<=L
0<=R_i<=L-D_i
入力は全て整数で与えられる。
こういち
2020/6/14 23:11
◆ou0jbJnEJ0Kb
もうちょっと難しい問題にしようと思ってたけど、思ったより簡単な問題になってしまった。
ボクの実力不足だな。もっと強くならねば…
ボクの実力不足だな。もっと強くならねば…
こういち
2020/6/15 0:07
◆ou0jbJnEJ0Kb
大事な情報忘れてたので補足。
光遺血ちゃんは、最初距離0の地点に居るものとします。
光遺血ちゃんは、最初距離0の地点に居るものとします。
SatoshiMcCloud
2020/6/15 18:49
◆Z1qfV11i63Jr
質問です。
爆弾を持ってないときの光遺血ちゃんは、移動するときのエネルギーは0ですか？
爆弾を持ってないときの光遺血ちゃんは、移動するときのエネルギーは0ですか？
こういち
2020/6/15 19:42
◆ou0jbJnEJ0Kb
SatoshiMcCloudさん
はい。その通りです。
あるいは、砲台で光遺血ちゃんごと爆弾を飛ばしていると考えてもらっても問題ありません。
いずれにせよ、爆弾を移動させるときにのみコストがかかります。
はい。その通りです。
あるいは、砲台で光遺血ちゃんごと爆弾を飛ばしていると考えてもらっても問題ありません。
いずれにせよ、爆弾を移動させるときにのみコストがかかります。
うょリウム(元 SPDX)
2020/6/16 8:04
◆UTOEg1c1vr.B
まったくどうでも良いのですが
最後の移動が大砲でなかったとき
光遺血ちゃんは助かるのだろうか…
最後の移動が大砲でなかったとき
光遺血ちゃんは助かるのだろうか…
こういち
2020/6/16 8:52
◆ou0jbJnEJ0Kb
うょリウムさん
光遺血ちゃんは爆発マニアなので、きっと大丈夫でしょう。(本当に？)
光遺血ちゃんは爆発マニアなので、きっと大丈夫でしょう。(本当に？)
こういち
2020/6/16 10:03
◆ou0jbJnEJ0Kb
真面目な話、爆発の周辺は破片とか飛んで危険だけど、爆発の中心はそれがないのでわりと安全。(真面目とは)
うょリウム(元 SPDX)
2020/6/17 1:03
◆UTOEg1c1vr.B
結果
自分が破片になる。
自分が破片になる。
こういち
2020/6/19 13:14
◆ou0jbJnEJ0Kb
うょリウムさん
超常現象…？
超常現象…？
うょリウム(元 SPDX)
2020/6/20 0:27
◆UTOEg1c1vr.B
爆発の中心にある物が
破片となって飛び散るのでは？？
破片となって飛び散るのでは？？
こういち
2020/6/29 0:21
◆ou0jbJnEJ0Kb
結構前ですが、新たな問題を投稿しました。
新たな問題が投稿されたので、いつものように解説書きます。
http://petitverse.hosiken.jp/community/petitcom/topic/?read=1507&ukey=0
新たな問題が投稿されたので、いつものように解説書きます。
http://petitverse.hosiken.jp/community/petitcom/topic/?read=1507&ukey=0
こういち
2020/6/29 0:29 ネタバレ
◆ou0jbJnEJ0Kb
コメントを書く
- こちらは「プチコン3号」「プチコンBIG」など、プチコンシリーズに関する話題を扱ったコミュニティです
- プチコンシリーズにまったく関係ない書き込みはご遠慮下さい。削除の対象となります
- こちらにはその他のゲームや雑談のコミュニティはなく、作る予定もありません (ひとりで管理できないため)。ごめんなさい
- ユーザー登録なしで書き込みができます
- 秘密の合い言葉は成りすましの防止 (トリップ機能)、書き込みの編集時の本人認証に使用します
- 秘密の合い言葉に他人に推測されやすい言葉、他サービスと同じパスワードは入力しないでください。
- 書き込むと、投稿時に入力したお名前と秘密の暗号が記憶され、ログイン状態になります