ymduu+2

初心を忘れないのでツンデレとPSPが今でも好き、技術メモとか制作物とかそういうの

IQ1のスプラローラー

これは IQ1 Advent Calendar 2019 の 20 日目の記事です

adventar.org

はろはろー、ymduuさんです。 前回のIQ1 Advent Carendar から 約1年、今年も引き続きSplatoonをやっていたので懲りずに今年やったことを書いていきます。
今年は昨年のエリアXに続き、ヤグラとホコがXになりました。アサリは……ナオキです
去年はZAPを持っていたのですが、今年はスプラローラーに持ち替えてやっていました。ヤグラではhighest2400を達成したり f:id:ymduu:20191219181505j:plain 通話のためにミキサーを買ったり

自分の挙動を見直すためにキャプボを買ったり

日々精進しております。

というわけで今日はスプラローラーの典型テクを書いていきたいと思います。
立ち回りというよりは対面のテクという感じなので、立ち回りは適宜ほかの文献などで補完するとよいです。僕の立ち回り: ニンジャを着て殴る

ギア構成

f:id:ymduu:20191219181825p:plain ローラーの必須ギアであるところのイカニンジャ、前衛職の必須ギアであるところのステジャンを履いて、残りは忍者のデメリットをイカ速で打ち消しつつひたすらメイン性能を積む構成です。力こそパワー！
スペシャル減少量ダウンとスーパージャンプ時間短縮はサブギア一つでで効果が大きいのでつけています。厳選が面倒だったわけではないです。

曲射

ローラーは振った時の飛沫で攻撃するブキです。敵の上から飛沫をかぶせるように振ることで、段差の下から、上から、障害物の陰から一方的に相手を攻撃できるほか、斜め上方向に飛沫を飛ばすことで射程を伸ばすこともできます。(もちろん威力は減衰しますが)
ローラーの対面を支える最重要テクです。

段差下

ローラーと言えば段差下ですよね！(当社調べ)
一般的なシューターやスピナーなどは段差の下にいる敵に弾を当てるのが難しい一方で、ローラーは曲射をつかうことで段差上の敵を一方的に倒すことができます。
同様の理由で、ヤグラ上にも強いです。

段差上

段差下ローラーは広く知られていますが、飛沫は重力に従って上から下に落ちていくため、段差の上から下にも強いです。段差下に陣取っているローラーに対してカーリングボムを溜めて流すのも強いです。

障害物

一発で倒し損ねたシューターなどが物陰に隠れることがよくあります。その場合も上からローラーの飛沫をふりかけてやることで対応できます。

偏差撃ち

スプラローラーが一度振ってから再度振り下ろすまでの時間は横振りで42F、縦振りで56F *1と、とっても長い です。
ふつうに今敵がいる場所に振り下ろしたのでは過去を殴ってしまい、当たりません。それは残像だ
偏差撃ち というのは、対面している敵がどちらに動くかを予測してそちらを殴ることです。これができないと攻撃が一切当たらないのでやっぱり必須テクです。直感で当てろ
これにはいくつか典型パターンがあるのでイカで紹介していきます。麻雀のスジみたいなもんです。つまりよくはずれる

壁登り読み

壁を登っている人が「やっぱやーめた」と降り始めることはなかなかないです。つまり、壁を登っている人はそのまま登り切る、と予測できます。

読み、というか出待ちに近いですが、そもそもタチウオ左に入った人はたいてい壁を登るので注意しておきます

動画だとわかりづらいですが、画面の端に登るために壁を塗っている敵が見えています。壁を登り始めた敵は登り切るので、前述の曲射で仕留めます。

直進読み

イカ状態で直進している人は(こちらに気づいて慣性キャンセルで急停止する場合を除き)直進します。イカは急には止まれない

パブロ対面です、こっちに突っ込んでくるのが見えたので気持ち進行方向に横振りを置いておきます

これはちょっと極端ですが、壁の裏に入ったのを見て、出てきそうなタイミングで横振りを出しています

スライド読み

これは難しいですが、マニューバと対面するときは「こいつ転がるな～」と頭の片隅に置きながら戦います。
スライドした瞬間その方向にエイムを振ります。 振り下ろす瞬間にスライドされると死にます。Ω＼ζ°)ﾁｰﾝ

物陰に隠れた人は出てくる

相手が物陰に隠れた場合でも、こちらを仕留めるために再度顔を出すことがあります。
それを予想してそこに攻撃を置いておきます。特に先に一発貰ってしまった場合などはかなりの確率でトドメを刺しにくるので、上手くいけば返り討ちにできます。

