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

まえがき

誰もやってなさそうな言語で競プロをやるシリーズ第4弾となります。

想定読者層は

• LabVIEWでプログラミングに入門してみたい人
• 普段テキストベースのプログラミング言語でやっているような処理をLabVIEWでやってみたい人
• なんでそれで競プロを？というネタを楽しみたい人
  こちらの方は以下の記事も合わせて御覧ください
  • AtCoderに登録したら解くべき精選過去問10をTeXで解いてみた
  • AtCoderに登録したら解くべき精選過去問10を「JSFuck」で解いてみた
  • AtCoderに登録したら解くべき精選過去問10をプロデルで解いてみた
• etc...

となっています。精選10問¹を題材にLabVIEWの基本的な処理から解説していきますので、是非前処理から何までLabVIEWで処理できるようになってしまいましょう！

【注意】LabVIEWは現在AtCoderでは採用されておらず、またテキストベースのジャッジシステムへの提出が困難な上、そもそも有償ソフトウェアである²ため今後もAtCoderで使用できるようになる可能性はとても低いです。あくまでネタとしてお楽しみください。

LabVIEWとは？

LabVIEWとは National Instruments 社によるグラフィック言語によりプログラミングができる開発環境であり、計測機器の制御等に使われます。

最大の特徴はこのグラフィック言語で、イメージとしてはフローチャートを描いたらそのままプログラムとして動くという感じです。後に示す通り本当にフローチャートっぽいです。
ビジュアルプログラミングといって想像されるようなScratchのような手続き型プログラミングとは違い、操作と操作のデータのやり取りに重点を置いた「データフロープログラミング」というパラダイムに基づいています。ワイヤーで繋がれて順序関係が無いような処理は並べて書/描けばそのまま同時に実行されるので並列処理が簡単にかけるという利点もあります³。

見た目通りに動く⁴ため、非プログラマーの実験家が測定機器の制御に使いたいといった用途に人気なようです。外部機器の制御では得てしてクエリを投げてから応答があるまで時間がかかるので、非同期処理が自然にかけるという点は便利ですね。

ジャッジ方法

これまでのようにコマンドライン上で呼び出して実行、というのも多分可能ですが、よくわからなかったのとせっかくのビジュアル言語なのでGUIでジャッジしてみました⁵。
ジャッジ用のプログラムは以下のようにしました。

プログラムの細かい解説はここでは割愛しますが、ダイアログでジャッジしたいプログラムファイルとテストケースのファイルを指定するとそれぞれのテストケースに対しプログラムを実行し、出力がテストケースと合っているかどうかと実行時間を測定します。
実行プログラムは文字列(ピンク色のノード)を受け取って文字列を出力する形式で作成し、ジャッジプログラム真ん中あたりの の中に代入されて実行されます。

テストケースは可能な限り公式のdropboxに公開されているものを使用しますが、見つけられなかったものは考えられるコーナーケースを含んだテストケースを作成し判定します。

解法

0. practice contest A - Welcome to AtCoder

プログラムは繋がりさえ保たれていればどう配置しても良い⁶のですが、基本的に左上から右下に向かって処理の順番になるように配置します(オート整理をかけたりするとこうなる)。

LabVIEWは静的型付け言語で、型はワイヤー(データの流れを表す線)の色で表されます。整数は青、文字列はちょっとジグザグしたピンク⁷で、ある型の配列はもとのワイヤーを太くしたもので表されます(Delimited String to 1D Arrayの前後を参照)。

処理の流れは
まとめて与えられた文字列を改行区切りで分割し行ごとの配列にする
└┬→ 1行目は数値に変換する───────────┐
.　├→ 2行目は更に空白で分割しそれぞれ数値に変換する┴ 数字の和を取る → 文字列に戻す┬→ "a+b+c"と文字列を空白を入れて結合→出力
.　└→ 3行目は文字列のまま ────────────────────────────┘
のようになっています。
1行目と「2行目の和」の和(2回目の+)につながる2つのワイヤーでは1行目のほうが先にデータが到達しますが、入力値すべてが揃うまでちゃんと実行を待機してくれます。データが枝分かれしているところでは(CPU使用設定に応じて)並列処理してくれます。
文字だけだとわかりにくいですね。ダイアグラムを見たそのままが一番わかりやすいかもしれません。

