More than 1 year has passed since last update.

プロデルAdvent Calendar 2019

@Mopepe51(雪下)

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

Last updated at 2022-04-05Posted at 2019-12-14

競技プロデル，題して競プロ ¹

2019/12/18 更新：#8，#10がコンパイル版で動かなかった件について追記

まえがき

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

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

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

追記

2019/12/18 実行時間超過した問題をコンパイル版で解決
2022/04/05 ブロック繰り返しや分解代入について追記

実行環境

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

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

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

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

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

0. PracticeA - Welcome to AtCoder

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

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

0.rdr

コンソールから受け取って，入力aとする
コンソールから受け取って，入力bcとする
コンソールから受け取って，入力textとする
分割bcは，入力bcを「 」で区切ったもの
「［入力a＋分割bc(１)＋分割bc(２)］ ［入力text］」をコンソールに表示して改行する

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

1. ABC 086 A - Product

1.rdr

ａｂは，コンソールから受け取ったものを「 」で区切ったもの
もしａｂ(１)％２が０またはａｂ(２)%２が0ならば
  「Even」をコンソールに表示して改行
そうでなければ
  「Odd」をコンソールに表示して改行
もし終わり

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

2. ABC 081 A - Placing Marbles

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

2.rdr

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

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

3. ABC 081 B - Shift Only

3.rdr

入力ｎは，コンソールから受け取ったもの
入力ａは，コンソールから受け取ったものを「 」で区切ったもの
結果は，０
((入力ａすべてを２で割ったあまり)の合計が０より大きい)になるまで繰り返す
  入力ａは，入力ａすべてを２で割ったもの
  結果に１を足す
繰り返し終わり
結果をコンソールに表示する

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

4. ABC 087 B - Coins

4.rdr

コンソールから受け取ってＡとする
コンソールから受け取ってＢとする
コンソールから受け取ってＣとする
コンソールから受け取ってＸとする
結果は，０
(０～Ａ)をｉへそれぞれ繰り返す
  (０～Ｂ)をｊへそれぞれ繰り返す
    (０～C)をｋへそれぞれ繰り返す
      もし５００×ｉ＋１００×ｊ＋５０×ｋ＝Ｘならば結果に１を足す
    繰り返し終わり
  繰り返し終わり
繰り返し終わり
結果をコンソールに表示

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

5. ABC 083 B - Some Sums

5.rdr

ＮＡＢは，コンソールから受け取ったものを「 」で区切ったもの
Ｎは，ＮＡＢ（１）
Ａは，ＮＡＢ（２）
Ｂは，ＮＡＢ（３）
結果は，０
Ｎ回，ｉにカウントしながら繰り返す
  各桁和は，０
  (１～「［ｉ］」の文字数)をけたへそれぞれ繰り返す
    各桁和に「［ｉ］」のけた文字目を足す
  繰り返し終わり
  もし各桁和≧Ａかつ各桁和≦Ｂならば結果にｉを足す
繰り返し終わり
結果をコンソールに表示して改行

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

6. ABC 088 B - Card Game for Two

6.rdr

コンソールから受け取ってＮとする
Ａたちは，コンソールから受け取ったものを「 」で区切ったもの
Ａたちを大きい順に並び替える
アリスは，０
ボブは，０
Ｎ回，ｉにカウントしながら繰り返す
  もしｉを２で割ったあまりが１ならば
    アリスにＡたち（ｉ）を足す
  そうでなければ
    ボブにAたち（ｉ）を足す
  もし終わり
繰り返し終わり
アリス－ボブをコンソールに表示

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

7. ABC 085 B - Kagami Mochi

7.rdr

コンソールから受け取ってＮとする
辞書を作って集合とする
Ｎ回繰り返す
  コンソールから受け取ってｄとする
  集合のｄは，１
繰り返し終わり
集合の個数をコンソールに表示する

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

8. ABC 085 C - Otoshidama

8.rdr

ＮＹは，コンソールから受け取ったものを「 」で区切ったもの
Ｎは，ＮＹ（１）
Ｙは，ＮＹ（２）
見つかったは，×
(０～Ｎ)を一万円へそれぞれ繰り返す
  もし見つかったならば繰り返しを抜ける
  (０～Ｎ－一万円)を五千円へそれぞれ繰り返す
    もし見つかったならば繰り返しを抜ける
    残りは，Ｎ－一万円－五千円
    もし，残り≧０かつ一万円×10000＋五千円×5000＋残り×1000＝Ｙならば
      結果を「［一万円］ ［五千円］ ［残り］」とする
      結果をコンソールに表示して改行
      見つかったは，○
    もし終わり
  繰り返し終わり
繰り返し終わり
もし見つかったでないならば，「-1 -1 -1」をコンソールに表示して改行

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

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

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

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

コンパイル実行時にエラーとなる問題ですが，範囲種類（（０～Ｎ）オブジェクト．range等に相当し，オブジェクトとしてはPythonのジェネレータのようなもの）を使うとエラーとなってしまうようです．
これを避けて実装すると

