AtCoder に登録したら解くべき精選過去問 10 問を Whitespace で解いてみた

はじめに

drken さんの 精選過去問 10 問 をジョーク言語の Whitespace で解いてみました．コンテストページはこちらです．

同じく難解言語である Piet で ABS を解いた方（basemusi さん）に触発されてやってしまいました．

追記

2018/3/24 14時頃：提出コードへのリンクを貼りました．ソースが読めないと盛り上がっていますが，Codeforces で Hack 対策にこれを使うとおそらく規約¹に引っかかるので，しないようにしましょうね．

対象

各種主流言語でのコーディングに疲れてきて気分転換をしたい方，ジョーク言語で遊んでみたい方， 人とは違ったことをして注目を集めてみたい方．

命令が特徴的な言語では，それに応じた考察をする²ことで，普段とは違った解き方が見えてきて楽しいかもしれません．

TL; DR

実質アセンブラ

Whitespace とは？

Edwin Brady 氏と Chris Morris 氏によって設計された言語で，2003 年のエイプリルフールに発表された言語です³．名前の通り，ソースコードは以下の三つの空白文字から成ります．

• （スペース，ASCII 32）
• （水平タブ，ASCII 9）
• （改行文字，ASCII 10）⁴

これらの文字の組み合わせによって各種命令を表現します．よくある Brainf*ck の派生劣化言語ではありません．スタックとヒープを用いてコーディングを行います．ここでいうヒープはフィボナッチヒープのような意味でのヒープではなく，ヒープ領域の意味と思われます．好きに使ってよい配列のようなものと思っておいて問題ないはずです．

また，以下の説明においては（文字通り）可読性のためにスペースを S，水平タブを T，改行文字（linefeed）を L で表すことにします（言語のアイデンティティこわれる）．

命令について⁵

Whitespace の各命令は IMP（Instruction Modification Parameter）と呼ばれる文字列で始まります．これにより命令がカテゴリ分けされています．

IMP	カテゴリ
S	スタック操作
TS	算術演算
TT	ヒープ操作
TL	入出力
L	フロー制御

IMP に続く文字列によって細かい命令を表現します．命令が引数をとる場合はコマンドの直後に整数リテラルを書きます．

整数リテラル

2進数に基づく表現をしますが，2の補数表現は用いられません．符号・絶対値表現を用います．S が 0 に，T が 1 に対応しており，L で終端を表します（任意ビット長の整数を用いることができます）．たとえば +4 は STSSL，-7 は TTTTL となります．また，浮動小数点数や実数は規定されていません．

スタック操作

コマンド	引数	命令の内容
S S	数値	スタックに与えられた数値を積む
S LS	なし	スタックの先頭と同じ値をさらにスタックに積む
S LT	なし	スタックの先頭要素と次の要素を入れ替える
S LL	なし	スタックの先頭要素を取り除く

ここで，スタックの先頭は後に入れられた要素（先に取り除かれる要素）（C++ でいうところの std::stack::top() で得られる要素）を指します．

算術演算

コマンド	引数	命令の内容
TS SS	なし	加算
TS ST	なし	減算
TS SL	なし	乗算
TS TS	なし	除算
TS TT	なし	剰余算

スタックに積まれた二つの数について演算を行います．先に積まれた要素が左オペランド，次の要素が右オペランドになります．演算結果がスタックに積まれます．

ヒープ操作

コマンド	引数	命令の内容
TT S	なし	格納
TT T	なし	取り出し

格納の際は，まず格納先アドレスを，次に格納したい値をスタックに積み，この命令を呼びます．取り出しの際は，取り出したいアドレスをスタックに積み，この命令を呼びます（取り出された値はスタックに積まれます）．

入出力

コマンド	引数	命令の内容
TL SS	なし	スタックの先頭要素を文字として出力
TL ST	なし	スタックの先頭要素を整数として出力
TL TS	なし	スタックの先頭要素が指すアドレスへ文字として入力を受け取る
TL TT	なし	スタックの先頭要素が指すアドレスへ整数として入力を受け取る

フロー制御

各種ジャンプやラベル付け，関数呼び出しなどを行うことができます．ラベルは整数リテラルを用います．また，ラベルの名前空間は一つのみであり，すべてのラベルは unique である必要があります．

コマンド	引数	命令の内容
L SS	ラベル	与えられたラベルを命令の置かれた場所に付ける
L ST	ラベル	関数呼び出し
L SL	ラベル	ラベルが示す先に（以下同様）無条件ジャンプ
L TS	ラベル	スタックの先頭要素が 0 ならジャンプ
L TT	ラベル	スタックの先頭要素が負ならジャンプ
L TL	なし	関数を終了して caller の元へ帰る
L LL	なし	プログラムを終了する

