00:03
東京海上日動 プログラミングコンテスト2020
A問題 ニックネーム
A問題 ニックネーム
問題文 あなたは同じ授業を受けている男性に名前を尋ねました。彼はSと名乗りました。
Sは英語文字からなる長さ3以上20以下の文字列です。
あなたはSから適当に連続する3文字を選んで、彼のあだ名とすることにしました。
彼のあだ名として適切な文字列を一つ出力してください。
入力例1、高橋の場合はTAK、入力例2、直博の場合はNAOですので、
SイコールインプットプリントSのカンマ0123かな?
2文字目までを出力でいかがでしょうか?
これでも3文字、あ、いけた。 延伸しましたのでB問題いきます。
B問題 タグ
問題文 2人の子供が数直線上で鬼学校をしています。
鬼学の子供は今座標Aにいて1秒あたり距離V移動することができます。
また鬼から逃げている子供は今座標Bにいて1秒あたり距離W移動することができます。
鬼学の子供は相手と同じ座標にいるとき相手を捕まえることができます。
今からT秒の間に、ちょうどT秒後も含む、鬼学の子供がもう一方の子供を捕まえることができるかどうかを判定してください。
ただし2人の子供は最適に動くとします。
A、V、B、W、そしてTが与えられます。
鬼が捕まえることができるなら全部大文字のYes、そうでないなら全部大文字のNoと出力。
入力例1、1、2、3、1、3秒後ですね。
座標、鬼学の子供。
まず鬼学の子が逃げる役の子とより早く動かないといけないから、
だからVとWだったらVの方が大きくないといけないんですね。
ちょっとのどいがらっぽいな。
失礼しました。
だから大前提としてこれは判定しておかないといけないね。
AとVイコールマップのイント、インプット、ドットスプリット。
BとWも同じコードをコピーします。
B、W。
タイム、Tイコールイント、インプット。
入力例を一応コピーしておいて。
IfVがWより小さかったら、その時点でExitですね。
Exit、プリント、No。
で、なかった場合だ。
1秒で2、違う、2。
今1にいて1秒に2個動ける。
今3にいて1秒に1個動ける。
これはどういうあれをすればいいんだ?
制約。
AとBは同じではない。
4パターンぐらい考えるか。
Aの、どうやるかな。
今座標1にいる鬼役の子が3秒間、1秒に2動くので、
2×3の6をプラスした7の座標と、
2×3の6をマイナスした座標、マイナス5を取る。
で、同じくBの3の座標にいる子も1秒に1個動くので、
3秒プラスして3×3の6と、マイナスした0と取る。
で、その差を求めて、ちっちゃかったらYesみたいなのを考えたんですけど、
それでいいか。
1回それでやってみるか。
AP、Aプラスイコール、
AプラスV×T。
BPイコールBプラスV×W。
Vじゃないわ。W×T。
で、マイナスパターンも作ります。
AMとBMは、
AプラスマイナスV×Tってどういう風に表記したらいいんだ?
カッコで括りゃいいのか?
カッコカッコにすりゃいいのか?
あ、消えちゃった。
マイナスカッコW×T。
で、IF APがBPよりダイナリーイコールだったらというのと、
OR AMが超ナリーイコールBMだったらプリントYes。
そうでなければプリントNoでいいんじゃない?
出力例1はYes。
出力例2は?
なんか違う気がするけど、Yesが出たのは違うな。
出力例2でYesが出る?なんで?
2。出力例2。
1232の3。
座標32で32が6。
9。2×3が6。7。
どっちに引っかかってるかちょっと。
プリント。
どのYesに引っかかってるか。これだな。
AM超ナリーイコールBM。
AMとBMを出力。
マイナス5とマイナス3。
そうだね。マイナスだね。32が。
そうか。マイナスしても。
うーん。
いやこれマイナスする理由ないかもしかして。
AとBってどうなってる?
AがBより小さいとかの制約がないので、
BがAよりマイナス地点にいる可能性もゼロじゃないんですよね。
ってなったら、
APBPのプラスの判定だけだ。多分。
どっかでミスると思うんだけどな。
入力例3がNo。
ターン出してみますか?
一応入力例自体はクリアしてるんですよね。
多分どっかでWAはになると思うんですが。
なったね。
いっちゃん最後でなったね。
不正解が3つ。
なのでこれが多分マイナスに行ってるやつなんですよね。
えーっと。どうしたらいいの?
if v小なりwがexit、これはOKのはず。
ん?本当に?
いやまあそうか。
BPAMBM。
そうか。
if AがBより小さかったら、
if APDINAL="BP",だったらprintesでいいんだ。
だから、このelse文。
else print no。
もしAがBより大きかったら、
if AMがBMより小さかったらprintes。
そうでなければ、
else print noか?
一回ちょっと出してみようかな。
あ、いた。ACでした。
だから大元の座標の位置を判定するのを忘れてただけですね。
ではC問題いきましょう。
C問題 ランプス
C問題。
ランプス。
配点500点。
どうした?
問題文。
数直線上に電球がn個並んでおり、電球には左から順に1からnまでの番号がついています。
電球Iは座標Iにあります。
電球には光の強さを表す非不正数値が定まっており、
座標Xに光の強さDの電球があるとき、その電球は座標X-D-0.5から座標X-D-0.5までの区間を照らします。
はじめは電球Iの光の強さはAIです。
そこで以下の操作を軽快繰り返し行います。
1以上n以下の各整数Iに対し、操作時に座標Iを照らしている電球の個数をBIとする。
各電球そして各電球Iの光の強さをBIに変更する。
軽快な操作を行った後の各電球の光の強さを求めてください。
入力例51-10010、出力例は12212。
はじめに座標Iを照らしている電球は電球Iのみであるので、操作後の電球Iの強さは1になります。
操作後の電球の強さ。
操作時に座標Iを照らしている電球の個数をBIとする。
各電球Iの光の強さをBIに変更する。
またはじめに座標IIを照らしている電球は電球IとIIであるので、操作後の電球IIの強さは2になります。
何を言っているんだ。
座標Iを照らしている電球は電球Iのみであるので、操作後の電球Iの強さは1になります。
またはじめに座標IIを照らしている電球は電球IとIIであるので、操作後の電球IIの強さは1になります。
何を言っているんだ。
新問題を解説します。
回転500点ってことは結構難しい目なのかな。
でも3、4年前のやつだしな。
まず1回の操作をシミュレーションするのにかかる計算量を見積もります。
シミュレーションの内容を整理すると、各電球IについてI-AIからI-AIまでの区間に1を足し、最終的に各座標に書かれている値を計算するというものです。
これは累積はというテクニックによりオーダーNの計算量で行うことができます。
例えばC++での実装は次のようになります。
ということでC++の回答例がありますが。
ここはちょっと流し見しつつ。
解説長。
よって問題文の通りにシミュレーションすると、計算量はオーダーN×K、NKとなります。
しかし最悪ケースではNKは4×10の十乗なので、これでは間に合いません。
そこで次のような事実に気づく必要があります。
オーダーログN回操作を繰り返すと数列は収束し、全てNになる。
小説みたい。
これらは大雑把には次のような理由で成立します。
まず操作を1回行うとどの項も1以上になります。
さらに操作を1回行うと端は2以上、その他の項は3以上になります。
さらにもう1回行うと、というのを繰り返すとログN回ぐらいまでは操作するごとに各項の加減が約2倍になることが分かり、
最終的に電球の強さがNになって収束する項が現れます。
その後は強さがNになって収束する項が増えていき、さらにログN回ぐらいの操作を行うと全体がNになります。
ここで使った性質はA-I小なりイコールAIが成り立つならばB-I小なりイコールBIであるという性質であり、
各電球の強さが0の状態からオーダーログN回の操作を繰り返すと全てNになるという観察により、
常にオーダーログN回の操作で全てNになるということが分かります。
実際にはN小なりイコール2×10の5乗の制約のもとでは、41回操作を行えば十分です。
よってシミュレーションを行う回数はオーダーログN回で十分なので、オーダーログNの計算量でこの問題を解くことができます。
なるほど。ではちょっと収録外で勉強しておきます。また次回お会いしましょう。お疲れ様でした。