作業のお供としての ASMR

この記事は ISer Advent Calendar 2020 の 4 日目として書かれました.

もともとこの日は ISer らしい記事を書こうと思っていたのですが,間に合わなかったので埋め合わせとしての簡単な話をします.

ASMR is 何

ここ最近よく耳にすることがある言葉ではないでしょうか.Wikipedia には「ASMR (Autonomous Sensory Meridian Response) は, 人が聴覚や視覚への刺激によって感じる,心地良い,脳がゾワゾワするといった反応・感覚」とあります.

主に睡眠導入やストレス解消を目的として使用されることが多いようですが,特にオススメしたいのが作業のお供としての使用です.

どんな音声?

基本的には「本人が ASMR だと思ったら ASMR」というスタンスで語られることが多いですが,主なジャンルとしては,タッピング,耳のマッサージ,耳かき,咀嚼音あたりでしょうか.

バイノーラルマイクと呼ばれる,立体的な音を録音できるマイクを用いて作られることがほとんどです.

タッピング

物体を叩いて出る音を録音したものを言います.マイクを叩いて音を出すこともあれば,他の様々な物体を叩いて出た音を録音することもあります.

私的には初めて聞く ASMR としてオススメだと思います.

耳のマッサージ

耳の形をしたマイクに対してマッサージして出る音を録音したものを言います.ゴム手袋などのアタッチメントをしてマッサージをする音声もあれば,実際にクリームやオイルなどを塗ってマッサージをする音声も多くあります.

耳かき

大きく二つに分かれていて,コルクなどを耳かき棒で擦って音を出すものと,耳の形をしたマイクを現実で耳かきするように擦るものがあります.

耳かきされて心地良くなったり眠くなったりしたことがあるでしょうか? これを聞けば同じ経験ができると思います(もちろん感覚はないですが).

個人的には一番好きなジャンルです.

咀嚼音

何かを食べて出る音を録音したものを言います.せんべいや金平糖など,硬いものを題材として扱われることが多いですが,チキンなどを扱う音声もあります.

このジャンルは好き嫌いがはっきり出ると思います.「咀嚼音」は一般的にネガティブと捉えられがちですよね.

他にも...

囁き声,シャンプー,炭酸水の他,環境音も ASMR に入れられることがあります.

ASMR のハマり方

イヤホンをします(ここ大事).Youtube で ASMR と検索します.気になったものを再生します.おわり.

オススメの ASMR クリエイター

せっかくなので,自分が良いと思った ASMR のクリエイターをいくつか挙げたいと思います.

Hatomugi

色々なジャンルの ASMR を投稿している方で,私が ASMR にハマり出した頃によく再生していました.

オーソドックスなものが多いので,初めての方にはオススメです.

周防パトラ

現在毎週月曜日の24時から睡眠導入 ASMR を配信している方です.

作業用には向かないかもしれませんが,睡眠のお供として用いてはいかがでしょうか.

ともえとエルゼのほんわかASMR

週に数回の高頻度で長時間 ASMR 配信をしている方です.リクエストに応じたジャンルを取り上げてくれます.

生配信だけでなく,特定のジャンルを取り上げた動画も投稿していて,ボリュームのあるチャンネルとなっています.

ASMR を聞くときに絶対にやるべきこと

それは Youtube Premium に加入することです.バックグラウンド再生機能が神で,バッテリー減少を抑えられます.

学生であれば月額 680 円とめちゃくちゃお得です.絶対に加入すべき.ASMR 興味なくても.

最後に

ここまでお読みいただきありがとうございました.ASMRって本当にすごくて,家で作業しているときはほぼ100%聞かなきゃいけない体にさせられてしまいました.

皆さんもオススメの ASMR 配信者やジャンルを見つけて,快適な ASMR ライフをお送りください.

Aheui(아희)で AtCoder Beginners Selection を解いてみた

この記事は ISer Advent Calendar 2019 の 11 日目として書かれました.昨日は joechtr くんの記事でした.

