ABC160
ABC160に参加しました。
不要不急でない要件で外出しており、最初の30分はスマホコーディングでした。
ABCの三完でした。かれこれひと月くらいはコンテストのたびに悔しがっている気がします。
AtCoder Beginner Contest 160 - AtCoder
IDはsaikatotoです。
A-Coffee
string型で受け取り、s.at(2) == s.at(3) && s.at(4) == s.at(5)であればYes、そうでなければNoを出力します。
B-Golden Coins
500円を500円硬貨一枚で払うときの嬉しさは、5円硬貨100枚で払うときの嬉しさよりも大きいので、限界まで500円硬貨で払い、払えない分を限界まで5円硬貨を使って払うことで嬉しさを最大化できます。
具体的には、Xを500で割った商の1000倍と、その余りを5で割った商の5倍を足して出力します。
C-Traveling Salesman around Lake
スタートする家を固定して考えると、ある家からスタートしてすべての家を訪ねるための最短距離は、一度進みだしたら、同じ方向に湖に沿って進んでいき、家が出てくるたびに寄り、スタートした家の隣の家を最後に訪れる、というのが最短です。言い換えると、スタート位置を決めると、そのあとは最初に時計回りに回るか、反時計回りに回るかを選んで進み続けるしかありません。途中で戻ってくる場合、どんどん移動距離が長くなります。湖の全周が分かっているので、ある家からスタートした場合の最短距離は、全周からある家の隣の家までの距離を引いたものと等しくなります。つまり、湖の周りの家から隣り合う二つの家を選んで、その距離が最も大きくなるとき、その二つの家をスタートとゴールにしたルートが最短移動距離になります。
D-Line++
中途半端にBFSを勉強していた結果、いろいろとこねくり回して時間を無駄にした挙句解くことができませんでした。一日たって冷静に考えると、i<jとなるようにi,jの組み合わせを全列挙して、X,YはX + 1<Yなのでi,j間の最短距離をmin(j - i, abs(X - i) + 1 + abs(Y - j))とすればO(1)で求められるので、全列挙にかかるO(N^2)で解けることに気が付きました。
i,jの最短距離は、X,Y間の辺を利用するかしないかで分けて考えることができるので、利用しない時をj - iとし、利用する時をabs(X - i) + 1 + abs(Y - j)として、より小さいほうが最短距離になります。利用する時の最短距離は、Xとiの距離、XとYの距離、Yとjの距離をそれぞれ足し合わせることで求められます。AtCoderの解説PDFではこれに加えてYとiの距離、XとYの距離、Xとjの距離を足し合わせたものも考えるというように書いていましたが、X,Yの制約とi,jの設定の仕方を考えると必要ないと思います。XとYの距離は当然1なので、この点には注意する必要があります。
問題文を読んで、グラフの最短距離なら勉強したぞ、BFS使えばいいな、と安直に考えたのは大失敗でした。落ち着いて考えれば解けたと思いますし、そうでなくても早めに見切りをつけてEに行っていればEは解くことができたと思うので非常に悔しいです。
E-Red and Green Apples
赤色、緑色、無色のリンゴをそれぞれ降順にソートします。赤色のリンゴのうち、大きいほうからX+1番目以降は確実に必要ありません。緑色のリンゴも同様にY+1番目以降は必要ありません。コンテスト中にまず考えたのは、色のついているリンゴのうち、小さいものから無色のリンゴの大きいものと取り換えていく方法です。具体的には、赤色のX番目、緑色のY番目のうち小さいものと、無色の大きいほうから1番目を比べて、無色のほうが大きければ赤色か緑色の該当するリンゴと無色のリンゴを入れ替え、小さければ交換を終えます。入れ替えた場合には、比較対象のリンゴを、入れ替えた色付きのリンゴは一つ大きいものにし、無色のリンゴは一つ小さいものにします。赤色か緑色の入れ替えていないリンゴはそのままにします。
この方針でコードを書いている途中で、X個の赤色のリンゴとY個の緑色のリンゴとC個の無色のリンゴから、大きいものから順にX+Y個取っていく、という方針でもっと綺麗にコードを書けることに気が付きました。ただ、時間もあまりなく、また考察は正しいと思ったので、方針を変えずに書き上げて終了5分前に提出しました。残念ながら、このコードは3つREを吐きました。赤色か緑色のリンゴのどちらかをすべて無色のものに交換しきった後も比較しようとしているからです。REの原因に気が付いた時には残り45秒ほどで、修正は間に合いませんでした。5分で方針を変えて書き直す自信もなかったので仕方ないかなと思います。
1日たってから解きなおしました。大きいものから順にX+Y個取っていくという方針のコードはあっさり書けました。今回の方針に合致したデータ構造として、priority_queueがすぐに出てきたのは成長したのだろうと自分に言い聞かせることにしました。コンテスト中にREしたコードを書きなおすのは憂鬱で気が進みませんでしたが、一番勉強になると考えて書き直しました。あっさり直せたというのが余計に悔しかった…。
補足説明ですが、大きいほうからX+Y個取るという考え方については、赤色はX個まで、緑色はY個までしか食べられない、というように考えるほうが分かりやすいかと思います。赤色の大きいほうからX個、緑色の大きいほうからY個、無色をC個のうち、大きいほうからX+Y個食べたとき、どのように食べても赤色がX個以上、あるいは緑色がY個以上になることはありません。
F-Distributing Integers
解説を見てもまだ早いように感じました。
今回は以上です。そろそろいい出来だったと言ってコンテストを終えたいものです。