デュアルスイーパーに先制されて一度物陰に隠れました。右側から再度飛び出してくることを予想してそこに攻撃を置いておきます。

逃げ先読み

一般に、イカちゃんは不利になった時にイカの場所に逃げていく傾向があります。
- 自陣
- 自分のインクで塗られている場所
- 襲っている人の反対側
これを踏まえると、不利になったイカちゃんが逃げていく先を予測できることがあります。

ZAP(？)に追い立てられているエクスが見えたので、ZAPの反対側上方から落下して挟み撃ちにすることができました。

削り

ローラーは射程が短いブキだと思いがちですが、実は2確でよければ短射程シューター(ZAP、🍣等)より少し短いくらいの射程があります。
これを利用して、普段より広めの間合いで戦うことができます。
主に味方のカバーや1回許してしまった場合などに用います。

これはジェッパを出していた人が通話で「あと一発～」と言ってくれたので追撃した図です。

接近

とはいえ、ローラーのメインの間合いは近距離です。間合いに入るための工夫をします。

カーリングボム

カーリングボムを投げると敵の注意がそちらに向きます。敵がそちらを見ている間に別の方向から強襲します。
(上手くいっている動画が撮れなかった)

視界の外から

カーリングボムを投げなくても、敵が見ていない方向から突っ込めばOKです。
敵が見ている方向は弾が出ている方向から推測することができます。

ボトルの弾が出ている方向の垂直方向から突っ込むことで気づかれずに接近できました。

逃げたふり

これは筆系のブキが良く使うテクですが、ローラーでもできます。
逃げたと見せかけておいて近くに潜伏し、いないと思って近づいてきた敵を返り討ちにします。

不利対面をチャクチで誤魔化して逃げた、と見せかけてその場で潜伏することで、近づいてきた敵を倒すことができました。

その他

対スーパーチャクチ

アップデートで狩りやすくなったスーパーチャクチですが、振っている間にエイムを合わせられるスプラローラーなら、振っている間に出たチャクチは見てから狩れます。本当はチャクチ溜まっているのを見て予測できた方がよい

一人目は前述の段差下で、三人目は前述の削りです。三人目は味方がカバーしてくれました。

コロコロ

前述のとおり、振りを外したあとにもう1回振るまでには42Fかかり、ZAP はそれまでにこちらを2回殺せるだけの弾を出します。悲しいですね。そのため、外した後にワンチャンを狙って轢きに行くことがあります。

一人目に縦振りを外したあと二人目に干されそうになって轢きに行っています

コロコロ2

前述のとおり、振りを外したあとにもう1回振るまでには（ｒｙ
なので、壁を塗るのも一苦労です。横振りで壁の上部を塗った後にコロコロに移行して、そのままエイムを上に振ることで素早く壁を塗るテクがあります。

この壁はそんなに高くないですが、壁を塗った時インクが垂れてくる性質を使うことでもっと高い壁を塗ることもできます。

おしまい

終わりです。スプラローラーはニンジャを着て殴るだけというIQ1なブキです。IQ1各位は持って敵を殴りましょう。おわり

*1:https://wikiwiki.jp/splatoon2mix/%E3%83%96%E3%82%AD/%E3%82%B9%E3%83%97%E3%83%A9%E3%83%AD%E3%83%BC%E3%83%A9%E3%83%BC

CODE FESTIVAL 2016 qual B D Greedy customers

所見

700初自力AC

atcoder.jp

問題概要

長さNの整数列Aについて以下の操作を繰り返し行う。

  • ある正整数Pを決め、Ai >= P なる最小のiについて、Ai -= P をする。

任意のiについてAiが0にならないように操作を行うとき、操作は最大何回できるか。

取った方針

前から順番にAiを1にしていくことを考える。
理由:

  • 数列の前の方に大きい数字があるとその数字が操作の対象になってしまうから。
  • i > j のとき、Ai にAj 以下のPを作用させることはできない。(Ajが対象になってしまうので)
  • 操作の回数を大きくしたいとき、Pは小さい方が有利であるから。
    • 小さいPを数列の後ろの方に作用させたい時、その前にある数はなるべく小さいと都合がよい。

0番目の数は、1をAi-1回引くことで1にできる。
次にPを1にすることはできないので、Pを2にすることを考える。
Pが2の時、以下をすると行える操作数が最大。

  • Aiが奇数のとき、Ai/2回2を引く。
  • Aiが偶数のとき、Ai/2 - 2回2を引き、1回3を引く(行われる操作はAi/2-1回)