Advent Calendar 初エントリーということで,そもそもブログすら書いたことのなかった自分はネタ探しから苦労...

東京大学のコンピュータ系サークル TSG が今年の駒場祭で放送していた TSG Live! 4 のライブコードゴルフ大会なるものを見ていたところ,大会内で使用可能な言語だった Aheui に心を惹かれ,これについての記事を書くことに決めました.

Aheui とは

公式 Document 曰く,「ハングルで書く難解なプログラミング言語」とのこと.俗にいう esolang です.

この Document 内で,以下のようなコードが例示されていました.

밤밣따빠밣밟따뿌
빠맣파빨받밤뚜뭏
돋밬탕빠맣붏두붇
볻뫃박발뚷투뭏붖
뫃도뫃희멓뭏뭏붘
뫃봌토범더벌뿌뚜
뽑뽀멓멓더벓뻐뚠
뽀덩벐멓뻐덕더벅

これはなに?

実行すると Hello, world! と出力されます.どうして...

このコードを理解するとともに,自分で Aheui*1 を書いてみようというのがこの記事の目標です.

ハングルの仕組み

Aheui を読み書きするためにはハングルの構造をある程度理解しておかないといけないので,ここで簡単に説明します.

ハングルの文字は「子音」と「母音」と「終声」*2の3つの部分から成ります.

読み方は簡単で,たとえば子音 ㄱ (k) ,母音 ㅏ (a) からなる 가 は ka と発音します.これに終声 ㄱ が加わった 각 は kak と発音します*3

また,子音として発音しない ㅇ があり,これと母音 ㅜ (u) からなる 우 は u と発音します.これに終声 ㄹ (l) が加わった 울 は ul と発音します.

子音となるもののうち,Aheui で意味をもつものは次の15個です.

ㄷ (t) , ㄸ (tt) , ㄴ (n) , ㅌ (th) , ㄹ (l) ,
ㅁ (m) , ㅂ (p) , ㅃ (pp) , ㅍ (ph) , ㅅ (s) ,
ㅆ (ss) , ㅈ (ch) , ㅊ (chh) , ㅇ, ㅎ (h)

形の似ているものは大体似たような音を持ちます.

基本的な母音は,日本語のあいうえおの他に,/ɔ/ (eo) と発音するものがあります*4. また,母音の前に y がついたものや,母音同士を組み合わせたもの*5も母音として扱われます.

Aheui では主に次の8個が意味を持ちます.

ㅏ (a) , ㅑ (ya) , ㅜ (u) , ㅠ (yu) , ㅓ (eo) , ㅕ (yeo) , ㅗ (o) , ㅛ (yo)

この母音を構成する部品がコードの動きを表します.たとえば ㅏ は右方向に一つ動き, ㅠ は下方向に二つ(一つ飛ばしで)動きます.

終声となりうるものはたくさんあります.ここでは割愛.Aheui では ㅇ , ㅎ ,それ以外の3種類に分かれます.

Aheui の仕組み

C 言語や Python などという何でもできるプログラミング言語とは違い,Aheui には 26 個のスタックと 1 個のキューと extension protocol しかありません.

また,演算も以下のものしか存在しません.

ㄷ(加算), ㄸ(乗算), ㄴ(除算), ㅌ(減算), ㄹ(あまり), ㅁ(入力), ㅂ(出力), ㅃ(複製), ㅍ(交換), ㅅ(選択), ㅆ(移動), ㅈ(比較), ㅊ(分岐), ㅇ(無), ㅎ(終了)

これらと先ほどの母音を組み合わせて実装をしていくことになります.

早速やってみよう

ということで本題です.

AtCoderAtCoder Beginners Selection に載っている問題を解いていきます.

残念ながら(?) AtCoder で Aheui を提出することはできないので,手元で実行し AC かどうか確認することにします.

ちなみにコーディングは, TIOAVIS で行ないました.AVIS でコード組立+デバッグをして TIO で大きなケースを確かめるという手順です.

