読者です 読者をやめる 読者になる 読者になる

KMC活動ブログ

京大マイコンクラブの活動の様子を紹介します!!

Pietで競プロしたい

この記事は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は単純明快な言語なので比較的簡単に書けます。

  1. pietのインタプリタをまず書く

  2. pietの画像ソースコードを読み込んでおく

  3. 読み込んだデータをインタプリタが実行しやすいように前計算しておく

  4. データをインタプリタに埋め込む

という形で実装しました。

コンパイラソースコード下の問題の提出コードの下にコメントで書いているので、興味があればそちらを参照してください。


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++なんか目じゃないですね!

f:id:kmc-log:20151223125153p:plain

分かりやすいように、メモをつけてみました。

f:id:kmc-log:20151223170828p:plain

このコードをc++コンパイルして提出したソースコードはこっちです
(故意に少しカオスなコードにしています)。
Submission #596428 - AtCoder Beginner Contest 007 | AtCoder

拙いですが*3コンパイラソースコードも提出コードの下の方にコメントで書いてあります。

pietでちゃんとACしてます。これで、絵で楽しく競プロをすることができました!

最後に

確かに手の込んだpietプログラムを人力で描くのは骨が折れますが*4、最近では優秀なpietのエディタPidet(KMC製)やpietコードの生成支援ソフト(KMC製)も多く出てきてpietの開発環境は大幅に向上しています。

しかし何といっても、そこには絵という美しいものでプログラミングができるというロマンがあります。このロマンがpietの魅力でしょう。

文字なんてよく分からないものを捨てて、息抜きに競技プログラミングにロマンを追い求めてみては?

KMCM(宣伝)

京大マイコンクラブではロマンを追い求めたい新入部員を募集しています。年齢や所属、国籍や宗教その他諸々に関する制約はありません。詳しくは入部案内を見て下さい。

www.kmc.gr.jp

これで私が知る限りではKMC Advent Calendar 2015は終わりです。
ありがとうございました。

*1:私はbase64と名乗っていますがbase64についてはあまり詳しくないです。すみません。

*2:京大工学部情報学科1回生です。優しくしてね。

*3:コードが読みにくいだけでなく、バグらせててin(c),out(c)の処理がcharの範囲でしかできないです。

*4:pietではスタックに変数を積みすぎると、一部の操作がスタックの要素数に比例する計算量なので、一部というか結構な数の問題が解けないかも。