Help us understand the problem. What is going on with this article?

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

競技プロデル,題して競プロ 1
2019/12/18 更新:#8,#10がコンパイル版で動かなかった件について追記

まえがき

プロデル Advent Calendar 2019 15日目 の記事です.

今回のアドカレで日本語プログラミング言語「プロデル」を知りました.
プロデルとは,日本語としてかなり自然な表記ができることが特徴のプログラミング言語です.
教育目的であることが多い他の日本語プログラミング言語とは違い汎用ソフトウェア開発を目指して開発されており,オブジェクト指向を取り入れたり2ライブラリを豊富にしているなど実用性にも重きを置かれています.

使い心地を確かめるべくAtCoderの入門問題を解いていき,基本的な使い方を解説していきたいと思います.

実行環境

◆動作環境情報◆
プロデル 1.6.985
Windows 10(64)
メモリ:7.90 GB

公式サイトからインストーラ一つで簡単にセットアップできました.
予測補完やデバッガ,GUIの作成機能と高機能なIDEごとインストールされるので非常に使いやすいです.

このエディタ上でそのまま実行することもできますが,コンソールからの起動もできます.
AtCoderのジャッジシステムにはプロデルが導入されていない3ので手元環境で動作確認をしていきます.

以下の形式でテストケースを実行し,正誤を測ります.(コマンド内容については以前の記事も参照のこと)

wsl time pconsole.exe source.rdr < in.txt > out.txt

0. PracticeA - Welcome to AtCoder

残念ながらQiitaではプロデルはじめ日本語プログラミング言語のシンタックスハイライトに対応していないため,プロデルデザイナにおける表示のスクリーンショットを添付します.

image.png

おまけ:テキストでも貼っておきます

0.rdr
0.rdr
コンソールから受け取って,入力aとする
コンソールから受け取って,入力bcとする
コンソールから受け取って,入力textとする
分割bcは,入力bcを「 」で区切ったもの
「[入力a+分割bc(1)+分割bc(2)] [入力text]」をコンソールに表示して改行する

splitに相当するものは文字列の区切ったもの手順となります.
埋め込み文字列のエスケープは[]ですね.
文字列→数値へは暗黙の型変換をしてくれているようです.数値の足し算は,文字列の結合にはが使われます.

1. ABC 086 A - Product

image.png

1.rdr
1.rdr
abは,コンソールから受け取ったものを「 」で区切ったもの
もしab(1)%2が0またはab(2)%2が0ならば
  「Even」をコンソールに表示して改行
そうでなければ
  「Odd」をコンソールに表示して改行
もし終わり

配列の要素へのアクセスは〈配列〉(n)となります.配列などのインデックスアクセスは1-indexedなので注意が必要です.
なお,ソースコード中の英数字は全角半角・大文字小文字は区別されません.※参考

2. ABC 081 A - Placing Marbles

image.png

コメントアウト部分はループによる解法です.数えたもの手順があるので1行で書けましたね.

2.rdr
2.rdr
コンソールから受け取ったものから「1」を数えたものをコンソールに表示して改行

/*
入力は,コンソールから受け取ったもの
結果は,0
入力の文字数回iにカウントしながら繰り返す
  もし,入力のi文字目が「1」ならば
    結果に1を足す
  もし終わり
繰り返し終わり
結果をコンソールに表示して改行
*/

3. ABC 081 B - Shift Only

image.png

3.rdr
3.rdr
入力nは,コンソールから受け取ったもの
入力aは,コンソールから受け取ったものを「 」で区切ったもの
結果は,0
((入力aすべてを2で割ったあまり)の合計が0より大きい)になるまで繰り返す
  入力aは,入力aすべてを2で割ったもの
  結果に1を足す
繰り返し終わり
結果をコンソールに表示する

配列の各要素に対する操作(e.g. Pythonではmap)は〈配列〉すべてを〈操作し〉たもののように書けます

4. ABC 087 B - Coins

image.png

4.rdr
4.rdr
コンソールから受け取ってAとする
コンソールから受け取ってBとする
コンソールから受け取ってCとする
コンソールから受け取ってXとする
結果は,0
(0~A)をiへそれぞれ繰り返す
  (0~B)をjへそれぞれ繰り返す
    (0~C)をkへそれぞれ繰り返す
      もし500×i+100×j+50×k=Xならば結果に1を足す
    繰り返し終わり
  繰り返し終わり
繰り返し終わり
結果をコンソールに表示

0から始めたループを書くときは〈値〉回〈変数〉にカウントしながら繰り返すよりも(0~N)を〈変数〉へそれぞれ繰り返すと書いた方が便利です(前者は1スタートなので).

5. ABC 083 B - Some Sums

image.png

