Rabbit Holeをやった。Yomiのパターンが少しずつ分かってきた。
1回戦の方だが、こちらはもうほぼ完全に覚えた。
- 衝撃波(ジャンプ)
- 剣投げ+剣爆発(しゃがみ)
- ナイフ(ジャンプ、真上でないと剣の残弾に当たる)
- 自機狙い鎖(歩き)
- 突撃×2(緊急回避)
- ナイフ(ジャンプ)
- 飛び上がり+鎖(歩き)
一番難しいのは飛び上がり後の画面全体鎖攻撃で、隙間を探して身を入れるだけなのだが、その隙間が狭い。このゲームは自機が割と大きくて歩きに慣性もあるからSTGとは訳が違う。緊急回避も考えてみるべきか？
2回戦の方はそもそもまだ場数を踏めてないゆえに明かし切れていない。が、ちょっとずつ分かってきた。
- 1回戦と共通
- 衝撃波
- 剣投げ+剣爆発
- ナイフ
- 突撃
- 自機狙い鎖
- 1回戦に無いもの
- バウンドする光球
- 全画面投げナイフ(緊急回避)
- 8方向弾
1回戦と共通のものは同じ避け方が効く。バウンドする光球は遅いから見て避けれるとして、全画面投げナイフと8方向弾は前フリが読めていない。全画面投げナイフ時は時間が遅くなる演出が入るから見てから緊急回避が妥当か？
今日摂取したコンテンツ。
https://yamaiga.com/road/nokogiri/main.html
鋸山の古い石切り場の廃道。鋸山は旅行で行ったことある場所なので楽しく読んだ。しかし石切り場跡が観光客の気楽に見れない場所にも多数あったとは。
かなり久しぶりにABCに参加した。実力が落ちているというよりは環境についていけてないという感触を感じた。もうレート下がるのをちゃんと覚悟して毎週ちゃんと参加するべきだろう。AI禁止も明言されるようになったのでやめてた時期程荒れてないはずだ。
A: 6通り全探索
B: やるだけ
C: やるだけ
D: nC2通り全探索だが、各組み合わせをKi×Kj全て探索しているとTLEする。個数カウントしてかけ算にすればよく、1通りあたりO(Ki×log(Kj))で出せる。Kiがクソデカ(10^5)だったとして、1つのサイコロに注目するのは高々N回なので、100×10^5=10^7で済む。真面目に式にするとO(N(ΣKi)(ΣlogKi))くらいになると思う。
E: 無駄に難しく考えて時間を溶かした。まず方針として、全て連結になっていなければどこかの連結成分に余分なケーブルが存在するはずなので、余分なケーブルを探してその片方をその連結成分と非連結な別の連結成分に繋げればよい。これを繰り返せばかならず1ステップで連結成分数が1ずつ減るので、連結成分の数-1が操作回数になる。
余分なケーブルの求め方だが、シンプルに順番に連結していって既に両側が連結ならそれは余分なケーブルであるという単純なアルゴリズムで求められる。最初二度手間のややこしいアルゴリズムで求めていたがそんなのはいらなかった。余分なケーブルでどこを繋げるかが少し難しいところだが、連結成分の一覧を持ってしまえばよい。自分でない別の連結成分でさえあればどれでもよいので、連結成分の一覧を管理してさえいれば簡単に求められる。
F: 平方分割でごり押した。想定解は逆順に考える方法らしい。頭いい！
G: コンテスト終了後にちょっと考えてみたがよく分からなかった。C-B=B-Aを2B=A+Cと変形すると畳み込みが見えるらしい。これは見えなかった。
Categories: 未分類