Welcome to AtCoder

標準入力にある  3 つの整数の和と文字列を出力せよという問題です.

まず入出力と加算に関して,以下の文字があります.母音を除いた表記ができないので,便宜上 ㅏ (a) を加えています.

  • 방:標準入力から数を読み取り,その値を今いるスタックに積む.
  • 밯:標準入力から文字を読み取り,その文字コード (UTF-8) の値を今いるスタックに積む.
  • 망:今いるスタックの先頭の値を出力する.
  • 맣:今いるスタックの先頭の値の文字コード (UTF-8) が指す文字を出力する.
  • 다:今いるスタックの先頭2つを消去し,その和をスタックに積む.

「今いるスタック」って何ぞや?と思うかもしれませんが,ここでは飛ばします.

和を出力するパートは簡単ですね.방방방다다망 で終わりです.

文字列の出力ですが,文字列の長さを読み取ってくれるコマンドはないので,無事詰みです.いかがでしたか?

嘘です.Aheui では入力を読み取る際,値 or 文字がないとき  -1 が勝手に入力されるので,これを使えば文字列の終点を知ることができます.

というわけで,読み取った文字(値)が  -1 かどうかを判定するために,次のような文字も用います.

  • 차:今いるスタックの先頭の値が 0 でないときは母音の示す方向を,0 のときは母音の示す方向と逆の方向に動く.先頭の値は消去される.
  • 빠:今いるスタックの先頭の値を複製してそのスタックに積む.

読み取った値に +1 して 차 で判定すればいいですね.

スタックに値を積むには,以下の文字を用います.

  • 바:終声がㅇ, ㅎ以外の場合,終声に対応する値が今いるスタックに積まれる.
     0: 終声なし(바)
     2: ㄱ, ㄴ, ㅅ
     3: ㄷ, ㅈ, ㅋ
     4: ㅁ, ㅂ, ㅊ, ㅌ, ㅍ, ㄲ, ㄳ, ㅆ
     5: ㄹ, ㄵ, ㄶ
     6: ㅄ
     7: ㄺ, ㄽ
     8: ㅀ
     9: ㄻ, ㄼ, ㄾ, ㄿ

肝心の  1 がない!

しかし  1 の表し方はたくさんあるので,そのうちの適当なものを用いればよいです*6

  • 타:今いるスタックの先頭  2 つを消去し,消去前に先頭にあったものから,  2 番目にあったものを引いた差をスタックに積む.
  • 나:今いるスタックの先頭  2 つを消去し,消去前に先頭にあったものから,  2 番目にあったものを割った商をスタックに積む.

「出力の末尾には改行を入れること」とあるので,\n文字コード  10)も出力しておきます.

というわけで,これらをもとにして書いたコードはこちらです!

방방방다다뭉
맣붛멓떠벓벆
초빠받반타다
빠타희

 1\le a, b, c\le 1000, |s| \le 100 なので次のような最大ケースが考えられます.

1000
1000 1000
abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuv

これに対して先ほどのコードを実行すると,次のように表示されました.

3000 abcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuvwxyzabcdefghijklmnopqrstuv
User time: 0.029 s

 AC 

Product

 2 つの整数が与えられて,その積の偶奇を判定する問題です.

Aheui には余りを求める関数があるので,これを用いれば簡単に偶奇が判定できます.

  • 라:今いるスタックの先頭  2 つを消去し,消去前に先頭にあったものから,  2 番目にあったものを割ったときの余りをスタックに積む.

出力の指定は「積が奇数ならOddと、偶数ならEvenと出力せよ」

  • 맣:今いるスタックの先頭の値の文字コード(UTF-8)が指す文字を出力する.

これをもとに O, d, d,もしくは E, v, e, n を出力しなければなりません.めんどくさ...

使う必要のある O, d, E, v, e, n の文字コードはそれぞれ  79, 100, 69, 118, 101, 110 です.