5.rdr
5.rdr
NABは,コンソールから受け取ったものを「 」で区切ったもの
Nは,NAB(1)
Aは,NAB(2)
Bは,NAB(3)
結果は,0
N回,iにカウントしながら繰り返す
  各桁和は,0
  (1~「[i]」の文字数)をけたへそれぞれ繰り返す
    各桁和に「[i]」のけた文字目を足す
  繰り返し終わり
  もし各桁和≧Aかつ各桁和≦Bならば結果にiを足す
繰り返し終わり
結果をコンソールに表示して改行

ASCII文字が基本のプログラミング言語では大なりイコール,小なりイコールが>=だったか=>だったか間違えがちというのがあるあるですが,プロデルではそのままなので間違えることもありません.

6. ABC 088 B - Card Game for Two

image.png

6.rdr
6.rdr
コンソールから受け取ってNとする
Aたちは,コンソールから受け取ったものを「 」で区切ったもの
Aたちを大きい順に並び替える
アリスは,0
ボブは,0
N回,iにカウントしながら繰り返す
  もしiを2で割ったあまりが1ならば
    アリスにAたち(i)を足す
  そうでなければ
    ボブにAたち(i)を足す
  もし終わり
繰り返し終わり
アリス-ボブをコンソールに表示

引き算は-またはであり,ではないことに注意が必要です.(日本語入力で初めに入力されるのは「ー」(長音符)だったため一度バグらせました)

7. ABC 085 B - Kagami Mochi

image.png

7.rdr
7.rdr
コンソールから受け取ってNとする
辞書を作って集合とする
N回繰り返す
  コンソールから受け取ってdとする
  集合のdは,1
繰り返し終わり
集合の個数をコンソールに表示する

種類(クラスに相当)のインスタンス作成は〈種類〉を作って〈変数〉とするなどのように書きます.
集合を表す種類は見つかりませんでしたが,連想配列に相当する辞書があるためこれで代用可能です.

8. ABC 085 C - Otoshidama

image.png

8.rdr
8.rdr
NYは,コンソールから受け取ったものを「 」で区切ったもの
Nは,NY(1)
Yは,NY(2)
見つかったは,×
(0~N)を一万円へそれぞれ繰り返す
  もし見つかったならば繰り返しを抜ける
  (0~N-一万円)を五千円へそれぞれ繰り返す
    もし見つかったならば繰り返しを抜ける
    残りは,N-一万円-五千円
    もし,残り≧0かつ一万円×10000+五千円×5000+残り×1000=Yならば
      結果を「[一万円] [五千円] [残り]」とする
      結果をコンソールに表示して改行
      見つかったは,○
    もし終わり
  繰り返し終わり
繰り返し終わり
もし見つかったでないならば,「-1 -1 -1」をコンソールに表示して改行

真偽値のリテラルは/×と書きます.

この問題で最悪計算量となるケースは「$N$=2000で$Y$円となることがありえない場合」ですが,それに近い入力例4で9~12s(なぜかばらつきがある)かかってしまいました.
$N$を変えて試してみたところおおよそ$O(N^2)$で計算時間が増大しており,$O(N^2)$の想定解法にはなっているようですが,実行時間そのものは遅いようです.

プロデルはコンパイル済み実行可能ファイルの作成も可能で,これを行えばインタプリタ実行より計算時間は有利になるはずですが実行時エラーで止まってしまいました.
Exception.ToString() が失敗したため、例外文字列を表示できません。となるためエラー内容も不明です.こちらの解決は今後の課題とします.


2019/12/18追記
一応の解決をみたので追記します.

コンパイル実行時にエラーとなる問題ですが,範囲種類(0~N)オブジェクト.range等に相当し,オブジェクトとしてはPythonのジェネレータのようなもの)を使うとエラーとなってしまうようです.
これを避けて実装すると

NYは,コンソールから受け取ったものを「 」で区切ったもの
Nは,NY(1)
Yは,NY(2)
見つかったは,×
(N+1)回,s一万円にカウントしながら繰り返す
  一万円は,s一万円-1
  もし見つかったならば繰り返しを抜ける
  (N-一万円+1)回,s五千円にカウントしながら繰り返す
    五千円は,s五千円-1
    もし見つかったならば繰り返しを抜ける
    【残り:数値】は,N-一万円-五千円
    もし,残り≧0かつ(一万円×10000+五千円×5000+残り×1000=Y)ならば
      「[一万円] [五千円] [残り]」をコンソールに表示して改行
      見つかったは,○
    もし終わり
  繰り返し終わり
繰り返し終わり
もし見つかったでないならば,「-1 -1 -1」をコンソールに表示して改行

のようになります.
これを実行すると入力例4で実行時間が4.2~4.5sとなります.

速くはなりましたがまだ制限時間をオーバーしています.

ここで,型注釈をつけてみましょう.

image.png