以上が Whitespace で使える命令列になります．

いざ出陣

現状，AtCoder では Whitespace を用いることができません（えーん）．そのため，今回は C++ でインタプリタを実装し，Whitespace のソースをそこに埋め込む形で提出しました．

これを書いている途中にインタプリタの実装ミスに気づき，「Whitespace らしき何か」を提出していたことが判明したので，正しく直して再提出しました．まだ実装ミスがあったり仕様の勘違いがあるかもしれません．

解法

0 問目：PracticeA - はじめてのあっとこーだー（Welcome to AtCoder）

整数 $a$，$b$，$c$ および文字列 $s$ が与えられるので $a+b+c$，' '，$s$，'\n' を出力します．

Brainf*ck とは違い，整数の入出力で苦しむことはありません．やるだけです．

practice_1.ws
   
	
		   	
	
		   
			   	
				      
	
		   
				   	
 	   
	
	    	     
	
  
   
   
	
	    
			 
 	
     	 	 
 
		  	
		 

提出コード

1 問目：ABC086A - Product

整数 $a$，$b$ が与えられるので $a\times b$ の偶奇を判定します．

「$a$ が偶数なら 'Even'」「$b$ が偶数なら 'Even'」「それ以外なら 'Odd'」という方針でもよいですが，面倒なので指示された通り掛け算をすればよいです．

abc086_a.ws
   
	
		   	
	
		   
			   	
				  
   	 
	 		
	  
   	 	 
   		  	  
   		  	  
   	  				
	
  	
  	
  	
  



   
   	 	 
   		 			 
   		  	 	
   			 		 
   	   	 	
	
  	
  	
  	
  	
  

提出コード

2 問目：ABC081A - Placing Marbles

文字 $s_1s_2s_3$ が与えられるので，それらに含まれる '1' の個数をカウントします．整数として受け取って 9 で割ったあまりを出力してもよいですが，甘えのような気がしたので指示通りやります．3 回のループを回せばよいです．

abc081_a.ws
   
   
		   			

   
   	
	
	    	
			   		    
	  	
	  	
   
   
			   	
	   		 
   	
   	
	    
 
		 
   
				
 	   	 	 
	
  

提出コード

3 問目：ABC081B - Shift only

$N$ 個の整数 $A_1$ から $A_N$ が与えられるので，それらの二進数表示の trailing zero の最小個数を求めます．

これを解くにあたっては $O(1)$ の空間さえあれば十分です．すなわち「今の入力」と「今までの trailing zero の最小個数」です．個数を数える関数と最小値を更新する関数を作りました．最初の難関です．

今回のようにループ中でループ変数を使用する必要がないときは，ループ変数の正負をあらかじめ逆転しておくと += 1 と jump if neg だけでループさせることができて楽です．⁶

abc081_b.ws
   
   	 	   
		    	
	
		   	
			  		
	  

   
   	
	
		   	
			
 	 	

 	 	  
   	
	    
 
		 
   
				
 	   	 	 
	
  



   	
   
 
	
   	 
 
    	
	      	 
	 		
	  		
   	 
	 	  
	   	
	    
	
 
 	 

   		
 


	

   	  
 
    
				  	
		 	 	
 


	

   	 	
   
 
			 
	

提出コード

4 問目：ABC087B - Coins

整数 $A$，$B$，$C$，$X$ が与えられるので，$500a+100b+50c=X$ を満たす自然数解 $(a, b, c)$ の個数を数えます（$0\in\mathbb{N}$）． $a\le A$，$b\le B$，$c\le C$ です．

三重ループを書きます．ループの最も内側で判定用の関数を呼び出します．スタックに返り値を積むなどして caller 側で個数を数えるのが綺麗なのかもしれませんが，呼び出した関数側で処理してしまいました．

abc087_b.ws
   
   
	
		   	
	
		   	 
	
		   		
	
		   		
   		
			   		  	 
	 	 		    	  
   
					    	 	
   	
					    		 
   	 
					 
   

 	 	  
   		 
			   	
	  	 
    		 
 
			 
		 	

 
 

   	
   		 
   	 
					    	 	
			   	
	  	 
    	 	
 
			 
		 	 

 
 

   	 
   	 	
   	
					    	  
			   	
	  	 
    	  
 
			 
		 		

 
 

   		
	
 	   	 	 
	
  



   	  
   		
			   		 
				  	   	 
   	 	
				  
	  	   	 	 
   	  
				  
	  	
	  	 	

	

   	 	
   	
	   
	

提出コード

5 問目：ABC083B - Some Sums

整数 $N$，$A$，$B$ が与えられるので，$1$ 以上 $N$ 以下の整数のうちで 10 進法での桁和が $A$ 以上 $B$ 以下であるものの個数を数えます．