2\sim 9 の整数と,加減乗除を用いてこれらの値を捻出します.ただし,ㅃ で値が複製できるので,これをうまく使えばコードが短くなります.

 79 = 8\times 9 + 7

 100 = 79 + 3\times 7

 69 = 8\times 8 + 5

 118 = 69 + 7\times 7

 101 = 69 + 4\times 8

 110 = 101 + 9

これをもとにして書いたコードはこちらです!

방방따박루밣따붅
붉떠벏벓처봃그두
다빠맣밪붉뭏뻐뻐
뭏멓뻐더떠밝밠뚜
희멓뭏뻐붏벘멓더
해도벏도떠

 1\le a, b\le 10000 なので次のような最大ケースが考えられます.

Test 1: 10000 10000  
Test 2: 9999 9999

これらに対して先ほどのコードを実行すると,次のように表示されました.

Test 1: Even
User time: 0.036 s
Test 2: Odd
User time: 0.031 s

 AC 

Placing Marbles

長さ 3 の文字列中に存在する 1 の数を求める問題です.

文字として読み取って,それが 1文字コードと一致すれば答えを  +1 すればよいです.

スタックが複数あるので,読み取った文字をもっておくものと,ans 用のものと,文字数の残りをもっておくものをそれぞれもっておけばよいですが,一応  1 個のスタックだけでも実装可能です.

ans をスタックの一番奥に入れておいて,その手前で読み取った文字の判定を行なっていきます.

부두러벅
붛어차볼텨
빠붔뱛벖또
너범해초더
멍더터뻐희

このコードの実行順を追っていくとわかると思いますが,もし盤面をはみ出た場合は,ちょうど反対側に移動して実行が継続されます.(盤面はトーラス)

この問題のテストケースは  \{0, 1\}^{3}8 通りしか存在しないので,すべて試すことにします.

Test 1: 000
Test 2: 001
Test 3: 010
Test 4: 011
Test 5: 100
Test 6: 101
Test 7: 110
Test 8: 111

これらに対して先ほどのコードを実行すると,次のように表示されました.

Test 1: 0
Test 2: 1
Test 3: 1
Test 4: 2
Test 5: 1
Test 6: 2
Test 7: 2
Test 8: 3
User time: 0.018 s

 AC 

Shift only

数列  A に対し, 2 で割り切れる回数の最小値を求める問題です.

これくらい複雑な問題になると1個のスタックだけじゃどうにもならないので,以下のように値を管理していきます.

stack (終声なし):  2 で割る操作をする場所

stack ㄱ:  N を保持したあと,各要素の  2 で割り切れる回数を保持しておく場所

stack ㄴ: 数列  A を保持しておく場所

stack ㄷ: ある index までの, 2 で割り切れる回数の最小値を保持しておく場所

最終的に stack ㄷ にある値が出力すべき答えとなるはずです.

これ以降,スタックの先頭にあるものから順に  0, 1, \ldots と index を付けることにします.たとえば,stack ㄱ の  0 番目の値を  ㄱ_0 と書きます.また,stack (終声なし) は  None_0 などと書きます.

スタック間の値の受け渡しや,操作の対象となるスタックの選択を行なうコマンドがあります.

  • 사:終声で指定されたスタックに操作対象を移す.
  • 싸:終声で指定されたスタックに,今いるスタックの先頭の値を移動させる.

まずこれらのコマンドを使いながら,数列  A_1, A_2, \ldots, A_N を読み取っていきます.

 ㄱ_0 の値が  0 でない限りは,標準入力から値を 1 つ読み取り,それを stack ㄴ に移動します.そして, ㄱ_0 の値を  1 減らします.この操作を繰り返せば, ㄱ_0 = 0 となり,stack ㄴ には数列  A_1, A_2, \ldots, A_N が保持されます.

この操作の部分コードです.

삭방뺘희차방싿밧박나탸