8_annotation.rdr
【NY:文字の配列】は,コンソールから受け取ったものを「 」で区切ったもの
【N:数値】は,NY(1)
【Y:数値】は,NY(2)÷1000
【見つかった:真偽値】は,×
(N+1)回,【s一万円:数値】にカウントしながら繰り返す
  【一万円:数値】は,s一万円-1
  もし見つかったならば繰り返しを抜ける
  (N-一万円+1)回,【s五千円:数値】にカウントしながら繰り返す
    【五千円:数値】は,s五千円-1
    もし見つかったならば繰り返しを抜ける
    【残り:数値】は,N-一万円-五千円
    もし,残り≧0かつ(一万円×10+五千円×5+残り=Y)ならば
      「[一万円] [五千円] [残り]」をコンソールに表示して改行
      見つかったは,○
    もし終わり
  繰り返し終わり
繰り返し終わり
もし見つかったでないならば,「-1 -1 -1」をコンソールに表示して改行

これをコンパイルして実行するとなんと入力例4が0.4sで実行できるようになりました.
これでACです.やったね!

ちなみに,数値の注釈を整数とするとこれは4sほどかかります.
整数数値のサブクラス,もといサブ種類のはずで,このコードでは型推論で最終的に整数種類となるはずなのでこちらの方がより速くなりそうなものですが,注釈なしとほぼ同等の実行速度となりました.不思議です……


9. ABC 049 C - Daydream

image.png

9.rdr
9.rdr
コンソールから受け取ってSとする
Sは,正規表現によってSを「eraser」から「!」に置換したもの
Sは,正規表現によってSを「erase」から「!」に置換したもの
Sは,正規表現によってSを「dreamer」から「!」に置換したもの
Sは,正規表現によってSを「dream」から「!」に置換したもの
Sは,正規表現によってSを「!」から「」に置換したもの
もしS=「」ならば
  「YES」をコンソールに表示して改行
そうでなければ
  「NO」をコンソールに表示して改行
もし終わり

正規表現も扱えます.

10. ABC 086 C - Traveling

image.png

10.rdr
10.rdr
コンソールから受け取ってNとする
前xは,0
前yは,0
結果は,○
N回繰り返す
  txyは,コンソールから受け取ったものを「 」で区切ったもの
  tは,txy(1)
  xは,txy(2)
  yは,txy(3)
  結果は,(結果かつ(x-前x)の絶対値+(y-前y)の絶対値≦tかつ(x+y)%2=t%2)
繰り返し終わり
もし結果ならば「Yes」をコンソールに表示して改行でなければ「No」をコンソールに表示して改行

こちらも最大で4s程度かかってしまいます(テストケース1_004~1_006のとき).
こちらは入出力が多くなることが原因かと考えられます.


2019/12/18追記
こちらは範囲種類を使っていなかったのですが型注釈をつけてみたらコンパイル版で動くようになりました.

image.png

10_annotation.rdr
10_annotation.rdr
コンソールから受け取って【N:数値】とする
【前x:数値】は,0
【前y:数値】は,0
【結果:真偽値】は,○
N回,繰り返す
  【txy:文字の配列】は,コンソールから受け取ったものを「 」で区切ったもの
  【t:数値】は,txy(1)
  【x:数値】は,txy(2)
  【y:数値】は,txy(3)
  結果は,(結果かつ(x-前x)の絶対値+(y-前y)の絶対値≦tかつ(x+y)%2=t%2)
繰り返し終わり
もし結果ならば「Yes」をコンソールに表示して改行 でなければ「No」をコンソールに表示して改行

この問題はテストケースがすべて公開されていますが,実行時間は最大で0.7秒にまで縮まりました.
AC!


終わりに

以上,11問をプロデルで解いてみました.
構文解析が優秀なようで,()で括らずともかなり日本語のまま書くことができました.
助詞の使い方で順序を変えた表現ができるというのも面白いですね.

余談ですが,C言語を始めとしたプログラミング言語には,代入演算子で=を使ってしまっているがゆえ等値演算子は==となっているものが多くありますね.
私は等値のほうが「=」の意味としてプリミティブだと思っているので代入演算子の方を変えればいいのに,と思っているのですがプロデルは「=」が使えるのでなんだかうれしいきもちになりました.

明日は今回使用した機能を元に競プロ的コードを書く際に必要となりそうな事項を機能ベースでまとめたいと思います.


  1. これが言いたかっただけだろ 

  2. 「厳密な意味でのオブジェクト指向プログラミング言語ではありません」とのこと.どのあたりがそうなのかはよくわかりませんでした.Javaはオブジェクト指向側にカウントされているし…… 

  3. 2019/12/15現在,AtCoder Language Updateのスプレッドシートにはプロデルも導入希望言語として挙げられています.いつか本記事のコードが提出できる日も来るかもしれません. 

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした