Ein Heftiges Heft

heftig: 1) von starkem Ausmaß, großer Intensität 2) leicht erregbar, aufbrausend (von Duden)

Human Resource Machine Year 32 の高速化

課題内容

f:id:Nitrone7:20190923015708p:plain 左側の各パネルの文字に対し,カーペット上に同じものが何個あるかをカウントし,右側にそのカウント結果を運び出してください。

※以下はネタバレを含みます。自己責任のもと閲覧をお願いします。


素直な解法

loop{
    a = input()
    cnt = 0
    for c of str:
        if c == a:
            ++cnt
    output(cnt)
}

実際のコード

-- HUMAN RESOURCE MACHINE PROGRAM --

a:
    INBOX   
    COPYTO   18
    COPYFROM 14
    COPYTO   19
    COPYFROM 14
    COPYTO   17
b:
    COPYFROM [17]
    JUMPZ    e
    COPYFROM 18
    SUB      [17]
    JUMPZ    c
    JUMP     d
c:
    BUMPUP   19
d:
    BUMPUP   17
    JUMP     b
e:
    COPYFROM 19
    OUTBOX  
    JUMP     a


DEFINE LABEL 14
eJwzYGBgcPaMqI/wjaj/G3avuTA6tWNz1OsethC1Bdt9N+w7kLhhH1AJw4osyemXin5MfV5mPcOt3Ln9
VGlE/feCz9X/cz9XH802q/PMUmzrzlRb8CpzzZJHOX/WV+cv2WpYrLXrUIXWLpD+RS0bKp1bfHaXdtbN
qprs3G4wXbENbO7SwokbFm2ZHDk/c9HseaWrf837fIB/cepZz6UnL6gsf33x1qqTF0TWOp9Zu/7S/lMb
mrac2mC08tJa6xnVq173xK183cMwCkbBKKAIAABDoGHy;

DEFINE LABEL 17
eJxjZ2Bg2N8aUc/Yeq+ZsXXvcSCX4U5boU9tG48nwygYBaNg2AMAyvoJiw;

DEFINE LABEL 18
eJyTZmBguNN2z25/K4PDopYA74wm62DB+pBUuyqG1o6yNUvCCu+dmFFw8sKMAuu7QKUM2zsYHCI6Up27
etWilSfklsdOSu2omvx4bujU6WuKpslu9J0heujkzHsnQGoragonFtQXTnzTsGWydu+WyQyjYBSMgkEH
ALHGL1g;

DEFINE LABEL 19
eJxTZWBgsElWbJudvLfJJjmiXj0+t1wqwrssNWR248ugk90vg9YsWR5cuto+LHFzSBTHTvkkjp1ALQwz
CiLqLQv2NoUVtnWKFElOFymS3ahYGVEvWfO52rvxc7Va871mtea2zifNr3ucW45uA+lJ7f+TlTXzVuaB
OdPTzy6eng4SY5rjHsM059Y6+bmJm9mXae1asOL5doZRMApGAd0AALcAPuw;

クエリを取りこむたびにカーペットの文字列を線形走査する。計算量は O(Q×|S|) で,400 ステップくらいかかる。

この方針で進めても目標は達成可能だけれど,たとえば問題文がこう書かれてあって競プロをすこしやってるなら絶対こうは書かないと思います:

文字列 S と Q 個のクエリが与えられます。各クエリの文字が S の中に何個含まれているかを出力してください。 制約: |S| < 10⁵, Q < 10⁵


前処理で計算量を減らす

というわけでなんというか当然のようにこうなる:

map = {
    A: 4,
    B: 5,
    C: 2,
    X: 3
}

loop{
    a = input()
    if a == 'A':
        output( map[A] )
    elif a == 'B':
        output( map[B] )
    elif a == 'C':
        output( map[C] )
    else:
        output( map[X] )
}

実際のコード