ループを回して関数を呼び出して出力します．この辺りから虚無を感じ始めてきます．

abc083_b.ws
   
   
	
		   	
	
		   	 
	
		   
			
   
 
 
 	 	 

 	 	 	
   	
	  	 
 
	  	

 
 

   	
 

	
 	   	 	 
	
  



   	 
   		
   
		 
   		
 
    	 	 
	 		   		
				      		
 
			    	 	 
	 	  
 
	  	  

 
 		

   	  
 


	

   	 	
   		
			   	
				  	
		 		 
   		
			   	 
			 
		  	
		 		 
 
    		
 
			  
	   		
				    
	
   		 

	

提出コード

6 問目：ABC088B - Card Game for Two

$N$ 個の整数 $a_1$ から $a_N$ があり，値の大きい方から交互に二人で取り合うことを考えます．このとき，両者の得た整数の合計の差を求めます．

ソートして符号を入れ替えつつ足していけばよいのですが，Whitespace でソートを実装する気にはならなかったので，考察をします．

$N$ 個の整数に重複がある場合を考えます．同じ整数が二つあった場合，両者は交互に取り合うことから，差としては無視することができます．すなわち，各整数の個数の偶奇さえ持っておけばよいことになります．

$a_i$ の上限が小さいため，配列で管理することができます．具体的には，各 $i$ に対して count[a_i] を count[a_i] = 1-count[a_i] で更新します．

入力を受け取った後は，count[100] から降順に見ていき，count[j] が 1 なら答えに j を足し引きします（符号は別でもっておいて交互に変える）．

これで，$O(N+\max a_i)$ で解けました．

abc088_b.ws
   		  	  

   
 
    
		    	
	  	 
 
	  	

 
 

   	
 

   
   
	
		   
				  	
   	 
   
	
		   
			 
 			   	
 
		  			    	
	    
 
		 	 
 

   
   
		    		  	 	
   	
		    		  	  

   		
 
 			
	  	  
 
    		  	 	
				  
   
				      
 
			    		  	 	
   		  	 	
			  		
	  
		 
   	  
   	
	  	 
 
	  	 	

 
 		

   	 	
 

   
				
 	   	 	 
	
  

提出コード

7 問目：ABC085B - Kagami Mochi

$N$ 個の整数 $d_1$ から $d_N$ のうちで unique なものの個数を数えます．⁷

実質的に 6 問目と同じで，個数を数えていきます．今回は偶奇ではなく OR で更新します．すなわち，count[a_i] = 1 と更新して，count[j] が 1 なら答えに 1 足します．というか直接 count[j] を足してもいいです．簡単ですね．

abc085_b.ws
   		  	  

   
 
    
		    	
	  	 
 
	  	

 
 

   	
 

   
   
	
		   
				  	
   	 
   
	
		   
			   	
		    	
	    
 
		 	 
 

   
   
		    		  	  

   		
 
 			   
				      
 
			    	
	  	 
 
	  	  

 
 		

   	  
 

   
				
 	   	 	 
	
  

提出コード

8 問目：ABC085C - Otoshidama

整数 $N$ と $Y$ が与えられるので，

