この記事はKMCID:base64*1*2による KMC Advent Calendar 2015 の25日目の記事です。
昨日の記事はhakurin君によるガルパンはいいぞ。液タブもいいぞ。そんなクリスマスイブでした。液タブ便利そうですね。あと魔理沙かわいい。
PietにおいてKMCは日本最先端(たぶん)
最近KMCではpietという、ドット絵でプログラミングができる難解プログラミング言語が流行っています。そのことはKMCアドベントカレンダーのpietに関する記事の多さからも明らかでしょう。
試しに「piet」でGoogle検索をしてみると、KMC関連のページが多くヒットします。KMCでのpiet活動はmurataさんによる18日目の記事 KMCとPiet,そして最強のPietの為にdllを動的にC#で読みこむ話 でまとめられているので省略しますが、
KMCのpiet力はとにかくすごい‼(小並感)。
pietでクリスマスをつよく生きる
本題に入る前に、今日はクリスマスらしいです。カップルからすれば絶好のデート日和。その光景を目の当たりにすると思わず、「リア充爆発しろ」と言いたくなりますね。
そんな、皆さんが日ごろから願っていることを叶えるプログラムをpietで描いてきました。それがこちらです。
Pietは絵でプログラミングするのですが、文字も絵のうちなので、思ったことをそのまま描く(そしてごにょごにょする)だけでプログラムができてしまいます。
すばらしいですね!
このプログラムに「リア充」を入力して実行すると、
なんと!リア充が爆発(的に増加)します!
具体的には1384万5841回「リア充」と出力します。
見た目にも分かりやすくやりたいことが描けるところがpietのすばらしいところですね。
Pietで競技プログラミング
本題に入ります。私はKMCでpietのほかに競技プログラミングの活動に参加しているのですが、そこに致命的な問題があるのです。
面白いプログラミング言語であるpietが競技プログラミングコンテストで一切使用できないのです。
これを由々しき事態だと感じた私は、pietでウハウハな競プロライフを送るために、pietからc++に変換するコンパイラ(っぽいもの)を書いて実際に問題を解いてきました。
コンパイラと言っても、pietは単純明快な言語なので比較的簡単に書けます。
という形で実装しました。
コンパイラのソースコードは下の問題の提出コードの下にコメントで書いているので、興味があればそちらを参照してください。
pietで解いてきた問題はABC第7回のD問題「禁止された数字」です。
D: 禁止された数字 - AtCoder Beginner Contest 007 | AtCoder
問題を簡単に紹介すると、10の18乗以下のA,B二つの整数が入力として与えられて、A以上B以下の数のうちで4または9を含む数(以後「禁止された数」と呼ぶ)がいくつあるかを答える問題です。高校の数学の問題にもありそうですね。
問題の解説はこの記事の目的からそれるので簡単にします。 この問題ではA,Bが10の18乗以下と非常に大きいので、桁dpを用いて数え上げます。
c++でのコードはこんな感じになります。
#include <iostream> #include <vector> #include <algorithm> #include <string> using namespace std; typedef long long ll; string A,B; //solve(s) := 0からsまでの間にある禁止された数の個数 ll solve(string s){ vector<ll> o(s.size()+1,0); // o[i] := sの上からi桁でsより小さい、禁止されていない数の個数 vector<ll> uo(s.size()+1,1);//uo[i] := sの上からi桁でsに等しい 、禁止されていない数の個数 for(int i=0;i<s.size();i++){ ll num=s[i]-'0'; //num := sの上からi+1桁目の数 o[i+1] = o[i]*8 + uo[i]*(num-(num>4)); uo[i+1] = uo[i]*(num!=4 && num!=9); } return stoll(s)-(o[s.size()]+uo[s.size()]); } int main(){ cin >> A >> B; A=to_string(stoll(A)-1); cout << solve(B)-solve(A) << endl; return 0; }
このアルゴリズムをpietで描くと下のようになります。 見た目の芸術性ではc++なんか目じゃないですね!
分かりやすいように、メモをつけてみました。
このコードをc++にコンパイルして提出したソースコードはこっちです
(故意に少しカオスなコードにしています)。
Submission #596428 - AtCoder Beginner Contest 007 | AtCoder
拙いですが*3、コンパイラのソースコードも提出コードの下の方にコメントで書いてあります。
pietでちゃんとACしてます。これで、絵で楽しく競プロをすることができました!
最後に
確かに手の込んだpietプログラムを人力で描くのは骨が折れますが*4、最近では優秀なpietのエディタ(KMC製)やpietコードの生成支援ソフト(KMC製)も多く出てきてpietの開発環境は大幅に向上しています。
しかし何といっても、そこには絵という美しいものでプログラミングができるというロマンがあります。このロマンがpietの魅力でしょう。
文字なんてよく分からないものを捨てて、息抜きに競技プログラミングにロマンを追い求めてみては?
KMCM(宣伝)
京大マイコンクラブではロマンを追い求めたい新入部員を募集しています。年齢や所属、国籍や宗教その他諸々に関する制約はありません。詳しくは入部案内を見て下さい。
これで私が知る限りではKMC Advent Calendar 2015は終わりです。
ありがとうございました。