Easy筋トレ1日目: SRM562, 561

前回の筋トレ以降、仕事の都合上全く練習できずにいたら、恐ろしくレーティングが下がり始めました。

過去５回、Easyを凡ミスや、単純に閃かなかったなどの理由でSystem Failし続けています。

というわけで、急遽筋トレ再開します。

SRM562 Easy "PastingPaintingDivOne"
■時間
４０分ほど？

■試した解き方
各斜め線の挙動を考える（斜め線間での干渉はないため、一本の斜め線（例： (0,3),(1,4),(2,5),...）毎にしか考える必要がない。
線の中で、一番左上の透明でないピクセルは必ずT回コピーされる。
それ以降のピクセルは一回しか現れない。
ただし、透明のピクセルの場合は自分よりも（最大距離T-1で）右下で透明ではない、最初のピクセルの色になる。
以上の条件で、足すだけ。
大体O(w*h)で解ける。

1st submit:
OK

■Editorialの解き方
シミュレーション的解き方。実際にコピーしてみて、前回と同じレイアウトになったらそれ以降は掛算で計算。あんまきれいじゃないよな？

■反省
やたら時間かかってしまった。
斜め線の中を、一番左上のピクセルと、それ以外の２ケースだけで考えればいいことに気づかず、もっと色々なケースがあると勘違いしてしまったため。

SRM561 Easy "ICPCBalloons"
■時間
４０分ほど？

■試した解き方
どの問題をどのサイズの風船にするかは、割当が2^15しかないので、全パターン試す。
割当が決まっている時に、実際に風船の色を割り当てる方法は、（証明してないが）なんとなくGreedyでいけそうな気がした。

1st submit:
OK

■Editorialの解き方
同じ。

■反省
これも時間かかってしまった。
実際のGreedyの割り当て方を考える所に悩んでしまった。