東京海上日動 プログラミングコンテスト2020 (A,B問題)解説
こんばんはー。最近レート降下中のRuteです。
今回は、AtCoder Beginner Contest ... ではなく
東京海上日動 プログラミングコンテスト 2020 の 解説をまとめます。
(といってもA,B問題だけですが)
まず、私に足りないことが今回のコンテストでわかりました。
読解力不足です。(どういうことか知りたい方はこの後のB問題をご覧ください)
1. A問題「A - Nickname」
問題URL https://atcoder.jp/contests/tokiomarine2020/tasks/tokiomarine2020_a
問題概要:
長さが以上
以下の文字列
が与えられます。
から適当に連続する
文字を出力しなさい。
解法:
適当に連続する文字ですから"先頭から3文字"を考えます。Pythonでは
における先頭i文字をS[:i]で取得することが可能です。今回の場合はS[:3]で取得できるので、あとはこれを実装するだけです。
コーディング:
回答コード:https://atcoder.jp/contests/tokiomarine2020/submissions/14218268
2. B問題「Tag」
問題URL https://atcoder.jp/contests/tokiomarine2020/tasks/tokiomarine2020_b
問題概要:
数直線上に、に存在する点P,
に存在する点Qが存在する。
点Pは毎秒の距離を移動することが可能。
点Qは毎秒の距離を移動することが可能。
点Pと点Qで鬼ごっこをするとき、秒間に点Pが点Qに追いつくかを判定せよ。ただし、点Pと点Qは最適な移動を常に行う。
解法: 読解力不足が及ぼした結果...
最初、提出したコードはこちらです。
残念ながらこれではWAになりました。なぜWAの判定となるか わかりますか？この後説明します！
初めに、問題を整理すると(ここでは鬼役を点P,逃げ役を点Qとしています)
点Pの0秒での座標は,移動速度は
点Qの0秒での座標は,移動速度は
です。
解法(アルゴリズム的なもの)
のとき、明らかに点Pは点Qに追いつけないので"NO"を出力します。
(V = Wかつ A = Bのときはすでに追いついていますが、制約上このようなケースは考えられないです)
そうでない場合は、
距離 = と
の絶対値、 速度 =
と
の絶対値
として以降話を進めていきます。
誤った解釈だとこうなる。
距離を速度で割ったあまりが0でない場合、「相手と同じ座標にいる」というのが不可能なので"NO"と出力する。
あまりが0の場合は、距離を速度で割った商が
・以内なら"YES",
・より大きいなら"NO"
と出力する。
...という解釈で最初は進めていました。しかし、なぜかWAを連発します。ここで、問題文がよく分からなくなるといういつもの現象に.... (Writerさんごめんなさい
冷静に考えると、1秒単位で同じ座標にいるとき以外も考えられそうです。(例えば、「1.5秒で同じ座標にいる」という場合を考えることができます)
ちょっと不安だったのでclarを投げました。
すると、答えが「Yes」として返って来ました。こうなると解釈が変わってきます！
正しい解釈
での条件分岐はそのままで
距離・速度について
0 < 距離/速度 ≦ならば"YES",
そうでなければ"NO"
を出力する。
これでようやくACを出すことが出来ました！
コーディング:
回答コード:https://atcoder.jp/contests/tokiomarine2020/submissions/14237193
ちなみに読解力不足が招いた代償として4回のWA...(うち1回はコピーミスによるRE)
まぁ読解力不足ということで、次回以降は気をつけます。
以上、東京海上日動 プログラミングコンテスト2020のA問題、B問題の解説でした！
明日のABCではRatingを上げられるようにしたいです！