次に,stackㄴにある値を一つずつ,  2 で割り切れる回数を求めます.  2 で割り切れるとき,  2 で割った余りは  0 なので,ㅊ を用いて回数を数えていきます.

 ㄴ_0 2 で割った余りが  0 のとき, ㄴ_0 2 で割った値に置き換えたあと, ㄱ_0 の値を  +1 して操作を繰り返し,余りが  1 のときはもう  2 で割り切れないので,回数を数えるのは終わりです.

この操作の部分コードです.

삳빠박랴희처박나삭발밨타다

そして,  2 で割り切れた回数である  ㄱ_0 と,ans の値のある  ㄷ_0 を比較します. ㄱ_0 \lt ㄷ_0 の場合, ㄷ_0 の値を  ㄱ_0 で置き換える必要があります.

2 つの値を比較するコマンドが存在します.

  • 자:今いるスタックの先頭 2 つを消去し,消去前に先頭にあったものを  x2 番目にあったものを  y として, x \le y のとき  1 を,そうでないときは  0 をスタックに積む.

これでこの問題で行なう操作は終わりです.あとは,数列  A_1, A_2, \ldots, A_N に対しすべて調べ終わっているかどうかを確認するため,一番初めに stack ㄴ に  0 を入れて「終点」と扱うことにすれば,わざわざ残りの数を管理する必要がなくなるのでうれしいです.

以上の部分コードをうまく組み合わせるとこのようにできます.

부방뺘붕처사밟밟따싿산쑤썩두섣썯석
싼속코싼불밬밧튜붸희멍수보선삳빠토
쑥뻐토터벘추러벅뻐처솓뼈쑤선추저
석솓뻐석터뻐숙썩고뻐해도서토뻐속
      다사박노

 1\le N\le 200, 1\le A_i\le 10^{9} なので次のような最大ケースが考えられます.

200
536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 536870912 

これらに対して先ほどのコードを実行すると,次のように表示されました.

29
User time: 0.439 s

 536870912 = 2^{29} なので, AC 

Coins

 0 \le i\le A, 0\le j\le B, 0\le k\le C を満たす整数の組  (i, j, k) であって,  500i + 100j + 50k = X を満たすものの個数を数える問題です.

式の両辺をあらかじめ  50 で割っておくと,式が  10i + 2j + k = X / 50 \cdots(\ast) となって簡単になるので,先に  X 50 で割っておきます.

複数のスタックを用いて,以下のように値を管理していきます.

stack (終声なし):  i, j, k の値を確認するのと, (\ast) が成立するかどうかを判定する場所

stack ㄱ, ㄴ, ㄷ, ㄹ: それぞれ  A, B, C, X/50 の値を保持しておく場所

stack ㅁ, ㅂ, ㅅ: それぞれ  i, j, k の値を保持しておく場所

stack ㅋ: あるindexまでの,式が成立する組の数を保持しておく場所

最終的に stack ㅋ にある値が出力すべき答えとなるはずです.

まずは  i, j, k がそれぞれ  A, B, C 以下であるかどうか判定する部分コードを作ります.

比較コマンド ㅈ と分岐コマンド ㅊ を用いて, k \le C ならば  (\ast) の判定に移り,そうでなければ  j +1 k 0 にしてもう一度  i, j, k の判定に戻ります.

 j についても  j \gt B ならば  i +1 j 0 にして繰り返します.

 i \gt A となった場合,考えられるすべての組について判定し終えたので,stackㅋにある値を出力して終わりです.

ここまでの部分コードは次の通りです.

삳빠싸삿빠싸사쟈숫차우
우 더러벘벌섭터뻐  
산빠싸삽빠싸사쟈숩차우
우 더러벘벌섬터뻐 
삭빠싸삼빠싸사쟈숰차우
해       멍 희

次に, (\ast) が成立するか判定する部分コードを作ります. i = ㅁ_0, j = ㅂ_0, k = ㅅ_0 なので,各スタックに移動して値を複製したあと stack (終声なし) に移しています.