ここで、Aiが2の時はP を2にすることはできず、Pを3にすることになる。

Pがnの時、以下をすると行える操作数が最大。

  • Aiがnで割り切れないとき、Ai/N - 1回nを引き、最後の1回はAi == 1 となるようにPを定める。(操作回数はAi/N回)
  • Aiがnで割り切れるとき、Ai/N - 2回nを引き、最後の1回はAi == 1となるようにPを定める。(操作回数はAi/N-1回)

よって、Ai==P なるAiが現れる度にPをインクリメントしながら上記の計算を行えばよい。それを行うコードは以下

int ans = A[0] - 1;
int P = 2;
for (int i = 1; i < N; i++) {
    if (P == A[i]) {
        P++;
        continue;
    }

    int sell = A[i] % P == 0 ? A[i] / P - 1 : A[i] / P;
    ans += sell;
}

正しい方針

同上

得られた知見

  • かしこい貪欲

解くのに必要な要素

  • 実験……
  • 手でシミュレーションするの大事(口だけ)

周辺調査によって得られた知見

特になし

ABC132 E Hopscotch Addict

https://atcoder.jp/contests/abc132/submissions/7044671

所感

拡張ダイクストラ、ノードを増やすんだけど、実際に実装するときは距離を格納する配列の次元を増やすみたいな実装になるんだなあ

問題概要

有向グラフの上で移動することを考える。頂点Sから頂点Tに移動するとき、移動距離が3の倍数となる経路は存在するか、するならばその経路の長さを3で割ったものを出力せよ。

取った方針

BFSで頑張ろうとするも死亡

正しい方針(解説の方針)

一般に拡張ダイクストラとか呼ばれている方法をする。(今回は辺のコストが1なのでBFSでよい)
それぞれのノードについて、そこに至る経路長 mod 3 が0, 1, 2 の場合について場合分けする。
元のグラフについて、辺(a, b) が存在するとき、辺(a0, b1)、(a1, b2)、(a2, b0)を張ったグラフを考えて、そのうえでS0からT0に到達するパスがあればよい。
上記のグラフに対してBFSなりダイクストラなりを行うとOK
このとき、実装は実際にグラフの頂点を増やすのではなく、最短経路を保持する配列distの次元を増やし、キューに次展開するノードだけでなく状態も合わせて入れておくと(例: pair (2, 1) がノード2、経路長mod 3 が1であることを表し、dist[2][1] はノード2に経路長mod 3 が1で来る場合の最短経路を表す)実装が楽。
参考:

drken1215.hatenablog.com

得られた知見

・探索 + 状態を持つ -> 拡張ダイクストラ / BFS
・拡張ダイクストラは最短経路を持つ配列distの次元を増やすと実装が楽

解くのに必要な要素

・状態の数だけノードを増やしたいと思う心

周辺調査によって得られた知見

特になし

AGC002 knot puzzle

https://atcoder.jp/contests/agc002/submissions/6740547

所感

AGC500も大した事ねえなガハハ(on 調子)

問題概要

N本のロープがあり、i番目のロープの長さはa_iである。
i番目のロープの右端とi+1番目のロープの左端が結ばれているとする。
長さL以上の繋がったロープのみ結び目をほどくことができるとき、すべての結び目をほどくことはできるか判定し、可能ならその手順を出力せよ。

取った方針

まず、ロープを結び目を含まないロープと結び目を一つ含む長さL以上のロープに分割できることが必要だと考える。(結び目を2つ以上含む場合、一つの結び目を解決した時点で長さがL未満になる可能性があるのでNG)
"結び目を一つ含む長さL以上のロープ" につながっている結び目のうち一番端のものは、ほどいても残るロープの長さがL未満になることはないので、ほどくことができる。
よって、"長さの和がLを超える隣り合ったロープが存在する" という条件を満たせば可能で、"長さの和がLを超える隣り合ったロープ" 以外の結び目を端から順番に解いていけばよい。

正しい方針

同上

得られた知見

・構築->必要条件から攻める

解くのに必要な要素

・必要条件を列挙したらなんだかんだで十分だったというアレ

周辺調査によって得られた知見

特になし

ABC136 E MaxGCD

https://atcoder.jp/contests/abc136/submissions/6726558

所感

時間があればできた……？(怪しい)

問題概要

長さNの数列Aがある。以下の操作をK回以下行って得られるN個の数のGCDを最大化せよ。