-- HUMAN RESOURCE MACHINE PROGRAM --

    COPYFROM 14
    COPYTO   17
    BUMPUP   17
    BUMPUP   17
    COPYTO   18
    BUMPUP   18
    COPYTO   15
    BUMPUP   15
    COPYTO   16
    BUMPUP   16
a:
b:
c:
d:
    INBOX   
    COPYTO   19
    SUB      1
    JUMPZ    e
    JUMP     f
e:
    COPYFROM 15
    OUTBOX  
    JUMP     a
f:
    COPYFROM 19
    SUB      0
    JUMPZ    g
    JUMP     h
g:
    COPYFROM 16
    OUTBOX  
    JUMP     b
h:
    COPYFROM 19
    SUB      4
    JUMPZ    i
    JUMP     j
i:
    COPYFROM 17
    OUTBOX  
    JUMP     c
j:
    COPYFROM 18
    OUTBOX  
    JUMP     d


DEFINE LABEL 0
eJwTZ2Bg8IntM/aJ3XoDyGRoi+fxlE9a4RqYftJtRdZk3+r8swkzCuxzZxRUNcTlObdPTuPtY0rk7Zud
fLKbP0Ovf29ezMxb+Y/nhhXKbgwr9Nl9NLvqKH8Gwyn1eIZTDKNgFIyCQQ8A+I8k4A;

DEFINE LABEL 1
eJzjY2BgmFrb5jK3yj2GpeJPVmD6zk9AIQbvxlTnNw0xIYtaPlfz9chuVJ7w4xZIvKPs4JyE1oNzGEbB
KBgFwwIAABqxFpg;

DEFINE LABEL 2
eJwTYGBgMEkr9PmUZh1sWXCveWrt0W3n60UPcTbdO3G8qe0cUJrheNOa+FWNa+Ila54XJVfsbZpQHDBh
RkHmIv6M2ccYRsEoGAVDGgAAg9sdOA;

DEFINE LABEL 4
eJwTYGBgyO2JCcnt2eIX0D3ZV7Jmi59i5cHwjjKjFL8SjhLD4oh6w2KW+Tylpavdyu03NVQe3abW/PlA
6FTRQ++mb9jHMApGwSgY0gAAKo4bIA;

DEFINE LABEL 15
eJwTY2Bg2JHy+QB/huzGV5kH5yzIZWg1LK4LXVrO4NBQGWGV0bS3ibFVbcHP9ufb13erPQUqZ1iQO392
XF7MzLlVMTNB/KyZDA5bprJEgdhTa7dMzmjaMplhFIyCUTAkAABr4SMr;

DEFINE LABEL 16
eJyTZ2Bg4CkVTF5bwnDqVKnknVOl516dKl3wACjMYFe1pKCg3j43oNs+d3nf0cKHE3LL90xiaI2dNH+2
w8THc4273BeuanRf2NvAMj+hNXNRV++f9Wz9TVuO9PvsVp7gfOZl78kLp0pPXuApbTsHMm/DoiatwEUc
+rPnVVkzzblnxzAKRsEoGHAAAI68OXI;

DEFINE LABEL 17
eJwTYmBguNPWlL+oZWdGRc3ODMVK+9xb+c7tcXnWM+LyuhZbFvxZ71eSuye7dMO+XdXmh++0mR8O6Nba
xddzdBtQK8OGRaIWrrO/BzCMglEwCoYkAACTJiBl;

DEFINE LABEL 18
eJwTZGBgMCzW8/Ir+R7wpuFe86Suo9s8+mYfi51kfffm5IMPgdIMQHbwnTat0oZKo5Xvi7V2vS/u3wsS
j5y/1/bZrK44BgLgTcOWydq9WyYTUjcKRsEooD8AAHeQIzk;