\left\{\begin{array}{l}
x + y + z = N \\
10000x + 5000y + 1000z = Y
\end{array}\right.

の自然数解（$0\in\mathbb{N}$）をひとつ出力します．存在しなければ '-1 -1 -1' を出力します．

$Y$ が 1000 の倍数であることになっているので，Y = Y/1000 - N としておき，x と y について二重ループを回して Y-9*x-4*y を 0 たらしめる x と y が見つかれば，それらと N-x-y を，そうでなければ -1 たちを出力します．

多重ループを回しつつ，ループ変数を使おうとすると（たぶん）スタックだけでは事足りなくなるので大変ですね．

abc085_c.ws
   
	
		   	
   	
	
		   	
			   					 	   
	 	    
				  			    	 
   
					    		
   
		 
   

 	 		
   		
			   	
	  	 
    		
 
			 
		 	

 
 

   	
   	 
			   	
	  	 
    	 
 
			 
		 	 
   		
   
			   	 
				  			 
 
 

   	 
  		
	
 	   	     
	
    		
	
 	   	     
	
    		
	
 	   	 	 
	
  



   		
   	
			   	  	
   	 
				  
   	  
   		
				  
	   	  	
	  	  

	

   	  
   	 
				
 	   	     
	
     		
				
 	   	     
	
     
			   	 
			   		
				   	  		
 	   	 	 
	
  

提出コード

9 問目：ABC049C - 白昼夢 / Daydream

正規表現で殴ります（できたらなあ）．

arc065_a.ws
   	

   
 
 	
	  
 			   	 	 
	  	
	  	
   	
	   
 
 

   	
   	
	  	
   	 

 	 	 	
 
 
	  	  

 
 	 

   		
   	 	 
   	  				
   	  			 
	
  	
  	
  



   	  
   	 	 
   	 	  		
   	   	 	
   	 		  	
	
  	
  	
  	
  



   	 	
 
    			  	 

 	 	 	 

	  		 
   	
	  	 
    		  	 	

 	 	 	 

	  		
   	
	  	 
    		 		 	

 	 	 	 

		 			
 
    			  		

 	 	 	 

	  		

 
 	  	

   		 
 
    		 		 	

 	 	 	 

	  	   

   			
   	
	  	 
    		    	

 	 	 	 

	  		
   	
	  	 
    		  	 	

 	 	 	 

	  		
   	
	  	 
    			  	 

 	 	 	 

	  		
   	
	  	 
    		  	  

 	 	 	 

	  		
   	
	  	
	

   	   
 
    		  	 	

 	 	 	 

	  		
   	
	  	 
    			  		

 	 	 	 

	  		

   	  	
   	
	  	 
    		    	

 	 	 	 

	  		
   	
	  	 
    			  	 

 	 	 	 

	  		
   	
	  	 
    		  	 	

 	 	 	 

	  		
   	
	  	
	

   	 	 
 
					  	
	  	 		
   

	

   	 		
  		

	

提出コード

10 問目：ABC086C - Traveling

たぶん 9 問目の方がつらいです．これも $O(1)$ の空間があれば十分ですね．

t，x，y および前の値との差分の絶対値 dt，dx，dy を持っておきます．dt < dx + dy または (dt+dx+dy)%2 > 0 になることがあれば 'No'，最後まで耐え切れば 'Yes' です．大文字小文字に気を取られて改行を出力し忘れて WA，なんてことがないようにしましょうね．

ところで，どうやら dx などを考慮しなくても AC できる嘘解法があるようです．あと，$i=1$ の部分しか判定しない（と思われる）バグを提出したところ WA のケースが一つだけだったので怖かったです．

arc089_a.ws
   
   
   
	
		   
				  	   
   
		    	
   
		    	 
   
		    		
   
		    	  
   
		    	 	
   
		 
   
   		
	
		   		
			 
    
				  	   		
 
			    
 
			    	  
	
		   	  
			 
    	
				  	
 	 	 
   	  
 
			    	
 
			    	 	
	
		   	 	
			 
    	 
				  	
 	 	 
   	 	
 
			    	 
 
			    	  
			   	 	
				    
    		
			 
		  	
		 	
   		
				      	
	      	 
	 		
	  	
   	
	    
 
		 
   	 	 
   			  		
   		  	 	
   	 		  	
	
  	
  	
  	
  



   	
   	 	 
   		 				
   	  			 
	
  	
  	
  



   	 
 
 
		 		

	

   		
  		
	  

	

提出コード

あとがき

Whitespace を書いていたはずなのに，コーディングフェイズではほとんど印字可能文字ばかり入力していました．アセンブラ風の代替言語を書いて，それを Whitespace に変換するスクリプト（Bash）におまかせしました．

そのスクリプトにバグがあったり，代替言語でミスを埋め込んだり，散々でした（罰が当たったわけですね）．

あと Whitespace のソースを貼る際に通常の ``` で囲む方法ではタブがスペースに展開されたり印字可能文字のない行の空白が省かれたりしてつらかったです．結局 HTML を直接書きました．いい方法があったら教えてほしいですね．

1. Can-do's and Can't-do's の 4. ↩

2. n57577 ↩

3. https://esolangs.org/wiki/Whitespace やそのリンク先が参考になります． ↩

4. 実際には水平タブや改行文字を入力しているのに，ここでの表示では同じになってしまっていてつらい．いい方法があれば教えてほしいです．...と思ったけどプレビューとは表示が違っていて困惑． ↩

5. https://hackage.haskell.org/package/whitespace-0.4/src/docs/tutorial.html や http://web.archive.org/web/20150618184706/http://compsoc.dur.ac.uk/whitespace/tutorial.php など． ↩

6. Human Resource Machine というゲームで得た知見です．常識なのかもしれません． ↩

7. n575 ↩

8. Atcoder ではなくて AtCoder です，間違えないようにしましょうね．WhiteSpace ではなくて Whitespace だと思うのですが，既存のタグに合わせてしまいました（よわい）．
   文字列を後ろから読んでいって 'maerd'，'remaerd'，'esare'，'resare' のいずれにもマッチしない部分があれば 'NO'，先頭までマッチさせ続けられれば 'YES' を出力します．case-insensitive な人間⁸にならないように注意しましょう． ↩