AtCoder Beginner Contest 285に参加しました。
※いつもと違って日曜日に開催なので翌日の仕事に影響しないようにいつも以上に簡潔に考察の整理
結果
A,B,C,Dの4問正解でした。D問題がいつもより早く解けた気がする。
A - Edge Checker 2
配列で2分木を作るときに親子関係がどうなっているかを知っていればすぐに解ける問題。
子の番号は親の番号2と親の番号2+1になるのでa,bの関係がこれに当てはまるかどうかを判定する。
B - Longest Uncommon Prefix
問題文を読んでもいまいち何をすればいいかわからなかった問題。
入力例とその解説を読んで何をするのか読み取った。その後、読み取った内容から実装して入力例だと答えが一致することを確認してから提出。
i = 1,2,・・・N-1それぞれの場合で、 文字列中の文字をi文字飛ばしで比較していき、何文字目までは一致しないかを求めて出力する。
C - abc285_brutmhyhiizp
26進数変換をする。 A~Zで構成された26進数表記の値が与えられるので10進数に変換して出力する。
D - Change Usernames
文字列を頂点とみなしてS[i]からT[i]へ有向辺を伸ばしてく。 最終的に出来上がるグラフにループがあるかどうかを判定し、ループがなければYes、ループがあればNoを出力する。
E - Work or Rest
もう少しで解けそうな気がして時間内には解けなかった問題。
とりあえず考察としては、
適用される生産性はmin(最後に休んでからの日数,次の休みまでの日数)
→N日間のうち休日が1日だけだったとしてもAの後ろ半分は利用されることがない。 min(最後に休んでからの日数,次の休みまでの日数)は、休日、1日、2日、・・・、N/2-1日、N/2日、N/2日、N/2-1日、・・・2日、1日、休日（翌週）といった具合で変化していく。
週の半分をすぎると、最後に休んでからの日数より次の休みまでの日数の方が小さくなるのでAの後ろ半分は参照されることはない。連続n日働いた場合の生産性の合計は
になる。
総和が欲しいので累積和を予め計算しておけばこの部分はO(1)で算出できる。
このあたりで時間がなくなった来たのでとりあえず、i日連続で勤務した時の生産性を計算して、 サイズNの箱をサイズiのアイテムで埋めていったときの生産性の最大値はいくつになるのかという問題に置き換えて解こうとした。
改めて文章にしてみるともろにナップサック問題だけど、コンテスト中はナップサック問題だとは気づけなかったので貪欲法で解こうとして、でも入力例には合わないなあ、どこか考慮漏れがあるのかなあとデバックをしていた。
