AtCoder Regular Contest 063
受験勉強の息抜き（やってる時点で浪人不可避な気がするけど気にしない）。久々だったのでコードがグダグダです。
一応1時間で3完できました。F問題は3分考えて何も浮かばないので離脱。残り時間でこちらを書いてました。
C - 一次元リバーシ / 1D Reversi
問題概要
1次元上でリバーシを行う。N個既に配置されており、両端にいくつか石を置いて１色に染めたい。最小何手で出来るか。
http://arc063.contest.atcoder.jp/tasks/arc063_a
解説
取り敢えず白石や黒石が2個以上連続していても同時にひっくり返されて意味がないので、WWWなど連続しているものはWと1文字にまとめます。
すると、文字列は必ずBとWが1文字ずつ連続したものになります。
この状態なら、左に1番左の石と違う色の石をひたすら置けばいいです。実際は「操作後の文字列の文字数-1」が答えになります。
https://arc063.contest.atcoder.jp/submissions/970440
D - 高橋君と見えざる手 / An Invisible Hand
問題概要
高橋くんが商売で上げる利益が1円でも少なくなるよう店の価格を操作して下さい。
アダム・スミスの思想とは裏腹に、みんなが利益を得ようと努力しても社会は良い方向へは進まなさそうな問題です…青木くん何がしたいんでしょうか…
http://arc063.contest.atcoder.jp/tasks/arc063_b
解説
まずは高橋くんが最も利益を上げる方法（操作前）を考えます。
ある安くリンゴを買える店で買えるだけリンゴを買って、それより後に訪れる一番高くリンゴを売れる店で全部売るのがいいでしょう。
具体的には、順番に店を訪れる中で「今まで見た店の中でのリンゴの最安値（sml）」「今まで見た店の中で最も利益の出る場合でのリンゴ1個あたりの利益（profit）」「今まで見た店の中で最も利益の出る場合の店の選び方（pattern）」を考えてそれぞれ更新すればOKです（括弧内は自身のコードで扱った変数）。
例えばリンゴの単価10→30で売るか、20→40で売るかの2通りが店を回る中で高橋くんは選べるので、両方を潰さなくてはならない点に注意が必要です。
更新を終えたら、最も利益の出る時に使う店の片方の価格を1円だけ変えてあげればいいので、pattern店舗の価格を変えればOKです。
https://arc063.contest.atcoder.jp/submissions/970893
E - 木と整数 / Integers on a Tree
問題概要
N頂点の木の頂点のうち、いくつかに整数が書いてあります。「辺で結ばれた2頂点の差の絶対値は1でなければならない」というルールで全頂点に数字を入れてください。
http://arc063.contest.atcoder.jp/tasks/arc063_c
解説
ルールについて考察します。
ある頂点に5が書いてあるとすると、それに隣り合った数字は4か6、更にそれに隣り合った数字は3、5、7、…となっていきます。このことから、
- 各頂点に入る可能性のある数字の集合は必ず全要素が奇数、もしくは偶数で統一されている
- 各頂点に入る可能性のある数字の集合は、2ずつずれていく数列
このことより、各頂点に入る可能性のある数字の集合の最大値、最小値のみを記録すれば、各頂点に入れることの出来る数字全てを列挙することができます。
この最大値と最小値を使ってDPっぽくDFSをして各頂点に入れることの出来る数字の集合を確定させていきます。
適当に木の根を決めてDFSしていきます。各頂点で、その頂点の子の取れる数字の幅を元に、その頂点に入れることの出来る数字の幅を狭めていきます。
その際に、子の2頂点が奇数しか取れない頂点と偶数しか取れない頂点だった場合、どうしようもないので、その問題の答えは"No"になることに注意が必要です。
各頂点の取れる数字の幅が確定したら、再びDFSを行い、今度は根から取れる数字の中から適当に数字を1つ選んで確定させます。そうすると、その頂点の子の取れる数字の幅が親の数字の確定により狭まるので、狭めたあとにその中からまた適当に選んで、…を繰り返します。
結局かなりif文の多いあまり良くないコードに仕上がってしまいました…他の人はどんな感じで華麗に解いてるんでしょうか…
https://arc063.contest.atcoder.jp/submissions/972322
感想
久々で44位なので、まあまあの出来ですかね。本格的に再始動するのは受験が終わってからです。
