課題内容
左側の各パネルの文字に対し,カーペット上に同じものが何個あるかをカウントし,右側にそのカウント結果を運び出してください。
※以下はネタバレを含みます。自己責任のもと閲覧をお願いします。
素直な解法
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。
多分これが一番早いと思います
まだ速くできるなら教えてください(よろしくおねがいします)