ABC089 D - Practical Skill Test - lab2Gがプログラミングするブログ

　本日こなせた400問題についてお話しします　今日は放課後にメインの趣味である音楽ゲームのうちjubeatというゲームでEngraved Markというレベル10の楽曲でEXC(満点のことです理論値とも呼んだりします)が出ました　あと再び新規に400点問題が解けました　D問題！　いい日〜〜〜

　「続きを読む」から今回解けた問題についてお話します

問題ページ

https://beta.atcoder.jp/contests/abc089/tasks/abc089_d

問題文概略

Q回与えられたスタートとゴールに対して魔法少女さんが一定間隔で数字の刻まれたマスを踏んでいく、みたいな問題です
(魔力が云々ありますが、移動距離見てるだけだったりします)←夢のない発言
スタートがL、ゴールがR、間隔がDとして(R-LはDの倍数)
L, L+D, L+2D, …, R
みたいな感じ(R=L+IDになるIは必ず存在)

問題について

マスとその座標をどう持つか
累積和の利用

が主だと思います
前者ゲーに見えますが、なんと距離計算いちいちやってると間に合わない
そこで「どうしてDを最初にinputするの？」とか「移動区間に法則性がある？」とか考えてると、なんと累積和が使えることに気がつきます

因みに「累積和」とは、たとえば[1,2,3,4]という配列があるとして、これの累積和というと
[1, 1+2, 1+2+3, 1+2+3+4] = [1, 3, 6, 10]
といったような「配列の最初から順々に加算させて配列として持たせる」ことを言います(という認識)
これを用いて2から4の和が知りたい！となった場合は
10 (配列の3番目 1+2+3+4) - 1 (配列の1番目 1) = 9
として、いちいちループを回さなくても呼び出し2つで指定区間の和を導出することができます

方針

マスとその座標を辞書型で保存し、マスに書いてある数字をキーとして座標を呼び出す辞書を作成
経路パターンがD通りあることに着眼して、その経路パターンごとに距離計算の累積和リストを作成
　「経路パターンがD通りある」というのはメモ書きしてて気づきました
　たとえばD=3の時、1のジャンプ先は1+3=4なので2,3には止まらないんですよね　そして数字の間隔はDで一定なので、綺麗にズレるんです
　また、4からスタートする場合はスタート1の経路上ゆえ、1を消せば解決するので必要ありません　間隔Dで経路パターンも戻ってくるので、経路パターンはD通りになります
Q回のマス移動は累積和リストを用いてO(1)の減算で終わらせる

変数説明

わかりづらいであろうソースコードの変数の説明をちょこっとしますマスの数字を k とします

M
　key：マスの数字，value：マスの座標(x,y)　マスの数字から、その座標を取得します
anslist
　｛経路パターン(k-1 mod D) ］［経路のint(k-1 / D)番目］で格納　あるパターン上の始点(D=3なら1,2,3)からkまでの距離の和が格納されているのでk=Rからk=Lを引けばLR間の距離が求まります
sub_anslist
　［経路のint(k-1 / D)番目］で格納　anslistを作成するための道具

ソースコード

H,W,D = map(int,input().split())

M = {}

for h in range(H):
    A = list(map(int,input().split()))
    for w in range(len(A)):
        M[A[w]] = [h,w]

anslist = []
for d in range(1,D+1):
    ans = 0
    sub_anslist = [ans]
    now = M[d]
    for i in range(d+D,(H*W)+1,D):
        nex = M[i]
        ans += abs(nex[0]-now[0])+abs(nex[1]-now[1])
        sub_anslist.append(ans)
        now = nex
    anslist.append(sub_anslist)

Q = int(input())
output = []
for q in range(Q):
    L,R = map(int,input().split())
    left = anslist[(L-1)%D][(L-1)//D]
    right = anslist[(R-1)%D][(R-1)//D]
    output.append(str(right-left))
        
print("\n".join(output))

感想

『問題について』で挙げた話を中心にACに至るまでの経緯を述べます

「マスとその座標をどう持つか」が重要で、それをうまく持って距離計算の処理速度を速く済ますことが要求されている…
と思ってはじめ解いたのですが、Qから愚直に距離計算をさせた所TLEに　流石D、一筋縄ではいかない
(冷静にO（Q(HW)）(たぶん)なので終わるわけないですね、悲しい)
このTLEを受けて「距離計算を呼び出しワンパンで仕留めてやろう！」と思考を張り巡らせた所「累積和」が浮かび、O(Q)に抑えられ無事ACできました
今までやったことを応用できた実感があって気持ちよかったです　はえ〜すっごい快感

昨日の今日なので簡潔に書こうと思ったのですが、思ったより時間かかりました　しかし良い問題だと感じました　そうでもない？
無駄に更新の勢いがついてて、すぐに飽きないといいですが💦(音ゲー以外飽き性)
とりあえず、記事はMarkdownで編集しているのですが、数式記述にするべき箇所が多く見受けられるであろうので、こちらのお勉強もします　すみません(今日は夜も遅いのでサボりました🙇‍♂️)

それではまた