AtCoder ABC146 参加記
AtCoderのABC146に参加したので自分の解いた問題と解き方を載せておこうと思います。
A問題
今日の曜日を表す文字列 S が与えられます。 S は SUN, MON, TUE, WED, THU, FRI, SAT のいずれかであり、それぞれ日曜日、月曜日、火曜日、水曜日、木曜日、金曜日、土曜日を表します。 次の日曜日 (あす以降) が何日後か求めてください。
--解答--
SUN, MON, TUE, WED, THU, FRI, SAT を順に配列に格納して, 前から探索, S と一致したら 7 - index を出力
提出したコード
B問題
英大文字のみからなる文字列 S があります。また、整数 N が与えられます。 S の各文字を、アルファベット順で N 個後の文字に置き換えた文字列を出力してください。 ただしアルファベット順で Z の 1 個後の文字は A とみなします。
--解答--
S を前から順に見ていく. 各文字から 'a' を引いたものに n 足したものを 26 で割ってそれに 'a' を足したものを出力
提出したコード
C問題
高橋くんは整数を 1 つ買いに整数屋さんに行きました。 整数屋さんには 1 以上 109 以下の整数が売られていて、整数 N を買うためには A × N + B × d(N) 円が必要です。 ここで、d(N) は N の十進表記での桁数です。 高橋くんの所持金が X 円のとき、高橋くんの買うことのできる最も大きい整数を求めてください。ただし、買うことのできる整数が 1 つもない場合は 0を出力してください。
--解答--
二分探索するだけ. ただめっちゃバグらせて実装に時間がかかってしまったのは非常に反省.
提出したコード
D問題
N 頂点の木 G が与えられます。 頂点には 1 から N までの番号がついており、i 本目の辺は頂点 ai と頂点 bi を結んでいます。 G の辺を何色かで塗り分けることを考えます。 このとき、各頂点について、その頂点を端点に持つ辺の色がすべて相異なるようにしたいです。 上記の条件を満たす塗り分けの中で、使用する色の数が最小であるようなものを 1 つ構築してください。
--解答--
"親の親のノードの色を持ってdfs, map等で使った色管理して使ってない色から順に割り当て"って思ってたけれどそもそもノードに色を割り当てるっていうのが間違いだった
サンプルは通っていい感じだったけどWA
解説放送見て解き直し
一つ前の頂点から見ていくっていう考え方はあっていたっぽいけど辺の管理ができていなかった.
辺の番号を保持しておいて, DFS なり BFS なりを使って木の根から順番に塗っていけば OK
解き直して提出したコード
