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

## はじめに

このツイートを見ました

<blockquote class="twitter-tweet"><p lang="ja" dir="ltr">AtCoderでMATLAB使いたいって人どれくらいいるんだろう。（どれくらいいるかによってどれくらい頑張るかが決まるので）</p>&mdash; chokudai(高橋 直大)🌸🍆🍡 (@chokudai) <a href="https://twitter.com/chokudai/status/1255015433666564096?ref_src=twsrc%5Etfw">April 28, 2020</a></blockquote> <script async src="https://platform.twitter.com/widgets.js" charset="utf-8"></script> 

2020年5月現在、AtcoderでMATLABは使えないので、使えるようになったら嬉しいな導入して欲しいなと思って応援のために書きました。

この記事で扱うプログラムのライブスクリプトは[githubの自分のリポジトリ](https://github.com/pojoy/AtcoderBeginnersSelection-by-matlab)にあります。

参考記事
- [AtCoderに登録したら解くべき精選過去問10問をOctaveで解いてみた](https://qiita.com/universato/items/735d309d2a697e8529c0)
- [Atcoder Beginners SelectionをOctaveで解いてみた。](http://osrehun.hatenadiary.jp/entry/2018/03/21/220805)

## MATLABとは

MathWorks社が開発している数値解析ソフトウェア、およびその中で使われている言語の名称です。[MATLAB - MathWorks](https://jp.mathworks.com/products/matlab.html)
ディープラーニングや信号処理など様々なことができます。すごく便利。
学生の場合、学校が包括契約しているしているかもしれないので、確認してみてください。


## AtcoderBiginnersSelectionとは

@drkenさんの記事、[AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～](https://qiita.com/drken/items/fd4e5e3630d0f5859067#5-%E9%81%8E%E5%8E%BB%E5%95%8F%E7%B2%BE%E9%81%B8-10-%E5%95%8F) で紹介されたAtcoderの初心者向けの問題選です。問題だけ見たい人は[Atcoderのページ](https://atcoder.jp/contests/abs/)を見てください。

新しく言語を使ってみようと考えてる人がやってみるのにちょうど良い感じです。

## 環境

MATLAB R2020a

## 入力と出力について

### 入力

コマンドに入力例を貼り付けて実行することを想定します。

```MATLAB
x = input('') % 数字, 文字列
str = input('', 's') % 空白含め一行分をstringで取得
```
``scanf()``はないので``input(prompt)``を利用します。

Pythonのように ``x = input()``とすると引数不足で怒られるので注意してください。空白区切りはstrで取って``split(str)``します。数字の空白区切りは``str2num(input('', 's'))``か``str2double(input('','s'))``すると大変楽になると思います。

#### 現時点で分かっている問題点 (5月4日追記)

Octaveと比べ、MATLABはClikeな関数が使えません。よって大きな入力時にTLEする可能性がとても高いです。(Travelingのn=10000のときなど)
参考記事にあるような``scanf()``は使えませんし、``dlmread(filename)``についてはMATLABに存在しますが現在非推奨です。
``dlmread(filename)``の代わりに``readmatrix(filename)``という関数がありますが、どちらも``filename``に空文字/0/stdinなどは使えないためコマンドから入力を取ることができません。

つまり、``input("")``を多用するしか複数行を読み込む方法がないのが現状です。

この問題をどうにかしない限り、10000行の入力がある場合などで必ずTLEとなってしまいます。
知恵をください。

### 出力

適当に``print()``するとFigureがプリンターから印刷されます。(なければエラー)

```MATLAB
fprintf(formatSpec,A1,...,An)
disp(A)
```

formatSpecについては[こちら(MathWorks)](https://jp.mathworks.com/help/matlab/ref/fprintf.html#btf8xsy-1_sep_shared-formatSpec)を参照

公式の実装がどうなるか分からないですが、とりあえず``fprintf()``で答えを出すところまでを目指します。Octaveでは``printf()``でも大丈夫みたいですね。


## [PracticeA - Welcome to AtCoder](https://atcoder.jp/contests/abs/tasks/practice_1)

```matlab:PracticeA.m
clear

a = input('')
secondLine = str2num(input('', 's'))
% secondLine = str2double(input('', 's'))
str = input('', 's')

fprintf('%d %s\n', a+sum(secondLine), str)
```

``input('')``では``2/3``や``pi``といった入力も受け付けます。(doubleでの処理になります)

``str2num()``は
> X = str2num(chr) は文字配列または string スカラーを数値行列に変換します。入力には、個別の要素を示すためにスペース、コンマ、セミコロンを使用できます。[Mathworksより](https://jp.mathworks.com/help/matlab/ref/str2num.html:title)

だそうです。

これ以降もMathworksのリンクはたびたび出てくると思います。
MATLABの関数は公式ドキュメントにすべて記されているので、どのような引数が必要か戻り値はどうなっているのかは「matlab 関数名」と検索するとたいてい出てきます。
とても便利なので活用してみてください。

``sum(A)``はAがベクトルであれば総和を計算してくれます。Aが行列なら各列の和の行ベクトルが帰ってきます。``sum(matrix, 'all')``とかすると行列の要素の総和が帰ってきます(2018b以降)

## [ABC086A - Product](https://atcoder.jp/contests/abs/tasks/abc086_a)

```matlab:ABC086A_Product.m
clear

inputLine = str2num(input('', 's'))

c = prod(inputLine)

if mod(c, 2) == 0
    fprintf("Even\n")
else
    fprintf("Odd\n")
end
```

``prod()`` はベクトルの要素の積を返してくれます。

``if ~ elseif ~ else ~ end`` は見やすさのためにインデントを入れていますが、MATLABでは必ずしも必要ではありません。

余りは ``mod(a, b)`` で求めます。 ``a % b`` ではできません。MATLABでは ``%`` はコメントアウトです。[Mathworksのmodのページ](https://jp.mathworks.com/help/symbolic/mod.html)の詳細に定義があります。

## [ABC081A - Placing Marbles](https://atcoder.jp/contests/abs/tasks/abc081_a)

```matlab:ABC081A_PlacingMarbles.m
clear

str = input('', 's')
fprintf("%d\n", count(str, '1'))
```

``count(str, pattern)`` はstr内のpatternの出現回数を返します。str, patternはともに行列でも大丈夫です。

## [ABC081B - Shift only](https://atcoder.jp/contests/abs/tasks/abc081_b)

```matlab:ABC081B_Shiftonly.m
clear

n = input('')
a = str2num(input('', 's'))

answer = 0

while mod(a, 2) == 0
    a = a / 2
    answer = answer + 1
end

fprintf('%d\n', answer)
```

``while ~ end`` はそのままです。whileのあとの文が真であれば継続します。

``mod(a, 2)`` では1×nの行列が戻ってきます。これらの値が0であるかを ``== 0`` で比較し、すべて0であれば真となります。

## [ABC087B - Coins](https://atcoder.jp/contests/abs/tasks/abc087_b)

```matlab:ABC087B_Coins.m
clear

a = input('')
b = input('')
c = input('')
x = input('')

answer = 0
matrix = x - (0:a) * 500 + (0:b)' * 100
answer = sum(matrix >= 0 & matrix <= c*50, 'all')
fprintf('%d\n', answer)
```

MATLABでは(0:N)と書くことにより1×(N+1)のベクトルを生成します。またベクトルや行列に``'``をつけることにより転置したものになります。行ベクトルと列ベクトルを ``+`` 演算子で足し合わせると、行列ができあがります。[Mathworksを確認されたし](https://jp.mathworks.com/help/matlab/ref/plus.html)

``matrix >= 0 & matrix <= c*50`` では０か１のlogicalな行列ができます。
0は不適な組み合わせ、1は適当な組み合わせの時に発生するので、この行列の要素の総和が今回の答えとなります。

愚直な実装であると次のようになります。

```matlab
for i = 0:a
    for j = 0:b
        for k = 0:c
            if x == 500*i + 100*j + 50*k
                answer = answer + 1;
            end
        end
    end
end
```

## [ABC083B - Some Sums](https://atcoder.jp/contests/abs/tasks/abc083_b)

```matlab:ABC083B_SomeSums.m
clear

inputLine = str2num(input('', "s"))

answer = 0;
for i = 1:inputLine(1)
    temp = i;
    ref = 0;
    while temp ~= 0
        ref = ref + mod(temp, 10);
        temp = floor(temp/10);
    end
    if inputLine(2) <= ref & ref <= inputLine(3)
        answer = answer + i;
    end
end

fprintf("%d\n", answer)
```

**MATLABでは配列へのアクセスは1から始まります。**

``~=`` は不等価を表します。

## [ABC088B - Card Game for Two](https://atcoder.jp/contests/abs/tasks/abc088_b)

```matlab:ABC088B_CardGameforTwo.m
clear

n = input("")
a = str2num(input("","s"))

b = sort(a,'descend')

aliceScore = sum(b(1:2:n))
bobScore = sum(b(2:2:n))

fprintf("%d\n", aliceScore - bobScore)
```

``sort(A)`` はベクトルAを昇順に並び替えます。
``sort(A,"descend")``にすることで降順にします。

[colon(:)](https://jp.mathworks.com/help/matlab/ref/colon.html)についてはMathworksを参照。``1:2:n`` はつまり ``[1, 3, 5 ..., 2*fix(n/2)]``となります。
``b(1:2:n)``で奇数番目の要素を抜き出しています。

## [ABC085B - Kagami Mochi](https://atcoder.jp/contests/abs/tasks/abc085_b)

```matlab:ABC085B_KagamiMochi.m
clear

n = input("");
for i = 1:n
    a(i) = input("");
end

fprintf("%d\n", length(unique(a)))
```

MATLABでは行列の範囲外を指定して要素を挿入することができます。Mathworksの[(行列の作成、連結、および拡張)](https://jp.mathworks.com/help/matlab/math/creating-and-concatenating-matrices.html)を参照
ただし、サイズが大きくなるたびメモリを新しく確保するため、この方法は速度の低下の原因となります。あらかじめ``zeros(1,n)``などでメモリを確保しておくと良いでしょう。

for文でinput()を多用していますが、この問題の制約で${n\leq100}$というものがあり、十分小さいのでTLEしません。

## [ABC085C - Otoshidama](https://atcoder.jp/contests/abs/tasks/abc085_c)

```matlab:ABC085C_Otoshidama.m
clear

inputLine = str2num(input('', 's'));

n = inputLine(1);
y = inputLine(2);

answer = [-1 -1 -1];

for i=0:n
    for j=0:n-i
        if y == 10000*i+5000*j+1000*(n-i-j)
            answer = [i, j, n-i-j];
        end
    end
end

fprintf("%d %d %d\n", answer)
```

この解法ですが、Octaveで実行するとおそらくTLEします。

n = 2000, y = 20000000 とすると、自分のPCでの計測ですが、MATLABで0.085932秒であり、Octaveでは9.70843秒となりました。これではあまりにも差がありすぎるため、MATLABユーザーがOctaveを使っての参加を躊躇してしまう理由になると思います。

## [ABC049C - 白昼夢](https://atcoder.jp/contests/abs/tasks/arc065_a)

2020/05/05 変更 TLEしないように書き直しました。

```matlab:ABC049C_Daydream.m
clear

s = input("", "s");
r_elem = ["dream" "dreamer" "erase" "eraser"];
r_len = [5 7 5 6];

s_length = strlength(s);

pos = s_length;
flg = 1;

while pos
    for e = 1:4
        if strcmp(r_elem(e), ...
                extractBetween(s, max(1, pos - r_len(e)+1), pos))
            flg = 0;
            pos = pos-r_len(e);
            break
        end
    end
    
    if flg
        fprintf("NO\n")
        return
    else
        flg = 1;
    end
end
fprintf("YES\n")

```
``if strcmp(r_elem(e), ...``に出てくる``...``ですが、これは引数などが多く、横に長くなってしまった時に改行したい場合に使います。
``extractBetween(str, pos1, pos2)``はstrのpos1からpos2までの文字列を抜き出す関数です。
``return``で呼び出し元のスクリプトに戻ります。

<details><summary>TLEしてしまった解法</summary><div>

strlength(s)=10^5の時に10秒以上かかってしまいます。
上記のプログラムと考え方やアルゴリズムはほぼ同じですが、反転やint<->stringなどをする文字列操作が多いためTLEするものと考えられます。

```matlab:ABC049C_Daydream.m
clear

s = input("", "s");

s_reverse = reverse(s);

r_elem = reverse(["dream" "dreamer" "erase" "eraser"]);

flg = 1;

while s_reverse
    for e = r_elem
        k = strfind(s_reverse, e);
        if ~isempty(k) && k(1) == 1
            flg=0;
            s_reverse = s_reverse(strlength(e)+1:end);
            break
        end
    end

    if flg
        fprintf("NO\n")
        return
    else
        flg = 1;
    end
end
fprintf("YES\n")
```

``reverse(str)``で文字列を反転します。
``isempty()``は空配列であれば真となります。

</div></details>

## [ABC086C - Traveling](https://atcoder.jp/contests/abs/tasks/arc089_a)

**nが大きくなるとTLEします。**
意見求ム

```matlab:ABC086C_Traveling.m
clear

n = input("");

txy = zeros(3,n+1);

for i = 2:n+1
    txy(:,i) = str2num(input("", 's'));
end

for i = 2:n+1
    diff_t = txy(1,i) - txy(1,i-1);
    distance = sum(abs(txy(2:3,i)-txy(2:3,i-1)));
    if mod(distance - diff_t, 2) || (diff_t < distance)
        fprintf("No")
        return
    end
end

fprintf("Yes")
```

``txy(:,i)`` は txyのi列目のすべての要素を指しています。
よって最初のfor文によって``txy``には次のようにデータが入ります。

```matlab
txy =
     0     t1    t2   ...   tn
     0     x1    x2   ...   xn
     0     y1    y2   ...   yn
```

``sum(abs(txy(2:3,i)-txy(2:3,i-1)))``で2点間の市街地距離を求めています。

## おわりに

久々にAtcoderを開きました(最近サボっているので‥‥) ~~たぶんACできると思いますが、TLEとかしませんよね？~~TLEするものがありました。申し訳ない
MATLABにそこまで詳しくないので、もっと良い書き方があったら教えてください。

また、今回調べる上で"GNU Octave"の存在を知りました。以外と動かせるのかなと思いましたが、for文を2重にするだけで時間がかかってしまうのはつらいですね‥‥
MATLABの代用にはなりませんね‥‥

<!-- 気が向いたらOctaveとの比較の記事を書きます -->

MATLAB導入:pray: