世界Aと世界Bの時間の違いでの勉強時間計算
AtCoder Beginner Contest 117回目 A問題 エントランス・エグザミネーション
問題文 明日の入学試験に合格するために、太郎くんはあとT時間の勉強をする必要があります。
幸いにも、彼は今いる世界、世界AのX倍の速度で時間が進む世界Bへ世界超躍、ワールドリープすることができます。
世界BでX×T時間進むと、世界AではT時間進みます。 世界BでT時間勉強したとき、世界Aでは何時間進んでいるでしょうか。
平心と時の平和ですね。 入力はTとXが与えられます。
入力例1、8と3、出力例2.6666666、7。 3倍の速度で時間が進む世界Bで8時間勉強すると、世界Aでは2.6666時間進んでいます。
8÷3? 3÷8? 8÷3か。
入力例2、99と1だったら99.00008÷3だよね、これ多分。
プリント、8÷3、2.66666、OK。 なので、TとXをもらいます。
マップのイント、インプット、ドット、スプリット。 プリント、T÷Xで、どうだ?
はい、閉止したのでB問題に行きます。
B問題、ポリゴン問題文。 2次元平面上に辺の長さがそれぞれL1からLNのN角形。
何これ、でこ、多角形でなくても良い。 が書けるかを判定してください。
ここで次の定理を利用しても構いません。
定理、一番長い辺が他のN-1辺の長さの合計よりも真に短い場合に限り、条件を満たすN角形が書ける。
入力例はNとLの数字の配列。条件を満たすN角形が書けるなら、イエス、ソー、デナイラならノーを出力せよ。
入力例1、Nは4、4角形が3851で書けるかどうか、出力例はイエス。
8小なり9、イコール3たす5たす1なので、定理より二次元平面上に条件を満たすN角形が書けます。
一番長い辺が他のN-1辺の長さの合計よりも短い場合に限り、
だから、マックスを取ればいいのか。
Nイコールイントインプット、Lイコールリストのマップのイントインプットドットスプリット。
大文字のMイコールマックスLプリント、イエス、イフ、Mが小さければMより大きければなので、MサムLのマイナスMですね。
で、エルスのでどうでしょうか。
Lの合計からマックスを引いたものがマックスより大きければOKですね、ACでした。
新問題に行きます。
数直線上での最小移動回数の求め方
新問題、ストリームライン問題文。
数直線とN個のコマを用いて一人でゲームを行います。
はじめ、これらのコマをそれぞれ好きな整数座標に置きます。
この時、同じ座標に複数のコマを置いても構いません。
以下の移動を繰り返して、座標X1からXMのM個の地点すべてを、いずれかのコマで訪れることが目的です。
移動、コマを一つ選び、そのコマの座標をXとする。
そのコマを座標Xプラス1、もしくは座標Xマイナス1に移動する。
ただし、最初にコマを置いた座標は、その時点で訪れたとみなします。
目的を達成するまでに移動を行う回数の最小値を求めてください。
NとMで、下にXの数字配列、座標が与えられる。
入力例1はNMが2、5、Xが10、12、1、2、14、出力例は5。
以下の手順で5回移動を行うと目的を達成でき、この時が最小です。
はじめに2個のコマを、それぞれ座標1、座標12を置きます。
座標1のコマを座標2に移動。
座標10のコマを座標11。
11のコマを12。
12のコマを13。
13のコマを14。
Xがバラバラに置かれているから、一旦これソートしたほうがいいかな。
NM="map-int-input.split x="sorted-list-map-int-input.split".
コピペしちゃおう。めんどくさいから。
一旦確認。プリントX。
12、10、12、14の順に並びました。
これをどうすればいいんだ。
2分探索とか使えそうな予感はしますけどね。気持ち。
違うかな。
1個プラスするか1個マイナスするか。
DPか。目標を達成するために移動を行う最初の回数。
DPっぽいな。
1、2、10、10、12、14。
出力例は?
あ、そうか。N個のコマがあるんだ。
うわ、そうか。コマの数も考えないといけないの?
座標コマを1つ選び、そのコマの座標をXとする。
とりあえずNM。Nの方が大きかったら問答無用でゼロを出したらいいんだ。
FN、Dynally Call Mだったらプリント。
全部もうその時点で1個ずつの地点に置けばクリアなので。
エグジットして…じゃなかった場合だよね。
これどうすりゃいいんだ。
今11時13分なので15分まで悩みますね。とりあえずね。
入力例2。
37のマイナス10、マイナス3、0、9、マイナス100、27。
19回。
39、17。
DPっぽい気もするんだが、組み立て方がちょっと思いつかないですね。
座標に複数のコマを置いても構いません。
1個プラスか1個マイナスさせて、全ての目的地に訪れられるかどうか。
訪れられる場合は、られるかどうかっていうか訪れることはできるのか。
その数が途方もない数かどうかってことか。
最初、解説を見ます。
隣接する点に移動するというのと相当できるときは代替した方がいいのでXを相当する。
まずは最適行動について考えてみよう。
あるコマが担当する地点は区画の形になる。区間の形になる。飛び跳びになることはない。
ある区間が1つのコマの担当であるとわかった場合は、端を初期位置としてもう一方の端に向かわせればいい。
ここからグラフ問題のある問題へ帰着させる。
地点を頂点、相当後に隣接する地点の差を見てこれを辺と考える。
最初はM個の連結成分となっているが、ここからいくつかの辺を使って連結部分をN個にする。
辺を1つ採用することで連結成分が1つ減るので、移動回数を最小化するには辺のコストが小さい方からM-N個取ればいい。
総括すると、Xを相当して隣接する地点の差を取った配列Dを用意する。
この配列の小さい方からM-N個取ってきた相和が答え。
M-N小なり0の場合はM小なりNなので、持っているコマを全ての地点に置けるので0が答え。
うーん。解説コード例がシープラプラなので、ちょっと読み、読めない。
公式解説。
コマの数が目的地の数以上の場合、すなわちN大なりイコールMの場合、初めに各目的地に1つ以上のコマを配置できるので0回の移動で目的を達成できます。
以降、N小なりMとして考えます。
さらに、一般性を失わずにX1小なりX2小なりXMと相当されていると考えていいです。
実装では入力された座標を相当します。
ある1つのコマに着目したとき、移動を通して訪れる座標は区間になります。
同じこと言ってますね。
逆に、ある区間の整数座標すべてをある1つのコマで訪れる場合、区間の一端に最初に配置し、もう一端に向かって移動し続けるのが最適です。
また、複数のコマが同じ座標を訪れるのは無駄です。
従って、各コマが担当する区間を並べると、ちょうどN-1個の開区間が訪れられていない形になります。
LIイコールXIプラス1マイナスXIとすると、その時の合計移動回数は、
XM-X1マイナス訪れられていない開区間のLIの和となるため、
訪れられていない開区間のLIの和を最大化すればいいです。
これは、LIを大きい方からN-1個取るのが最大です。
計算量は相当がボトルネックとなり、オーダーMログMです。
なんのこっちゃですね。
Python使っている他のユーザーの方のAC正解例を見て、勉強しておきたいと思います。
今回はここまで。お疲れ様です。ではまた次回お会いしましょう。さよなら。