i != j のA_i, A_j について、A_iに1を足し、A_jに-1を足す。

取った方針

GCDをmに固定して考える。(典型)
mod m を取った数列Bを考えると、(典型)この総和が0(mod m)になることが必要。
上記の条件を満たし、移動する数(操作の回数)がK以下であることが必要。
これはmod m を取った値の総和から一番大きいものを引いたもの。(大嘘)
↑でWAしたあと、増やしてmの倍数になるパターンと減らしてmの倍数になるパターンの存在に気づき、コスト(増減する数)が小さい方を取ればよい(大嘘)と思い時間切れで死亡
そもそも解の候補を全探索していたが、本当は解の範囲は1<=x<=106 でなく 1<=x<=500*106なので間に合う解法ではない

正しい方針

GCD をmに固定して考える。(OK)
mod m をとると、増やしてmの倍数になるパターンと減らしてmの倍数になるパターンが存在する。(OK)
増やす量と減らす量が等しい必要があり、これはソートして累積和をあらかじめ計算しておくことで全探索ができる。(NG)(デバッグで気づけたはず)
ここまででNlogNで判定ができる。
解の候補を全探索するとmax(A)NlogNで間に合わないが、解の候補はAの和の約数(GCDがmの時、Aはcmで表せるはずなので)であり、これはsqrt(Nmax(A))なので間に合う。(NG)(時間があっても怪しいと思う)

得られた知見

・数a, b, c...のGCDの候補はa+b+c...の約数(約数の定義から自明)(a, b, c...のGCDがmである -> a, b, cはmを約数に持つ なので)
・公約数 -> mod を取ると余りだけを考えられて見通しがよくなる

解くのに必要な要素

・GCD の候補は総和の約数とすることで探索範囲をsqrt(N)にできる

周辺調査によって得られた知見

特になし

AGC014 Closed Rooms

atcoder.jp

所感

700 初自力、ものすごい逆詐称だ
problemsのれこめんどというのを使ってみたけど、500埋め終わったらこれをやったらいいかな

問題概要

'.'と'#' からなる盤面H*Wのが与えられる。1回の操作でイカができる時、最短何回で外周(0行目、0列目、H-1行目、W-1列目)に到達できるかを求めよ。

- 今いるマスから隣り合う部屋に移動することを K回まで繰り返す。ただし、'#'には移動することはできない
- その後、'#'を K 個まで選び、それらを'.'に置き換える。

取った方針

Kマス移動してK個の壁を破壊できるので、壁は存在しないとみなすことができる。
最初の操作では壁を破壊することができないので、最初のKマスの移動だけ全探索して、行ける中で外周に一番近い点を見つけたあと、そこから壁がないものとして直進した時が最適となる。
全探索はBFSをして、その後に外周までの距離をKで割って切り上げたものが答え。

正しい方針

同上

得られた知見

・特になし

解くのに必要な要素

・Kマス移動 + K個壁破壊 -> 壁は無いものとして扱うことが可能
・BFS

周辺調査によって得られた知見

特になし

ARC092 D Two Sequences

atcoder.jp

所感

基礎 * 大量だけど解けないね、悲しみ

問題概要

長さNの非負整数列a, b が与えられる。
a, bからそれぞれx, y を一つずつ取り出す方法はN2通りあるが、そのx + y のXORを計算せよ。

取った方針

XORなので各桁を独立に計算したくなるが、足し算を各桁独立に行えず死亡

正しい方針

a + b の二進i桁目(0-indexed)を求めるには二進i桁目までの a + bを計算すればよい。(それはそう)
二進i桁目までのみ考える時、mod 2i+1 で考えてよい。(二進i桁で表せる数は2i+1 - 1までなので)
ここで、a, b 共にmod 2i+1 を取っておくと、a + bは高々4 * 2i である。
2i = T とおくと、4T未満でi桁目が1となるのは[T, 2T) と[3T, 4T)である。(2進i桁目は2i ごとに繰り上がることを考えるとそれはそう)
よって、aを固定すると条件を満たすbの個数は二分探索で求められる。

得られた知見

・XOR -> 各桁独立に考える
・a + bのi桁目 は aのi桁目まで + b のi桁目まで と等しい
・n進i桁目(0-indexed) はniごとに1増える(n = 10なら小学生でも知っている事実)
・n進i桁目までのみを考える時、mod ni+1 で考える、n = 10で（ｒｙ
・modを取ると上限が定まり全探索ができることがある

解くのに必要な要素

・同上

周辺調査によって得られた知見

特になし