この操作を行なう部分コードは次の通りです.

삼빠싸사박발따따삽빠싸사밧따삿빠싸사다다

そうすると, None_0 = 10i + 2j + k となるので,この値と  ㄹ_0 = X / 50 を比較します.

上の  2 つの値の差が  0 ならば,stack ㅋ の値を  +1 します.

以上の部分コードと入力もろもろを行なうコードを組み合わせるとこのようにできます.

방싹방싼방싿방박발발따따나쌀바쌈바쌉바쌋바쑼
삳빠싸삿빠싸사쟈숫차우          아
우 더러벘벌섭터뻐      
산빠싸삽빠싸사쟈숩차우
우 더러벘벌섬터뻐 
삭빠싸삼빠싸사쟈숰차우
우해      멍 아
삼빠싸사박발따따삽빠싸사밧따삿빠싸사두
다살빠싸사탸우차   삿밪밧나댜  야  오
      밪밧나쌐샄도    

試しに入力例 3 に対して実行してみます.

30
40
50
6000

次のような出力になりました.

213
User time: 15.690 s

 TLE  遅っっっっっ.なんで  O(ABC)~(A, B, C\le 50) 通らないんですか.

仕方ないので少し改良します.このコードは  i, j, k に対する三重ループを回していましたが, i, j に対する二重ループのみ行ない, X/50 から  10i + 2j を引いた差が  0\le X/50 - (10i + 2j) \le C ならば答えを  +1 するという方針に切り替えます.

比較コマンド ㅈ を用いて, X/50 - (10i + 2j)\ge 0 かつ  C\ge X/50 - (10i + 2j) がどうかを調べていきます.

この操作を行なう部分コードは次の通りです.

                    도
                    솝 
                    쏩오섴더섭더썹뻐터벘벌   섴
삼빠싸사박발따따삽빠싸사밧따다살빠쌋사빠쌋삿타빠바쟈우차삳빠삿싿삳자초
                    툐벅벚   어       어

というわけで,これを使って先ほどのコードを書き直します.

방싹방싼방싿방발발박따따나쌀바쌈바쌉부
산빠싸삽빠싸사쟈우처삽빠타삼발밨타두쌐아
붓서숩떠희멍섴차숨져서써뻐섬써뻐석꺼삽두
뚜쏘뻐또벌벅서써뻐슙썹터벅샷뻐쑫썁뻐도숰
다살빠쌋사빠쌋삿타빠바쟈봊차솓삳주토벝
         더  오   차샄볼우

最大ケースに対して実行してみます.

50
50
50
6000

次のような出力になりました.

248
User time: 0.527 s

TL  2 sec. に無事間に合いました. AC 

Some Sums

 1\le i\le N のうち, A\le S(i)\le B \cdots(\ast) を満たす  i の総和を求める問題です.なお, S(i) i の各桁の和を表します.ここで, i = \overline{i_4 i_3 i_2 i_1 i_0} と表すことにします.上位の桁で余ったところには  0 を入れます.例えば  i = 314 の場合, i_4 = i_3 = 0, i_2 = 3, i_1 = 1, i_0 = 4 です.

複数のスタックを用いて,以下のように値を管理していきます.

stack (終声なし):  (\ast) が成立するかどうかを判定する場所

stack ㄱ, ㄴ, ㄹ: それぞれ  i, A, B の値を保持しておく場所

stack ㅁ: ある  i までの, (\ast) が成立するものの総和を保持しておく場所

stack ㅂ:  (\ast) が成立するかどうかを判定するために,値を一時的に保持しておく場所.

最終的にstackㅁにある値が出力すべき答えとなるはずです.

 j (0\le j\le 4) に対し, i_j = \lfloor i / 10^ j \rfloor \% 10 なので,ㄴ と ㄹ を用いて各桁の数字を求めておき,その和をとります.

ここまでの部分コードは以下の通りです.

