2022-02-14 『スーパーマリオ オデッセイ』をクリアした
昨日 (2022-02-13) のことだけど『スーパーマリオ オデッセイ』をクリアした。次の要素を収集して絵のクッパを倒してキノコ王国で花火を打ち上げた。
- パワームーンのコンプリート 880 個 (たぶん) & カンスト 999 個
- キャプチャーリストのコンプリート
- ミュージックリストのコンプリート
- 衣装のコンプリート
アクションゲームとしての全体的な難易度は低め。ここまでのプレイ時間は 60 時間。単純なクリアの時間は分からないけど 10 時間くらいになりそう。月の国のクリアまでで収集しておそらく 20 〜 30 時間くらい。そこからの収集で 50 時間くらい。衣装の収集で 60 時間くらい。
探索がとにかく楽しい。怪しいところにはだいたい何か配置されている。たとえば、見えるところ (低難易度) にひとつパワームーンがあれば、見つかりにくいところ (高難易度) にもうひとつある。目の前に入りたくなる建物と扉があれば、扉へ入る前に建物を一周すると建物の裏に何かある。寄り道が楽しい。
パワームーンの数と密度。パワームーン 880 個は多く聞こえるけど、プレイしてみると配置されている密度が高いので、数字ほどは多く感じない。……というよりはよくこのマップにそれだけの要素を詰め込んだものだと感心する。
気持ちよいアクション。『スーパーマリオ 3D コレクション』で『スーパーマリオ 64 』 (2020-11-14) ・『スーパーマリオ サンシャイン』 (2021-01-17) ・『スーパーマリオ ギャラクシー』 (2021-05-05) とプレイしてきた。『スーパーマリオ オデッセイ』はその中でも特に動きが気持ち良かった。ギャラクシーも良いのだけどオデッセイのキャプチャーによる多彩さは良い。ただ書いておきたいのはキャプチャーしていないときの動きもかなり良いという点。ジャンプ中の帽子投げはジャンプの安定化にかなり寄与している。ボディアタックは早く動けるほかわずかに上昇する点も良い。転がる動きは移動速度が早いしそこからの幅跳びなども気持ち良い。適当に操作してもかっこよく動く。序盤は徹底してアクションガイドへ誘導されるようにもなっている。
難しかったところ。アクションで言うと月の国裏・月の国もっと裏・チャレンジ！くずれ道・チャレンジ！消える道路・ペラペラの秘宝・ノコノコレースの森の国や失われた国あたり・ミニカー。 2P なしのビーチバレーが最難関かもしれない。探索で言うと絵画の一部やローカルコインが数枚見つからない状況とかかな。
良く出来たゲームだった。
アルゴリズムと数学 演習問題集 038 - How Many Guests? を解いた。
問題: https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_ai
N, Q <= 10^5 という制約から Q 回の質問ごとに L 日目〜 R 日目の来場者数の和を取ると O(NQ) が 10^10 近くなってしまうので間に合わない。そこで事前処理 O(N) で累積和 S を作成しておき質問ごとには O(1) で S_{R} - S_{L - 1} とすることで区間和を得る。 O(N + Q) となるので間に合う。
提出: https://atcoder.jp/contests/math-and-algorithm/submissions/29325041
アルゴリズムと数学 演習問題集 039 - Snowy Days を解いた。
問題: https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_aj
N, Q <= 10^5 という制約から Q 日間の日ごとに区画 [L_i, R_i] を走査して X_i を加算すると O(NQ) で 10^10 近くなってしまうので間に合わない。そこで日ごとの走査では L_i および R_i に差分 (増加・減少) のみを記録しておき、最後に区画ごとの走査をして差分情報から累積和を作成することで区画ごとの積雪量を算出する。いわゆる「いもす法」 https://imoz.jp/algorithms/imos_method.html 。これで O(Q + N) で間に合う。
提出: https://atcoder.jp/contests/math-and-algorithm/submissions/29325127
アルゴリズムと数学 演習問題集 040 - Travel を解いた。
問題: https://atcoder.jp/contests/math-and-algorithm/tasks/math_and_algorithm_ak
一瞬グラフの問題かと思ったけど左右の駅以外とは繋がっていないのでその観点は要らない。
M - 1 回の移動で端から端まで N 駅分の移動を繰り返されたとき単純なシミュレーションだと O(NM) になる。 N, M <= 2 * 10^5 なので O(NM) では間に合わない。
j 回目の移動 (1 <= j <= M - 1) において欲しいのは B_{j + 1} と B_{j} の間の距離だ。これは累積和と区間和を使えば O(1) で得られる。事前処理で A_1 からの距離の累積和 C を O(N) で求めておく。これでおおむね C_{B_{j + 1}} - C_{B_{j}} によって求められる。注意が必要なのは B_{j + 1} と B_{j} の大小関係は逆転する可能性があるので必要なら入れ替えておくこと。
提出: https://atcoder.jp/contests/math-and-algorithm/submissions/29325351
今日のコミット。