またいくつかファミコンソフトとスーファミソフトを買った。ドラクエ1,2,3が安く手に入ったのは嬉しい。
ABC307に出た。
A: やるだけ
B: やるだけ。
C: 位置関係を全部試すだけではあるが、探索範囲はしっかり考えなければならない。仮にシートXの位置を固定すると、シートAとシートBはXに少しでも引っかかっている範囲と考えれば、シートA,Bの左上位置のX,Yは-10～10くらいを試せばいいことが分かる。配置は20x20x20x20通り程度、一回の判定にはシートXの全てを見るので10×10程度、よって必要な計算回数は10^7程度になる。「シートA,Bの黒マスは全て使う」というルールを見落として時間を食ったのと、あと探索範囲を間違えて1WAした。細かい詰めが難しい問題。
D: スタックに入れてみるだけ。
E: シンプルなDP。良い感じにオーダーを落とせていったので気持ちよかった。まず、すべての数字は平等なので最初の数字は0として計算してよい。あとでパターン数にMを掛ければよい。
単純に「どこまで決めた」「最後の数字はいくつ」を持ってDPすると空間O(NM)の時間O(NM^2)になってしまう。そこで、累積和を使うと時間O(NM)に落とせる。次に、DPテーブルの「最後の数字≠0」は全て同じ値になることに着目する。これに気付くと「最後の数字=0」と「最後の数字≠0」の2つの値だけ管理すればよいことになり、O(N)に落とせる。
F: 単純にプリム法っぽい感じでやっていけないかと思ったが、一晩に2通路以上感染が進む場合があるので違うなとなった。それでダイクストラっぽい感じでやっていこうとしたが、日が変わるたびリセット的なことが必要と気付いて絶望した。一晩の間をシミュレートするには感染済みの部屋からの距離を見て行く必要があるが、次の日には「感染済みの部屋」の集合が変化している。
最終的にダイクストラっぽい感じのこと(感染済みの部屋からの距離を優先度付きキューに入れて見て行く)をしつつ、それとは別に新たに感染した部屋から隣接部屋への距離を記録していき、一晩分のシミュレーションが終わるたびに記録していた隣接部屋への距離を優先度付きキューに入れて次の晩のシミュレーションに備える、みたいな実装をした。
G: 解けず。
まず、最終的に全ての値はある値PもしくはP+1になる必要があることが分かる。次に、与えられた操作では総和が不変なので、$P=\lceil \sum A/N \rceil$であることが分かる。$M=(\sum A)%N$とすると、N個中M個がP+1で残りN-M個がPになる。考察できたのはここまでだった。
橋から順にPかP+1か近い方にやっていくとかを最初にやっていたが結局後ろにしわ寄せがくる。後ろからもう一回前に戻したりもしたがそれはおそらく非効率でWAが出た。上手い感じのPとP+1の割り当てを考えないといけないらしい。
今日摂取したコンテンツ。
見かけ上超光速に見える運動があるという話。なかなか面白かった。めっちゃ遠い壁にレーザーを当ててレーザーを振り回したら壁に映った軌跡が速く見えるよねというやつかと思ったが、それとは別のようだ。
速度-見かけの速度のグラフが面白かった。
Categories: 未分類