コンテストページ：https://atcoder.jp/contests/kupc2019/tasks
解法と反省
A - November Festival(3:29)
まずは重複度のリストをつくります。 その上を、現在の最大とその添字を保持しながら、左から順に走査していくと良いです。
B - ナップサック問題(17:16)
制約をグラフにして連結成分ごとにまとめると、普通のナップザック問題になります。BFS をするとよいです。
反省
BFS と Union-Find で迷ってしまい、若干行ったり来たりをしてしまいました。このあたりは今進めている低難易度埋めで改善する予定です。
C - てんびんばかり(29:33+(2))
K 個ずつ使うのであれば、2K + 1 の冪の分銅を用意すればよいです。 すると、測れる最大は等比級数の和です。
反省
計算間違いで 2WA なのですが、少し焦りすぎです。簡単そうに見える問題こそゆっくりと解くのが最近のトレンドです。
D - Maximin Game(86:00+(2))
ランレングス圧縮です。制約を半順序とみると、RLE の各成分を縦に繋げたもの（縦につなげることを、なんと呼ぶのでしたでしょうか。お名前が出てきません。）になりますから、掛け算です。
それぞれの成分を見ましょう。 小さい順に配っていって、最大の小さい方がいくつなのかを保持する DP です。 これはよく見るとパスカルの三角形の半分ですから、カタラン数です。 階乗を前計算することで、Θ( 1 ) で処理することが出来ます。
反省
これは、普通に考察に時間がかかりすぎました。 ランレングス圧縮の成分ごとに独立に見て良いことに気づかず、もとの列のままで上記の DP を試みていました。 それでもできはすると思うのですが、かなり苦しい戦いになりそうです。
どうすれば回避できたかというと、難しいですが、小さい例を作るのを怠ったのがありそうです。 サンプル 1 は小さすぎて、サンプル 2 は大きい上に初め 0 ばかりですから、自分で何かしらを作ってみるべきだったかもしれません。
E - 根付き森二人用ゲーム(237:34)
返り点のコーナーです。
F, G を先に解いてから、E を解きました。
解法
各木に対して、スタート地点からその木に行って、また戻ってくるまでの手数を数えます。 そして、次のような勝負を考えます。（先手とは、駒を根に移動させる人のことです。）
- 先手は偶数手で終わらせたいです。この勝負、勝てますか？
- 先手は奇数手で終わらせたいです。この勝負、勝てますか？
両方とも先手が勝つような木があれば、それに移動すれば勝ちです。 両方とも後手が勝つような木は、それを選んだ瞬間に負けが確定しますから、ないのと同じことです。
したがって、これらはすべてないものとみなします。 すると、いずれの木に対しても、先手でも後手でも勝てる勝負がありますから、その勝負をするとしましょう。それで偶奇が合うようなセットならば勝ちです。逆にそうでなければ相手がそのパターンですから、それは負けです。
反省
発想は難しくないのですが、かなり頭の混乱しやすい問題です。 ただ戦略で負けた感じはなく、たんに慣れといいますか、練度が足りませんでした。 このような困らせ方をする問題はたくさんあります。練習すれば確実に強く慣れると思います。
F - カズマ王国の陥落(186:28)
返り点のコーナーです。
G を先に解いてから、F を解きました。
解法
攻撃する町を予め選んでおきましょう。 各魔物がそれらのうち攻撃できる最も左を攻撃し、できないものはサボるとして良いです。 なぜなら最適解に於いては陥落できる町だけが本質ですから、 攻撃する町としては、それを選んでおけば最適解が構成できます。
攻撃する町を左から順に決めていく DP です。 最後に攻撃した町が i - 1 であるときの最大の成果を dp[i] と書きます。 ただし一度も攻撃していない場合は dp[0] に置いておきます。 これはかならず 0 です。
遷移
さて、dp[i] を計算しましょう。 各 j 対して dp[j] からの遷移です。 これは、前回攻撃した町が j - 1 な場合です。 このときは、j <= l < i かつ i <= r なる区間 [l,r[ （ただしこれは l を 1 減らしてあります。）に配置された魔物がお手隙きです。 ここにいるみなさんで総攻撃です。
高速化
この遷移を Θ( log N ) で行いましょう。 cmx (change max) による遷移ですから、Max による Aggregation ができると嬉しいですね。 セグツリーです！
前処理です。各区間 [l,r[ に対して、seg[l] += w をしておきます。 これで左端がある範囲であるものの合計が取れます。 ただ、条件は右端にもついていました。見ている場所よりも小さな右端を持つ区間はオワコンですから、削除をしたいです。そこで、vecvec v を作っておいて、v[r].push_back*1 です。
実際に遷移をしていきましょう。 dp[i] をみるときには、終点が i 以上のものしか残っていない状態を保ちましょう。 すると、cmx( dp[i] , seg.sum(j,i) ) で遷移できます。 終点が i のものは未来の子どもたちの役には立ちません。 v[i] の元 (l,w) を見て、seg[l] -= w です。
反省
そもそも解法を思いつくのに時間が掛かりました。
- 同じ区間の魔物の戦力を散らせて得をすることはありません
- 集中させる町を決め打ちしたとしても、どの区間の魔物がどの町を攻撃するのかは一意に定まりませんが、よく考えると一番左として大丈夫
- 以上のような性質は、「制限した探索空間に最適解が少なくとも 1 つ含まれるか」という観点で考えると考察しやすい
このあたりが反省点でしょうか。
G - ABCのG問題(131:02+(1))
H, W が 3 で割って 1 余る場合は、(i+j)%3 で A, B, C を決めて丁度数が合います。 特に、H = 4, W = 4 のときもこれでよいです。
それ以上な時は、i = 3 の行と j = 3 の列を無限に繰り返せばよいです。
反省
思いつけばすぐ系の問題です。 そこそこ時間も掛かりましたが、そこまで嵌ったわけではありませんから、むしろ良い方だったかもしれません。
ごちゃごちゃしがちな構築問題ですが、珍しくすっきりめな答えで嬉しいです。
未着手
H, I, J, K, L
多くありませんか！？
成績
22 位相当です。 黄色下位としては悪くない成績でしょうか。
勝負どころの E, F, G を 3 問とも通せましたが、一問でも落とすと横ばいから微冷えだったと思うと、身が引き締まります。橙になったらこの 3 問は必須で、H 以降も 1 問は通したいといったところでしょうか。レドコーダーへの道は長いです。
*1:l,w