DEFINE LABEL 19
eJwzZmBguF/JMv9U6fzZt/Lnz16Qq7ZAJef9srTsW+vSsjl2PsoRPTSjYO/x5ArnMxU1zmeAyhlye84m
BHRXNQR0y2680vn64pXOtnNnejbsezjh1rqqyUYrp08xWvltSv9e4WmTrxdN+3GraFrhNZA+mVWZi1SW
uy/sXtK1OHDRzrUmC59vN1lYdfTTwtSz3UtOXnBcseJ83Mp7J/au/Hxg70qW+TNWa+0qXjv72Nr1K84f
2rziPMgMye3vl0luZ3lituPxoze7I4607nu+ff+BP+uNjxqtZBgFo2AUkAwASKxvLQ;

カーペットの文字列は固定なので人力で数えた結果を床に記録し,A, B, C, X と順に見ればよい。

計算量は O(Q×(文字種類数)) になる。ステップ数は 59。

もっと速くする

そもそもループ内が map[a] みたいな形にできれば終わりなのでは?となったのでいろいろやってたらなんかできた。

arr = [4, 5, 2]
plus = 23

loop{
    a = input()
    a -= 'X'
    if a == 0:
        output( 3 )
    else:
        output( arr[a+plus] )
}

実際のコード

-- HUMAN RESOURCE MACHINE PROGRAM --

    COPYFROM 9
    SUB      8
    COPYTO   5
    COPYFROM 4
    SUB      8
    COPYTO   2
    COPYTO   3
    ADD      2
    COPYTO   0
    COPYTO   1
    BUMPUP   1
    BUMPUP   3
a:
b:
    INBOX   
    SUB      9
    JUMPZ    c
    ADD      5
    COPYTO   14
    COPYFROM [14]
    OUTBOX  
    JUMP     b
c:
    COPYFROM 3
    OUTBOX  
    JUMP     a


DEFINE LABEL 0
eJyTZmBgMKtlcHhedrTQr8SszrD4ZPfePMEVKjkb9qVlix5iz96wD6iEYVNdhJVeg56XXNvzoogO53a+
nvmzz/QIrnjZu3Ptkf7PB5omRBxpmvD5AEjt2pLUjjttbZ0gtuvs2TYG078HVE0+GM4wCkbBKBh0AABH
jy4s;

DEFINE LABEL 1
eJxTZGBgkMl3dpLJ/1z9P3dF1//ctnNAIQbDYlGLP1Vmls4tDA77W52dIjoCvMU6r/mXdqpFG3d1xRl3
/cm60/a8qKD+c3VDpWitX0lVw6Wie83vi6saJGuqGu606fUHdLPMD+hestW4q3/vz/aII+fr284F1604
H1YIscNm3iXTd9MfRTCMglEwCgYMAACAlDu/;

DEFINE LABEL 2
eJyTZGBgONOTGXum52A4X09MiHPLZN/ehtfuhsVtLrfyeTy7M+eHRaYcLaxL0uuvS5q+xiZZdiN/xt7j
jrkrzv+paju3qtH8cGmn/abSzlvrJnWVrp7U9X4Z0EiGTwuP6iTOOenGNCfAm2EUjIJRMGgBABbmLic;

DEFINE LABEL 3
eJxTYGBg4M/4HsCevSZ+b96frK2Fsxs1y+pmsVS4L7xeI3qot+HkhTcNAVePN127CVTKwNj62r21Wc9r
am1mbEWNYHJ09ZICloqI+rUl16asLbGeIVLkvtCyQHbj3rwlWx/lfD7Anj37mGdW6lmTtLr7IP2/5r12
r5t70u3AHB7Pm5NlcxhGwSgYBQMKAEADOoo;

DEFINE LABEL 4
eJwTYWBgWFuyJt6vxD3mUMUWP7XmLX5ybTEhs9q74n62N+UntN5rftKs2Ha+XnL61Nq6WXOr1ixRrHy/
zK1851rNslvrTpXabzIs1trlV3Jp/8euzwcYRsEoGAVDCgAApcIn8A;