ＮＹは，コンソールから受け取ったものを「 」で区切ったもの
Ｎは，ＮＹ（１）
Ｙは，ＮＹ（２）
見つかったは，×
(Ｎ＋１)回，ｓ一万円にカウントしながら繰り返す
  一万円は，ｓ一万円－１
  もし見つかったならば繰り返しを抜ける
  (Ｎ－一万円＋１)回，ｓ五千円にカウントしながら繰り返す
    五千円は，ｓ五千円－１
    もし見つかったならば繰り返しを抜ける
    【残り：数値】は，Ｎ－一万円－五千円
    もし，残り≧０かつ(一万円×１００００＋五千円×５０００＋残り×１０００＝Ｙ)ならば
      「［一万円］ ［五千円］ ［残り］」をコンソールに表示して改行
      見つかったは，○
    もし終わり
  繰り返し終わり
繰り返し終わり
もし見つかったでないならば，「-1 -1 -1」をコンソールに表示して改行

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

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

ここで，型注釈をつけてみましょう．

8_annotation.rdr

【ＮＹ：文字の配列】は，コンソールから受け取ったものを「 」で区切ったもの
【Ｎ：数値】は，ＮＹ（１）
【Ｙ：数値】は，ＮＹ（２）÷１０００
【見つかった：真偽値】は，×
(Ｎ＋１)回，【ｓ一万円：数値】にカウントしながら繰り返す
  【一万円：数値】は，ｓ一万円－１
  もし見つかったならば繰り返しを抜ける
  (Ｎ－一万円＋１)回，【ｓ五千円：数値】にカウントしながら繰り返す
    【五千円：数値】は，ｓ五千円－１
    もし見つかったならば繰り返しを抜ける
    【残り：数値】は，Ｎ－一万円－五千円
    もし，残り≧０かつ(一万円×１０＋五千円×５＋残り＝Ｙ)ならば
      「［一万円］ ［五千円］ ［残り］」をコンソールに表示して改行
      見つかったは，○
    もし終わり
  繰り返し終わり
繰り返し終わり
もし見つかったでないならば，「-1 -1 -1」をコンソールに表示して改行

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

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

9. ABC 049 C - Daydream

9.rdr

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

正規表現も扱えます．

10. ABC 086 C - Traveling

10.rdr

コンソールから受け取ってＮとする
前ｘは，０
前ｙは，０
結果は，○
Ｎ回繰り返す
  ｔｘｙは，コンソールから受け取ったものを「 」で区切ったもの
  ｔは，ｔｘｙ（１）
  ｘは，ｔｘｙ（２）
  ｙは，ｔｘｙ（３）
  結果は，(結果かつ(ｘ－前ｘ)の絶対値＋(ｙ－前ｙ)の絶対値≦ｔかつ(ｘ＋ｙ)％２＝ｔ％２)
繰り返し終わり
もし結果ならば「Yes」をコンソールに表示して改行でなければ「No」をコンソールに表示して改行

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

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

10_annotation.rdr


コンソールから受け取って【Ｎ：数値】とする
【前ｘ：数値】は，０
【前ｙ：数値】は，０
【結果：真偽値】は，○
Ｎ回，繰り返す
  【ｔｘｙ：文字の配列】は，コンソールから受け取ったものを「 」で区切ったもの
  【ｔ：数値】は，ｔｘｙ（１）
  【ｘ：数値】は，ｔｘｙ（２）
  【ｙ：数値】は，ｔｘｙ（３）
  結果は，(結果かつ(ｘ－前ｘ)の絶対値＋(ｙ－前ｙ)の絶対値≦ｔかつ(ｘ＋ｙ)％２＝ｔ％２)
繰り返し終わり
もし結果ならば「Yes」をコンソールに表示して改行 でなければ「No」をコンソールに表示して改行

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

2022/04/05 追記
最新版（Version 1.8.1117 2022/04/05現在）のプロデルではブロック文『～』を使った自然な形の繰り返し文やみなす文をつかった分解代入などを使ってより簡潔に記述できます．

10_new.rdr

コンソールから受け取って【N：整数】とする
【前のｘ：整数】は，０
【前のｙ：整数】は，０
【到達：真偽値】は，○
『
  コンソールから受け取ったものを「 」で区切ったものを｛【ｔ：整数】，【ｘ：整数】，【ｙ：整数】｝とみなす
  到達は，（到達かつ（ｘ－前のｘ）の絶対値＋（ｙ－前のｙ）の絶対値≦ｔかつ（ｘ＋ｙ）％２＝ｔ％２）
』をN回繰り返す
もし到達ならば「Yes」をコンソールに表示して改行 でなければ「No」をコンソールに表示して改行

終わりに

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

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

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

これが言いたかっただけだろ ↩
「厳密な意味でのオブジェクト指向プログラミング言語ではありません」とのこと．どのあたりがそうなのかはよくわかりませんでした．Javaはオブジェクト指向側にカウントされているし…… ↩
2019/12/15現在，AtCoder Language Updateのスプレッドシートにはプロデルも導入希望言語として挙げられています．いつか本記事のコードが提出できる日も来るかもしれません． ↩

You get articles that match your needs
You can efficiently read back useful information
You can use dark theme

What you can do with signing up