はじめに
このツイートを見ました
AtCoderでMATLAB使いたいって人どれくらいいるんだろう。（どれくらいいるかによってどれくらい頑張るかが決まるので）
— chokudai(高橋 直大)🌸🍆🍡 (@chokudai) April 28, 2020
2020年5月現在、AtcoderでMATLABは使えないので、使えるようになったら嬉しいな導入して欲しいなと思って応援のために書きました。
この記事で扱うプログラムのライブスクリプトはgithubの自分のリポジトリにあります。
参考記事
MATLABとは
MathWorks社が開発している数値解析ソフトウェア、およびその中で使われている言語の名称です。MATLAB - MathWorks
ディープラーニングや信号処理など様々なことができます。すごく便利。
学生の場合、学校が包括契約しているしているかもしれないので、確認してみてください。
AtcoderBiginnersSelectionとは
@drkenさんの記事、AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～ で紹介されたAtcoderの初心者向けの問題選です。問題だけ見たい人はAtcoderのページを見てください。
新しく言語を使ってみようと考えてる人がやってみるのにちょうど良い感じです。
環境
MATLAB R2020a
入力と出力について
入力
コマンドに入力例を貼り付けて実行することを想定します。
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がプリンターから印刷されます。(なければエラー)
fprintf(formatSpec,A1,...,An)
disp(A)
formatSpecについてはこちら(MathWorks)を参照
公式の実装がどうなるか分からないですが、とりあえずfprintf()で答えを出すところまでを目指します。Octaveではprintf()でも大丈夫みたいですね。
PracticeA - Welcome to AtCoder
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より
だそうです。
これ以降もMathworksのリンクはたびたび出てくると思います。
MATLABの関数は公式ドキュメントにすべて記されているので、どのような引数が必要か戻り値はどうなっているのかは「matlab 関数名」と検索するとたいてい出てきます。
とても便利なので活用してみてください。
sum(A)はAがベクトルであれば総和を計算してくれます。Aが行列なら各列の和の行ベクトルが帰ってきます。sum(matrix, 'all')とかすると行列の要素の総和が帰ってきます(2018b以降)
ABC086A - Product
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のページの詳細に定義があります。
ABC081A - Placing Marbles
clear
str = input('', 's')
fprintf("%d\n", count(str, '1'))
count(str, pattern) はstr内のpatternの出現回数を返します。str, patternはともに行列でも大丈夫です。
ABC081B - Shift only
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
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を確認されたし
matrix >= 0 & matrix <= c*50 では０か１のlogicalな行列ができます。
0は不適な組み合わせ、1は適当な組み合わせの時に発生するので、この行列の要素の総和が今回の答えとなります。
愚直な実装であると次のようになります。
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
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
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(:)についてはMathworksを参照。1:2:n はつまり [1, 3, 5 ..., 2*fix(n/2)]となります。
b(1:2:n)で奇数番目の要素を抜き出しています。
ABC085B - Kagami Mochi
clear
n = input("");
for i = 1:n
a(i) = input("");
end
fprintf("%d\n", length(unique(a)))
MATLABでは行列の範囲外を指定して要素を挿入することができます。Mathworksの(行列の作成、連結、および拡張)を参照
ただし、サイズが大きくなるたびメモリを新しく確保するため、この方法は速度の低下の原因となります。あらかじめzeros(1,n)などでメモリを確保しておくと良いでしょう。
for文でinput()を多用していますが、この問題の制約で${n\leq100}$というものがあり、十分小さいのでTLEしません。
ABC085C - Otoshidama
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 - 白昼夢
2020/05/05 変更 TLEしないように書き直しました。
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で呼び出し元のスクリプトに戻ります。
TLEしてしまった解法
strlength(s)=10^5の時に10秒以上かかってしまいます。
上記のプログラムと考え方やアルゴリズムはほぼ同じですが、反転やint<->stringなどをする文字列操作が多いためTLEするものと考えられます。
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()は空配列であれば真となります。
ABC086C - Traveling
nが大きくなるとTLEします。
意見求ム
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には次のようにデータが入ります。
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の代用にはなりませんね‥‥
MATLAB導入