DEFINE LABEL 5
eJyLZmBguG/H43nI9rW7n6VkULVJQl6c8dHC/0bzZ8cZn1tabRKyqtpk51o/y4gjLLYMp6IdGE4BtTAs
8tTrZ/S6tB/Cls0B0fPCVnTNC+vfeyPCaGVfTMzMp/FbJkembJlskiY5fXJa7h6QmhVZDK0iRYptDZWv
eypqXveAxHhK7XN5Spu2JFc8336/8ui2qbV/1n+pFVwBkrNuT3Ve3/09oGnC86I9kxTbpCfz9klPvrUu
dtLz7U0TRA959N07kduTepavB+Kuqwtyyz8tPFq4YumtTMvVtzK3rpHNKV7blG+4bkOl4brXPSJrt0yO
W8kyX2V5yCqdJYmb+Rc3belesmSr26amLSD9GXuNUlr3GaUkHOiKqz2YGXvmeFfcyxNnE46cupXpcGZD
pcMZ53bl0yu6+I5PnhRxeMvk9ccKJ3ad2DI59dTjuamnMhc1nT63tOl005Yzxzl28h3P3bP/QO4e5/2J
m9X2JW5mGAWjYBACALGKqYE;

DEFINE LABEL 8
eJwTY2BgmFvF4KBYec+Op1TPa0bBmvi4PK3S/7mpHY9yAiY8ylFbUFx0af/7YvPDHWVt54LrVpx/0+B8
Rq157/H9rc+3y7XZb6pt4yhxbnGPUWtmiXrTEOD9pbbNhWEUjIJRMCQAABoZKPM;

DEFINE LABEL 9
eJwzYGBgmBapFi0UfTBcP0Yy6ETcNf/ERD2vX8kn3c5mrHD9n1voY1ngHjOjQDDZsqC/QieTt88ntmtx
SJTsxhkFshs7ypq2AI1gKKi/5s/ZpOd1vGmFq1wbg4Nx12yb3J7ZNvMnrnC9Ofma//QpB8OnTwlJvTlZ
NqdpwvOij10cJaWdueV32vorrNu1Svl6tErnT+yvsJjyudpg+uxG7pkruk7OnDzp5Ey1BaFTZTc+nMCx
c3mf1q7aNo6dT5r/rNdreL/sfL37QoZRMApGAUUAAO0fVy0;

DEFINE LABEL 14
eJzTY2BgeBszu3F1rHP76li1pwxg/ufqu0lmdWWpVQ2f0u41b0jn7fPMejyXPVt2Y3emz+7Jaf17bZL7
98on5e45kMixE6SnOv9ztWWBWZ1hcVXD8aaqhtbmvU0gccma6el/qkRr/1St6GqorJvVUHlpv13VvROr
GhlOLWqpOirXtmEfSN2RfsW2I/1Kp5UnVB2F8N8vc5i4ZfKeSW2dNyc7t7vOVmyzmbei6+qCk92TF+r1
M4yCUTAKqAIAqIZUHg;

ポインタと文字同士の sub をうまく使って一発で文字に対応する個数を出せるように考える。ただし A, B, C が近いのに対して X がやたら遠くて,カーペットは 5×3 マスしかないのでこれはとりあえず例外処理をすることにする。

'A'-'X', 'B'-'X', 'C'-'X', 'X'-'X' はそれぞれ -23, -22, -21, 0 になる。 -23, -22, -21 は 23 を足すと 0, 1, 2 となるので,前処理として床の 0, 1, 2, 3 の場所に 4, 5, 2, 3 を置いておけば,あとはこれらのポイントがそれぞれ指す値を出力すれば良い(X のときはそのまま 3 を出力する)。

ちょっとしたテクとして,前処理として床においておく 2 や 23 はそれぞれ 'C'-'A', 'X'-'A' から生成できて,これは 0 からインクリメントするより高速に動く。 計算量は O(Q) で,ステップ数は 42。

多分これが一番早いと思います

まだ速くできるなら教えてください(よろしくおねがいします)