ダイアグラムを作成する際にワイヤーの接続前後で型が違ったり操作に不適切な型のワイヤーが接続されたり明確な合流操作なしにワイヤーが合流したりすると のようにワイヤーが破線となり、実行できなくなります。
コンパイルエラーを即座に教えてくれるので親切ですね。

テストケースが見つからなかったためサンプル出入力2つをテストしました。
結果： AC / 0ms

個別ケース結果

ex1 / AC / 0 ms
ex2 / AC / 0 ms

1msを切ってきました。十分速いですね。

1. ABC 086 A - Product

条件分岐には を使っています。真ん中に入ってきたbool値の真偽に応じて上か下の値を出力するもので、三項演算子のようなものです。
if文に対応するものもありますが、後述のようにダイアグラムが見づらくなるため真偽の項の評価が重くない場合(短絡評価はされないので両方とも計算されてしまう)はこっちを使ったほうがスッキリしますね。

公式テストケースから。
結果：AC / 2ms

個別ケース結果

0_000.txt / AC / 0 ms
0_001.txt / AC / 0 ms
1_002.txt / AC / 0 ms
1_003.txt / AC / 0 ms
1_004.txt / AC / 0 ms
1_005.txt / AC / 0 ms
1_006.txt / AC / 0 ms
0_000.txt / AC / 2 ms
0_001.txt / AC / 1 ms
1_002.txt / AC / 2 ms
1_003.txt / AC / 0 ms
1_004.txt / AC / 0 ms
1_005.txt / AC / 0 ms
1_006.txt / AC / 0 ms

2. ABC 081 A - Placing Marbles

白紙のページが重なったような四角：Forループストラクチャで囲うことでforループができます。For以外にも色々とストラクチャが存在します。ストラクチャ内外のデータのやり取りはコネクタを使うのですが、それについては3.でまとめて説明します。
ループカウンターは左下の［i］という四角のアイコンから取得します。

公式テストケースから。
結果：AC / 2ms

個別ケース結果

00_example_01.txt / AC / 2 ms
00_example_02.txt / AC / 0 ms
01.txt / AC / 0 ms
02.txt / AC / 0 ms
03.txt / AC / 0 ms
04.txt / AC / 0 ms
05.txt / AC / 0 ms
06.txt / AC / 0 ms

3. ABC 081 B - Shift Only

Whileループは濃い灰色の四角です。実は枠線がループする矢印になっていたりします。右下の［↺］に入力されるbool値が真の間ループし続けます。というアイコンにしてbreakしない限りループするというモードも存在します。

ストラクチャの境界を越えてデータ出し入れするときは枠線とワイヤーの交点にコネクタが作られますが、コネクタの種類によってデータをやり取りする方法が変わります。
のようにワイヤーの色の四角の場合は単純にデータをそのまま持ってきます。何回目のループでも同じ値です。
のようなコネクタは配列を分解してそれぞれの値を取り出す操作になります。foreach操作なので［N］を指定しなくても良くなります。出口に設置した場合は各ループの結果を配列にまとめたものが出力されます。
はシフトレジスタで、前のループの結果を引き継いで次のループへ渡す操作になります。累積和を計算するときなんかに便利ですね。

また、シフトレジスタと同様に前のループの結果を記憶しておいて次のループに値を渡す操作はフィードバックノード を使っても実現できます。
メインループのプログラムが長大になってしまった際⁸に、シフトレジスタでデータを端から端まで繋ぐとワイヤーが非常に煩雑になりますがフィードバックノードならば処理部分周辺だけ配線すれば良いのですっきりして見えます。
上のプラグラムは以下の様にもかけます。(ただし初期化方法などいろいろオプションがありややこしいので本記事では今後もシフトレジスタで表記します。)

公式テストケースから。
結果：AC / 1ms

個別ケース結果

1.txt / AC / 0 ms
2.txt / AC / 0 ms
3.txt / AC / 0 ms
4.txt / AC / 0 ms
5.txt / AC / 0 ms
6.txt / AC / 0 ms
7.txt / AC / 1 ms
sample1.txt / AC / 0 ms
sample2.txt / AC / 0 ms
sample3.txt / AC / 0 ms

4. ABC 087 B - Coins

すでに何度も登場していますが、 というのは配列の指定したindexの値を取り出す操作です。0-indexedですね。上下に伸ばして複数個まとめて操作することもできます。

数値演算子も剰余をとったり+1だけしたりΣで配列の総和をとったりと様々なものが揃っています。

公式テストケースから。
結果：AC / 1ms

個別ケース結果