빠박발따나박발따라싸빠박발따나박발따나박발따라싸빠박발따나박발따나박발따나박발따라쑤 
우                                        아
빠박발따나박발따나박발따나박발따나박발따라싸사다다다다

(少しずれているかもしれませんが, 2 行目の 아 は 1 行目一番右端の 쑤 の真下にあります.)

次に,先ほどの値  S(i) A 以上  B 以下であるか確認します.

 A, B の値はそれぞれ  ㄴ_0, ㄹ_0 なので,これらを ㅈ を用いて比較します.

 A\le S(i)\le B であれば, ㅁ_0 i を加えます.

これらをコードに書き下すと,以下のようにできます.

방싹방싼방쌀바쌈삭뺘숨차빠박발따라싸우
우       오 망희      아
빠박발따나박발따라싸빠박발따나박발따나박발따라싸빠박발따나박발따나박발따나박발따라쑤 
우       요                     터터벜벝석      아
빠박발따나박발따나박발따나박발따나박발따라싸사다다다다빠쌉산빠쌉삽쟈오차우
우       아                         오 아
살빠쌉사빠쌉삽자추
        삭빠쌈삼다                     오

 N \le 10^{4} なので,以下のような最大ケースが考えられます.

10000 2 30

これに対して実行すると...

48874001
User time: 6.854 s

 TLE  は?

書き換えるの嫌です.おわり*7

Card Game for Two

Alice も Bob も今あるカードの中で一番値の大きいものをとっていくのが最適なので,数列  A を降順ソートして  (奇数番目の総和) - (偶数番目の総和) が求める答えとなります.

複数のスタックを用いて,以下のように値を管理していきます.

stack (終声なし): 入力を受け取る場所

stack ㄱ, ㅅ: どちらも  N の値を保持しておく場所

stack ㄴ: ソート前(入力の状態)の数列  A を保持しておく場所

stack ㅁ: ソート済の数列  A を保持しておく場所

stack ㅈ: ソート済の数列  A を用いて答えを計算する場所.

ところで当然ソート関数は存在しないので実装しなければなりません.

再帰的な処理をするクイックソートマージソートは勿論,任意の 2 要素でスワップが必要なバブルソートですら使うことができません*8

なので,愚直な方法ですが配列内の最大値から順に取り出していき,新たな数列を作ることにします.具体的な実装は次の Python コードで表せます.

L = []
while len(A) != 0:
    m = A[0]
    B = []
    for i in range(1, len(A)):
        if A[i] < m:
            B.append(m)
            m = A[i]
        else:
            B.append(A[i])
    L.append(m)
    A = B

これは理学部情報科学科の講義「情報科学基礎実験」で課題として与えられた,「文字列のリストを受け取って昇順に整列されたリストを返す関数『 my-sort 』を Scheme で定義せよ」で書いた実装をほぼそのまま用いたものです.

計算量は  O(N^2) です. N\le 100 なのでたぶん間に合うでしょう.間に合わなかったら詰みですが...

ところで降順ソートをスタックとして管理するには一番奥の値が最小になる必要があるので,昇順ソートしてどんどんスタックに積んでいくという形をとります.なので先ほどの不等号の向きが A[i] < m になっています.

このソートを複数のスタックを用いて,以下のように値を管理していきます.

stack ㄴ: ソート前(入力の状態)の数列  A を保持してある場所

stack ㄷ: ソート中,  A の最小値になれなかった値を保持しておく場所

stack ㅁ: ソート中,  A の最小値となった値を順に保持しておく場所

stack ㅂ: ソート中,  A の各要素と,ある index までの最小値とを比較する場所

最終的に stack ㅁ に昇順ソートされた  A ができます.

ソート実装例

산쌈삭박밧나타뺘우차삼빠쌉산빠쌉삽쟈숨처산싿우
                  싿산쌈 우
  오                   어
두                  어
   밭받나투
발밨라타빠뺘뿌처 
밪로 쇽썬섣처  요

