トップ > プロコン > ABC146

ABC146

プロコン

今回は、Eまではいつもより難しく、Fはいつもより簡単だった。E以外の5完。昨日と違って緊張感はなく、それでいて集中して楽しむことができた。それなのに、今は結果が出ないことに落ち込んでいる。報酬がずーっと得られてなくて脳がもうやだって言ってる。

A - Can't Wait for Holiday

まず「SUN,MON,TUE,WED,THU,FRI,SAT」を問題文からコピペしてくる。テキストエディタで「,」を「","」に置換とかするべきだったがそれは手動でやった（人間のする仕事じゃない）。char*の配列に（各文字列の先頭のポインタを）入れて、入力と（std::stringとして）比較。次の日曜が遠い順に並んでることに気づくと場合分けが要らないとわかる。いやあ、けっこう重かった。

B - ROT N

文字列を受け取って加工して出力する。Nが26以下なので、単に足して'Z'より大きかったら26を引けばよい。絶対Aより簡単じゃんと思った。

C - Buy an Integer

「d(N) は N の十進表記で」というのを見てそれはNと何が違うんだと思ったが、改行位置がたまたま読みにくいだけで桁数だった。まあ二分探索なら求まるなと。他の方法も少し考えるが、結局二分探索みたいになる。というわけで実装。サンプルが合わず、買えるのは最大で10^9なことに気づく（思い出す）。直して提出。いやA*Nでオーバーフローの可能性があるのコンテスト後にwriterのツイート見るまで気づかなかったなあ。ABCだと色々甘えてる。ABCでサンプルに甘えることが多い自覚はあったけど、問題自体にも甘えてる（今回も実際そうしてくれてた）。

D - Coloring Edges on Tree

辺を塗るのね。木なので、最小の色数は最大次数で行けるかなと考える。まず葉ノードから考えてみるが、そのうち普通に根からDFSでいいと気づく。まず根からは周囲を1から次数までの数で塗って、子はその数を避けて1から塗っていく。親からの辺の数以上の次数なら1から次数まで使えるし、次数が少ないなら最大値を更新することがないので大丈夫。これで解けたけど、ここから実装をどうするか考えるパートがあるのが楽しい。グラフの辺に何番目の辺かという情報を持たせ、答えを入れるvectorも用意しといて、辺を塗るときにその配列の辺の番号のところに入れる（あと最大値も更新する）。

E - Rem of Sum is Num

手の付けようがないように見えるが、「Zero-Sum Ranges」や「Candy Distribution」のような雰囲気を感じる。1が、それらの問題における0みたいな働きをするなと思う。そこからしばらく悩むと、Aから1を引いておけばいいと気づく。これで解けたと思い、細かいところをしっかり詰めて実装。が、途中まで書いたところで、要素の数がK以上の区間はカウントしない問題だと気づく。このコードではダメだ。しばらく考えてダメだったので21:50頃に順位表を見てFへ。

K以上の長さの区間は置いといて、そもそも今の解法ではサンプルも通らない。多くカウントしてるはずなのに小さく答えが出たりする。そのバグも全くとれないし、要素の数がK以上の区間（またはK未満の区間）の数を求める方法もわからない。累積和の値をmapに入れて足してKになるやつを引き合わせる。mapにまとめないと処理に時間がかかるし、まとめると位置情報が消える。不可能としか思えない。


というわけで意味がわからない勘違いをしていた。知ってる問題だと思ってそれに頼りすぎたな。いや頼れよって感じでもあるが。でも頼りすぎた。累積和の値をバラバラにしたときに感覚が働かなくなってる。で、Twitterでしゃくとりを見たので考えてみたが、確かに同じ数（累積和の値）をインデックス付きで抜き出してしゃくとりすれば合計O(N)でできそうか（あまり深く考えてないけど）。

F - Sugoroku

考察と実装で8分ずつみたいな感じだった。ルーレットと言っているが好きに選べる問題設定だ。DPかという見た目。O(NM)は間に合わないけど、Mが（Nに対して）大きければ手数は短くなるし、手数がN回近くなるならMは小さいから、そのへんを突く問題なのかな。まず、最短手数を達成するだけなら最も遠くの0へ行けばいい（途中下車する意味はない）。その中で辞書順最小、つまり1回目を可能な限り短く跳んで、その中で2回目を短く跳んでという。ところで、操作は左右対称なので後ろからそうやって最小手数を求めれば、それを逆に辿ったのがそのまま答えでは？だって、たとえば5回でゴールするのが最小のとき、後ろから4回目に跳んだ先は「（前から見て）4回でゴールできる最も（ゴールから）遠い場所」になっている。で、前からの1回目のジャンプはそこに行けるのだからそれが最善だ。2回目からも同じ。ということで実装に入る。貪欲に遠くへジャンプするのは、愚直でよさそう。ジャンプする距離の合計はNにしかならないから。AC。Eへ戻る。

が、これTLEにならないことを証明してなかったことに気づいた。跳ぶたびにM個先から1個先まで0が見つかるまで検索してるので歩幅が短いときはO(NM)かかりかねない。当時何を考えていたか思い出せないが、何も考えていなかったんだろうなあ。改めて考えると自分の（考察は雑だったけど）コード（というより脳内生成した仕様書？）は正しそうだ。0を探して1ばっかりだったとしても、そこをもう一度検索することはない（このコードだと正確にはゴールできないケースで2回やることがある）。一番左の0へ跳ぶわけだから次はさらに左の0を見つけてしまう。0も1も1回しか見ないならO(N)だ。