01.txt / AC / 1 ms
02.txt / AC / 0 ms
03.txt / AC / 0 ms
04.txt / AC / 1 ms
05.txt / AC / 0 ms
06.txt / AC / 0 ms
07.txt / AC / 1 ms
08.txt / AC / 0 ms
09.txt / AC / 0 ms
10.txt / AC / 0 ms
sample01.txt / AC / 0 ms
sample02.txt / AC / 0 ms
sample03.txt / AC / 0 ms

5. ABC 083 B - Some Sums

はXがA以上B以下かの判定とこの範囲に丸めた数値を出力します。

公式テストケースから。
結果：AC / 5ms

個別ケース結果

01.txt / AC / 5 ms
02.txt / AC / 2 ms
03.txt / AC / 5 ms
04.txt / AC / 3 ms
05.txt / AC / 3 ms
06.txt / AC / 3 ms
07.txt / AC / 4 ms
08.txt / AC / 4 ms
s1.txt / AC / 0 ms
s2.txt / AC / 0 ms
s3.txt / AC / 0 ms

6. ABC 088 B - Card Game for Two

条件分岐はループと同様にストラクチャで表現します。単純なif文は黒メッシュの枠です。if文はTRUEの場合とFALSEの場合が画面外の方向に積み重なるので一度に全部見ることはできません。一度にプログラムを見通すことができないのはちょっと不便ですね。
データをストラクチャ外へ出力する場合はTRUEの場合とFALSEの場合でコネクタの配置が同じにならなければいけません。

公式のテストケースがなかったのでサンプル出入力と適当に$N$=100のデータを作ってテストします。
結果：AC / 0ms

個別ケース結果

ex1.txt / AC / 0 ms
ex2.txt / AC / 0 ms
ex3.txt / AC / 0 ms
random.txt / AC / 0 ms

random.txt

input:
100
34 18 52 1 35 51 40 96 42 2 39 50 54 3 4 6 80 8 61 49 27 12 22 2 91 67 69 7 78 54 45 26 26 97 52 98 87 2 19 3 28 16 74 49 54 3 27 85 47 97 94 81 31 63 99 21 27 39 64 97 74 79 89 38 96 6 75 22 33 45 46 94 6 2 100 77 63 37 2 16 31 97 1 45 52 51 6 67 73 73 26 28 50 63 10 51 31 33 43 41

output:
34

7. ABC 085 B - Kagami Mochi

マップやセットを扱うこともできます。型指定の関係で空集合を作るのが面倒だったので-1を入れています。
「配列から重複を削除」という操作もあるので今回はこっちのほうが早かったかもしれません。

同じく公式テストケースが見つからなかったためサンプル出入力と適当に$N$=100のデータを作ったものでテストします。
結果：AC / 0ms

個別ケース結果

ex1.txt / AC / 0 ms
ex2.txt / AC / 0 ms
ex3.txt / AC / 0 ms
random.txt / AC / 0 ms

random.txt ※100行あるので注意

input:
100
69
11
7
22
70
68
9
82
96
44
87
7
97
60
35
12
30
1
59
49
57
1
1
60
85
17
91
7
21
59
95
95
47
50
3
77
68
80
92
43
1
43
42
75
54
6
47
89
5
38
67
5
90
69
18
13
79
29
25
25
46
59
68
67
96
55
10
81
21
52
49
4
83
36
39
88
30
7
60
65
22
73
50
91
28
15
28
42
49
5
79
61
38
16
54
1
6
44
37
45

output:
64

8. ABC 085 C - Otoshidama

空白区切りで文字列を結合しようとすると少し煩雑になりますね。

公式テストケースがなかったためサンプル出入力でテスト。
入力例4が計算量最悪の場合なので時間はこれでOKです。
今回作成したtesterは出力例との比較しか行っていないため入力例3など複数の正解がある場合はWA判定になることもありますが正答を出しています。
結果：AC / 823ms

個別ケース結果

ex1.txt / AC / 0 ms
ex2.txt / AC / 0 ms
ex3.txt / WA / 297 ms
ex4.txt / AC / 823 ms

9. ABC 049 C - Daydream

文字列置換もできます。
一定の順序で置換すると全部置換できるという解法で解いています。

公式テストケースから。
結果：AC / 10ms

個別ケース結果