산쌈m = A[0] を, 삼빠쌉산빠쌉삽쟈if A[i] < m: を, 산싿B.append(A[i]) を, 삼싿산쌈B.append(m)m = A[i] を,それぞれ行なっています.

左下のブロックは L.append(m)A = B を行なっています.

これらを行なって,下から  2 行目の 처 で右方向に進むときソートが完了したということになるので,その値を足して引いて...とやって答えを求めれば OK です.

実装例

방빠쌋싹삭빠뺘붕처다빠산쌈삭박밧나타뺘우차삼빠쌉산빠쌉삽쟈숨처산싿우
 빠쏬  타오쑨                     싿산쌈 우
     토벅벋     오                   어
두                  어              아
   밭받나투    망희멍         섲썾
발밨라타빠뺘뿌처쌎삿뺘솢차삼쌎샂다삿발밨타타빠추 
밪로 쇽썬섣처  요오    터너벚벋섯터섲썾섬

 1\le N, a_i\le 100 なので次のような最大ケースが考えられます.

100
57 57 5 60 76 46 32 76 2 92 21 51 6 85 48 25 78 77 72 76 87 90 49 65 42 57 9 96 34 55 83 95 74 99 29 47 89 72 38 59 81 1 64 6 44 21 80 52 93 56 7 58 93 32 64 72 47 63 8 46 11 6 37 77 18 9 11 5 60 95 77 25 45 43 48 2 22 15 50 49 58 86 47 41 76 36 88 23 39 100 88 62 52 91 12 81 28 82 8 19

これらに対して先ほどのコードを実行すると,次のように表示されました.

59
User time: 0.847 s

 AC 

Kagami Mochi

数列  d 中の値の種類数を求める問題です. d をソートして種類数を求めていきます.

ソート済の配列に対し,隣り合った要素が異なる場合のみ ans に  +1 すればよいです.

実装例

방빠쌋싹삭빠뺘붕처다빠산쌈삭박밧나타뺘우차삼빠쌉산빠쌉삽쟈숨처산싿우
 빠쏬  타오쑨                     싿산쌈 우
     토벅벋     오                   어
두                  어              아
   밭받나투             샂망희
발밨라타빠뺘뿌처발밨타쌎삼쌉삿반반나타빠추  듀터벜벝섲
밪로 쇽썬섣처  요          삼빠쌉삽파자 추초
                  노번벅섯썹섬   어

Otoshidama

 N\le2000 O(N^2) は無理.

白昼夢 / Daydream

 |S|\le10^5 O(|S|) は無理.

Traveling

 N\le10^5 O(N) は無理.

まとめ

いかがだったでしょうか?*9

Aheui を書く上で一番大変なのはデバッグでした.まずはこのように下書きをしたあと,AVIS を使ってコードを書いて実行しつつミスを直していき,最後に TIO で大きいケースの実行をしていました.

f:id:m_ast:20191210171004j:plain

AVISは実行順を視覚的に追っていってくれるので本当に頼りになりました.ありがとう AVIS .

おわりに

まずは私をこの言語に出会わせてくれた TSG に感謝を.おかげで Advent Calendar を埋めることができました.

AVISを作った @disjukr さんには感謝してもしきれません*10

いつか Aheui を書きたいと思ってくれた誰かがこのページを参考にしてくれればいいなぁ.

明日 12 日は 犬 くんの記事です.きっとめちゃくちゃ面白い記事を書いてくれているに違いない!

*1:ahi と読みます.

*2:終声は存在しない場合もある

*3:発音のイメージは某太鼓のゲームの「カッ」

*4:口を開けて「お」と発音するとそれっぽくなります

*5:例: uo → wo

*6: 4-3, 2/2 など

*7:気が向いたときに  O(N / 10) で書き直そうと思います...

*8:ㅍは先頭 2 つの要素しかスワップできないため

*9:これ言ってみたかった

*10:Twitter でフォローもしてくれた.