Pietで競プロしたい - KMC活動ブログ

この記事はKMCID:base64 *1 *2による KMC Advent Calendar 2015 の25日目の記事です。

www.adventar.org

昨日の記事はhakurin君によるガルパンはいいぞ。液タブもいいぞ。そんなクリスマスイブでした。液タブ便利そうですね。あと魔理沙かわいい。

hakurin776.hateblo.jp

PietにおいてKMCは日本最先端（たぶん）

最近KMCではpietという、ドット絵でプログラミングができる難解プログラミング言語が流行っています。そのことはKMCアドベントカレンダーのpietに関する記事の多さからも明らかでしょう。

試しに「piet」でGoogle検索をしてみると、KMC関連のページが多くヒットします。KMCでのpiet活動はmurataさんによる18日目の記事 KMCとPiet,そして最強のPietの為にdllを動的にC#で読みこむ話でまとめられているので省略しますが、

KMCのpiet力はとにかくすごい‼（小並感）。

pietでクリスマスをつよく生きる

本題に入る前に、今日はクリスマスらしいです。カップルからすれば絶好のデート日和。その光景を目の当たりにすると思わず、「リア充爆発しろ」と言いたくなりますね。

そんな、皆さんが日ごろから願っていることを叶えるプログラムをpietで描いてきました。それがこちらです。

f:id:kmc-log:20151223125100j:plain

Pietは絵でプログラミングするのですが、文字も絵のうちなので、思ったことをそのまま描く（そしてごにょごにょする）だけでプログラムができてしまいます。

すばらしいですね！

このプログラムに「リア充」を入力して実行すると、
なんと！リア充が爆発（的に増加）します！
具体的には1384万5841回「リア充」と出力します。

見た目にも分かりやすくやりたいことが描けるところがpietのすばらしいところですね。

Pietで競技プログラミング

本題に入ります。私はKMCでpietのほかに競技プログラミングの活動に参加しているのですが、そこに致命的な問題があるのです。

面白いプログラミング言語であるpietが競技プログラミングコンテストで一切使用できないのです。

これを由々しき事態だと感じた私は、pietでウハウハな競プロライフを送るために、pietからc++に変換するコンパイラ(っぽいもの)を書いて実際に問題を解いてきました。

コンパイラと言っても、pietは単純明快な言語なので比較的簡単に書けます。

pietのインタプリタをまず書く
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;
}