subtask0_0.txt / AC / 0 ms
subtask0_1.txt / AC / 2 ms
subtask0_2.txt / AC / 0 ms
subtask1_0.txt / AC / 6 ms
subtask1_1.txt / AC / 7 ms
subtask1_10.txt / AC / 6 ms
subtask1_11.txt / AC / 7 ms
subtask1_12.txt / AC / 8 ms
subtask1_13.txt / AC / 7 ms
subtask1_14.txt / AC / 9 ms
subtask1_15.txt / AC / 6 ms
subtask1_2.txt / AC / 5 ms
subtask1_3.txt / AC / 8 ms
subtask1_4.txt / AC / 8 ms
subtask1_5.txt / AC / 6 ms
subtask1_6.txt / AC / 5 ms
subtask1_7.txt / AC / 4 ms
subtask1_8.txt / AC / 5 ms
subtask1_9.txt / AC / 5 ms
subtask0_0.txt / AC / 0 ms
subtask0_1.txt / AC / 0 ms
subtask0_2.txt / AC / 0 ms
subtask1_0.txt / AC / 7 ms
subtask1_1.txt / AC / 8 ms
subtask1_10.txt / AC / 6 ms
subtask1_11.txt / AC / 8 ms
subtask1_12.txt / AC / 8 ms
subtask1_13.txt / AC / 6 ms
subtask1_14.txt / AC / 9 ms
subtask1_15.txt / AC / 10 ms
subtask1_2.txt / AC / 7 ms
subtask1_3.txt / AC / 7 ms
subtask1_4.txt / AC / 9 ms
subtask1_5.txt / AC / 6 ms
subtask1_6.txt / AC / 8 ms
subtask1_7.txt / AC / 5 ms
subtask1_8.txt / AC / 6 ms
subtask1_9.txt / AC / 7 ms

10. ABC 086 C - Traveling

modやlog、三角関数など一定の数式を計算できる数式ノードというものがあり、まとめて計算することもできます。

公式テストケースから。
結果：AC / 279ms

個別ケース結果

0_000.txt / AC / 0 ms
0_001.txt / AC / 0 ms
0_002.txt / AC / 0 ms
1_003.txt / AC / 0 ms
1_004.txt / AC / 279 ms
1_005.txt / AC / 239 ms
1_006.txt / AC / 195 ms
1_007.txt / AC / 31 ms
1_008.txt / AC / 2 ms
1_009.txt / AC / 33 ms
1_010.txt / AC / 3 ms
1_011.txt / AC / 23 ms
1_012.txt / AC / 2 ms

まとめ

以上、LabVIEWで精選10問を解いてみました。なかなかいい感じに解けたと思います。
テスト用プログラムのようなファイルIOの処理やイベント処理など様々な処理ができ、またテキストボックスやグラフなどの出入力GUIを作るエディタもあるのでかんたんにアプリケーションが作れます。
SpaceXの地上管制ソフトもLabVIEWで作られているそうです。

SpaceX（Dragon2）のUIはChromiumとJavaScript。内部的にはC++で制御してるらしい。地上の管制チームのソフトは主にLabVIEWだそう。
UIの美しさこだわってるあたりが、SpaceXっぽいね。 pic.twitter.com/vZcrFmelJV

— D社のいとうさん (@itoh3d) May 31, 2020

現在LabVIEWは個人の非商用利用に限り無償使用できるコミュニティエディションも公開されているので興味のある方は一度使ってみてはいかがでしょうか？

---

1. @drken さんによる記事 AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～ に提示された初心者向け問題を集めた10問．言語を触って遊んでみるのに丁度いい難易度の問題が揃っています．現在はAtCoder Beginners Selectionとして問題セットがまとめられています. ↩

2. 最近は非商用なら無償使用できるっぽいです。 ↩

3. というよりそのために開発されたパラダイムです ↩

4. 本当か？ ↩

5. このため今回は標準出入力は扱っていません。競プロといえば、という感じもありますがかなり非標準的な方法を取らなければならなそうだったので断念しました。m(_ _)m ↩

6. こんな↓になっていても動きます。トポロジーですね ↩

7. その他、bool値は緑の点線、浮動小数点数はオレンジになり、多重配列は2重線, 3重線と太くなっていきます。またその他ファイルパスや複数の型の値をまとめたクラスタ(≒タプル)、列挙子などもあります。オブジェクト指向ではないのでユーザー定義クラスのようなものは無いようです。 ↩

8. LabVIEWはマクロ等は使えず、「メソッド」を作ろうとする度に別ファイルに保存する必要があるためコード分割が億劫になり文字通りのスパゲッティコードが爆誕しがちです。 ↩