はじめに
@drken さんの記事で紹介されていた AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～をOctaveで解いてみました。
Octaveは、有料のMATLABと互換性のある言語で、行列などの数値計算を得意としている言語です。RubyやPythonのように比較的書きやすく、マイナーな割にはかなりスマートにデータを扱うのが得意な印象です。MATLABの練習と競プロを同時にしたい人には、AtCoderのOctaveという選択になるのかなと思います。
問題については、自分レベルから正直にいうと、最初の10問としたらABCのB問題・C問題まであってかなり難しいのではと思います。実際、一筋縄ではいかない問題が後半に行くほど多数ありました。頑張って解いたので、まとめておきたいと思います。ただ、Octaveの魅力みたいなのは、この記事では伝えられないと思うので、Octaveの良問をセレクトした記事をまたいつか書ければと思います。ちなみに、私がよく触る言語は、Ruby, Python, C++, Octaveなので、その認識で読んでもらえると読みやすいかもしれません。
▼AtCoderの公式ページでのまとめ
問題 - AtCoder Beginners Selection
問題 - Language Test 202001
▼同様の他言語のまとめ記事
百花繚乱！なないろ言語で競技プログラミングをする資料まとめ - Qiita
▼先行記事
Atcoder Beginners SelectionをOctaveで解いてみた。 - ヘクトのメモ
2020/3/27追記：本日、リンク先のリンク先のAtCoder Beginners Selectionが外部攻撃に対する負荷対策ですべての提出コードが読めなくなっていたのが、解消されました。自分が問題を解いているときにコードは見れませんでしたが、メモはとても役に立ちました。時間制限の厳しい第10問はOctaveで解けた人がいたという事実がなければ、力尽きて諦めていたと思います。こちらもご参考になると思います。
なお、趣味でプログラミング言語を齧ってるだけなので、不確かなこともあるかもしれませんが、コメントなどでご指摘いただければと思います。
Octaveのバージョン
バージョンは、AtCoderの4.0.2/5.1.0、ローカルの5.2.0/5.1.9で検証しています。
AtCoderの現在のバージョンは4.0.2ですが、アップデートされれば5.1.0になる予定みたいです。
なお、自分が試す限り、4.0.2では使えたinput(0)という表記による入力が、5.1.0では使えなくなっております。input関数自体は使えます。
Octaveを使うには
ダウンロード・インストールをするのが普通かもしれませんが、下記のサイトからOctaveを試せます。
Online Compiler and IDE - Ideone.com
色々な言語が試せるオンラインのエディタで、Octaveを選択を出来、標準入力・標準出力も試せます。公開設定については注意しましょう。
Octave Online · Cloud IDE compatible with MATLAB
標準入力する場所がなさそうですが、アカウントなしでも簡単に試せます。
コードテスト - AtCoder Beginners Selection
AtCoderの各コンテストでタブから行けます。
標準入力・標準出力など簡単に試せるので結構便利です。
Octaveの主な入力
主にscanf関数とinput関数が短くて書きやすいのでこの2つを使います。
・input('') ...数値1つを読み込むときに使用。引数はユーザーに入力を促すために表示する文字列で、省略できません。余計な出力をしないよう空文字列を入れます。
・input('', 's')...文字列1行を読み込むとき。fgetl(0)でも同じ。
・scanf("%d") ...残り全ての数値をベクトルで読み込むとき。
・scanf("%d %s", 'C')...C言語のように1つずつ読み込むとき
・scanf("%d", [nr nc])...nr行nr列の行列の形で読み込むとき(1列目から埋めます)。
文字列はシングルクォートでもダブルクォートでも対応していれば問題ないです。
また、dlmread関数というものがあります。Octaveらしいです。
本記事でも最後の第10問は、まとめて行列の形で入力しないとTLEになり厳しいため、dlmreadを用いています。
行列形式で扱えるときは、scanf("%d", [nr nc])の形式やdmlread関数を用いると入力が速いので、そちらを使っていきましょう。scanf("%d", [nr nc])は1列目から埋めていきますが、dmlread関数は1行目から埋めていきますのでAtCoderの入力形式と同じなり直観的です。
その他、fread関数やfscanf関数などもありますが、覚えてなくても困ることはないでしょう。なお、入力系の関数の第一引数には、stdinや0が入れることがあります。stdinは0の値が入っている変数であり、ここではstdinと0は同じ意味合いと考えて良いでしょう。この0は、標準入力(standard input)であることを示す値であり、ファイル名を入れる代わりに0を入れることで「標準的な場所から入力を受け取ります」という意味合いになるようです。おまじないと考えて良いでしょう。
Octaveの主な出力
近年のAtCoderの単純な出力のものに対しては、disp関数のみで足りることが多いです。
しかし、disp関数は、正の数値の出力の際に、余計な空白1字を最初に出力します。
そのため、AtCoderの初期の問題は余計な空白があるとWAと判定されるため、disp関数のみでは上手くいかないです。
本記事でも、最初の練習問題A - Welcome to AtCoderがdisp関数のみでは対処できないです。
これに対する対処は、2通りほどあります。
①C言語のようなprintf関数を用いて、柔軟に対処。
②デフォルトの実数型から、int32関数やnum2str関数で型を変更してdisp関数で出力する。
他にもdlmwrite関数やfwrite関数などがありますが、使う機会は少ないでしょう。dlmwrite関数は、末尾の改行ありの出力で、第3引数で区切り文字を指定できるので、行列を出力したいときはスッキリ書けて良いかもしれませんが、本記事での扱いはないです。
Octaveのコメント
%と#がコメントとして使えます。
右側以降がコメントとなり、プログラムとして認識されません。
MATLABでは%しかコメントに使えないので、%を使うのがいいかもしれません。
PythonやRubyの言語に馴染んでいる方は、#の方が馴染みやすいかもしれませんが。
C言語、Python, Rubyなどの多くの言語で余りを求める記号が%ですが、Octaveでは%がコメントなので余りを求めるときはmod関数かrem関数を使います。mod関数とrem関数の挙動は基本的には同じすが、負の値が含まれてるときの挙動が異なります。mod関数はPythonやRubyなどの%であり、rem関数はC言語などの%です。
【参考】負数の剰余を計算してはならない - おともだちティータイム
練習：A - Welcome to AtCoder
[a b c s] = scanf("%d %d %d %s", 'C');
printf("%d %s\n", a+b+c, s)
Octaveには入力や出力の方法がいくつかありますが、最初はC言語風の書き方です。
C言語に馴染みのある人は、scanfやprintfという関数もご存知でしょう。
最後のfはformat(書式)の意味で、第1引数でformatを指定してます。
1行目は、1つずつスペースや改行区切りで入力を受け取っています。
"%d"とは、10進数(decimal number)の整数を読み込みです。
"%d %d"とすれば、10進数の整数を2つ読み込みます。
"%d %d %d %s"とすれば、10進数の整数を3つと文字列1つを読み込みます。
なお、"%s"は、string(文字列)のsです。
また、読み込み時は、"%d %d"のようにスペースがなくとも、"%d%d"でも問題ないです。
多くの言語がそうであるように、変数に代入するときは=を使います。
読み込んだ値は、上記のように[a b c s]という形で同時に代入できます。
[a,b,c,s]のようにカンマ区切りでも問題ないです。
ここで注意したいのは、文末のセミコロン;。
文末にセミコロン;がなくてもエラーにならず動きますが、セミコロン;がないと、最後に評価した式の変数とその値が出力されます。
デバッグには便利ですが、解答時の余計な出力は誤りとなるので、;を付け忘れないようにしましょう。
最終行は、printf関数を用いた出力です。
a+b+cの計算結果を%dの部分に表示し、次に変数sの値を%sの部分に表示しています。
なお、a+b+cは、ベクトル(行列)の形にしてsum([a b c])やsum([a;b;c])としても良いです。
最後の\nは、改行を表す特殊文字(エスケープシーケンス)。
本問は、無駄なスペースがあったり、最後に改行がないと誤答となるので注意。
なお、AtCoderは古い問題以外は、無駄なスペースがあっても最後に改行がなくとも正答と判定されているらしい。実際、本記事で紹介される以降の問題は、無駄なスペースがあっても許容される判定であり、出力にはdisp関数を用いている。disp関数は、正の数値の出力の際に、先頭に空白文字を一緒に出力し、最後に改行を出力する。
abc = scanf("%d");
s = scanf("%s");
printf("%d %s\n", sum(abc), s);
こんな風にscanf("%d")により、数値の部分までを縦ベクトルでまとめて入力してくれます。
そして、ベクトルを引数にした場合、sum関数でベクトル全要素の合計値を返してくれます。
また、input関数を用いた例もここで紹介します。
a = input('');
[b, c] = scanf("%d %d", 'C');
s = input('',"s");
printf("%d %s\n", a+b+c, s)
Pythonにも1行を読み込むinput関数がありますが、異なる点があります。
Octaveのinput関数は、第1引数を省略できません。
なお、第1引数は、ユーザーに入力を促すために出力される文字列を書くところです。
そして、input("")と書けば、文字列ではなく、数値として読みます。
なお、正確には、数値以外のデータも読み込めます。ここでいうデータとは、数値10、数式1+2、クオテーションで囲まれた文字列"Hello"、[]で囲まれたベクトル・行列[1 2; 3 4]、値の入っている変数piなどの形式のものです。コード上で代入できるものと考えて良さそうです。Python2の頃のinput関数の挙動と同じですね。
もし1行を文字列として受け取りたければ、第2引数にstring(文字列)の"s"を指定します。
第 1 問: ABC 086 A - Product (100 点)
[a b] = scanf("%d %d", 'C');
if mod(a * b, 2)
disp("Odd")
else
disp("Even")
end
入力は、練習問題で解いた通りです。
解法は、単純に、if文を用い2で割った余りで判定をして、条件分岐させて答えを出力しています。
mod(n,m)は、nをmで割った余りを返します。
本問では2で割るので、余りとして0 か 1を返してくれます。
多くのプログラミングではn % m でnをmで割った余りを計算できますが、Octaveにおいて%はコメントするための記号と解釈される。そのため、n % mと書いても、%以降の文は無視されてしまいます
そして、Octaveでは、0, 0.0, -0, 全ての要素が0の行列、""、''等が偽(False)の扱いです。
if文は、PythonやRubyのようにifのあとにスペースを書いてから条件式を書きます。ただ、C言語のようにifの直後に()を書いた中に条件式を書いても、問題なく動きます。if文は、Rubyのようにendで閉じます。なお、もし複数の条件式を書きたいときは、elseifです。ちなみに、C言語はelse if, Ruby/Crystalはelsif, Pythonはelif, PHPはelseifです。
最後に出力ですが、disp関数を用いています。dips関数は、最後に改行を出力してくれます。
第 2 問: ABC 081 A - Placing Marbles (100 点)
3つの解法を紹介します。
1つ目は、文字列として読み込み、0を削除することで、1を残した文字列の長さを数える方法です。
1つ目の解法は、大きくsizeを使う方法とlengthを使う方法にわかれます。
①size関数を用いる場合
s = input('','s');
size(strrep(s,'0',''))(2);
disp(ans)
②length関数を用いる場合
s = input('','s');
length(strrep(s,'0',''));
disp(ans)
1行を文字列として入力するときは、input関数で第2引数でstring(文字列)の's'を指定します。
strrep(s,'0','')は、文字列sの中にある'0'を''(空文字列)に置換した文字列を返す、つまり、文字列sの中にある'0'を削除した文字列を返しています。なお、strrepとはstring replaceの略でしょう。
1だけが残った文字列が返ってくるので、この文字列の長さを求めることで、答えが求まります。
文字列の長さの求め方は、size関数とlength関数の2通りあります。
①size関数を用いる場合
文字列を引数にsize関数を用いると、n文字の文字列を1行n列の行列(matrix)のように考え、行と列のサイズを1行2列のベクトルの形で返してきます。size関数で返ってきた行ベクトルの2列目が文字列のサイズなので、(2)という添字をつけて取り出します。
②length関数を用いる場合
size関数の大きい方の値が返る、と考えて良いでしょう。ベクトルや文字列だとわかっているものの長さを求めたい場合には、こちらを用いるとスッキリすると思います。
変数に明示的に代入しないと、自動的にansという変数に評価された値が入るので覚えておきましょう。
Octaveは行列や数値計算は得意ですが、文字列は得意ではないでしょう。
次の2つ目は、数学での理解に基づいた数値処理による解法です。
n = input("");
disp(mod(n,9))
- 求めたい数は、ある数字の1の数である。
- 0と1のみで構成された数字において、1の数と各桁の和は等しい。
- 各桁の和が最大でも8までであれば、各桁の和と各桁の和を9で割った余りは等しい。
- 最大でも各桁の和は111の3であるから、与えられる数字の各桁の和は、その和を9で割った余りと等しい。
- 一般に、ある数字を9で割った余りとその数の各桁の和を割った9で割った余りは等しい。
以上の事実から、求めたい1の数は、与えられた数字を9で割った余りと等しい。
そのため、mod関数かrem関数で、9で割った余りを求めて、それを答えています。
最後の3つ目は、数字を文字コードの数値で対応させることを利用した方法です。
競プロをやっていると、123, abc, ABCは文字コードが連続していることを利用すると書きやすいことがしばしばあります。
disp(sum(fgetl(0))-48*3)
fgetlは、ファイル(File)から1行(Line)を読み込む(get)関数。
あまり使わない独特な入力方法です。そもそもinput("",'s')と変わらないぽい。
fgetlの引数は読み込みたいファイル名を書くところですが、AtCoderではstdinか0を指定します。もともとstdinは予め0の値が入った変数です。詳しくないですが「標準の場所から入力して下さい」というおまじないです。
fgetlは、1行を読み込みます(改行は無視)。文字の横ベクトルの形で受け取ると考えて良いと思います。
sum関数は、ベクトルの要素を合計しますが、その要素が文字であれば文字コードの合計となります。
"0"の文字コードは48, "1"の文字コードは49です。そのため、読み込んだ数字の文字コードの合計から144(=48*3)を引いた数値が求めたい答えとなります。
第 3 問: ABC 081 B - Shift Only (200 点)
input("");
a = scanf("%d");
res = 0;
while mod(a,2) == 0
a /= 2;
++res;
end
disp(res)
入力部分は、input関数で1行の数値1つを読み込んだ後に、scanf("%d")で残り全ての整数をまとめて列ベクトルの形で受け取っています。
解法：
問題文通り、シミュレーションします。
数値が偶数かどうかは、mod関数かrem関数を用い2の余りを求め0と一致しているかどうかを見ます。
mod関数、rem関数は行列にも対応しているので、第1引数に列ベクトルaをいれます。演算子==を用いて0と比較し、一致していれば1(True)、一致してなければ0(False)を返しています。すべて1(True)のときのみ、Trueとなり、while文の中の処理文を実行していきます。処理文は、2で割って、答えの回数を増やします。
第 4 問: ABC 087 B - Coins (200 点)
[a,b,c,x]=scanf("%d%d%d%d","C");
r = x - ([0:a] * 500 + [0:b]' * 100);
res = nnz(r>=0 & r/50 <=c);
disp(res)
for文による三重ループや二重ループでも間に合いますが、for文を使わずに行列・ベクトルでまとめて処理するのがOctaveらしく速いコードになるので、二重ループのコードをfor文を使わずにまとめました。n行の列ベクトルとm列の行ベクトルに+演算子を使うと、それぞれの要素を全通り足し合わせたn行m列の行列が出来ます。コード上では、'を用いて行ベクトルを転置させて列ベクトルを作っています。
nnz関数は、number of nonzeroの略で、行列の非ゼロ要素の個数を返します。sum関数を2回使って求めても良いです。そのまま行列に1回だけsum関数を使うと、列方向に足した行ベクトルを返します。
for文による二重ループによる解法は、以下です。
[a,b,c,x]=scanf("%d%d%d%d","C");
0;
for i=0:a
for j=0:b
r = x - ( 500 * i + 100 * j );
if r >= 0 && r / 50 <= c
++ans;
end
end
end
disp(ans);
制約が50以下で高々132,651(=51^3)通りであるため、for文による三重ループによる全探索でも大丈夫です。ただ、二重ループも簡単なので、二重ループのコードを書きます。
0;とすることにより、変数ansに0が代入されます。
なお、ansという変数は特別で、後置インクリメントans++だとインクリメントできないので注意。
ただ、紹介しておいてアレですが、0;という書き方やansを変数に用いるのは挙動が謎なのであまり良くない気がします。第5問 ABC083_Bで、ans = 0;を0;と書き換えると、何故かREになります。
sからtまでのカウント変数をインクリメントさせながら、ループを回したいときは、for i = s:tという非常に簡潔な形で書けます。なお、s:tというのはrange型というデータの形で、データの型を調べたいときはtypeinfo関数を用いて調べることができます。s:d:kとすることで、kまでの初項s,公差dの有限個の等差数列を作ることができます。
disp(1:5) % => 1 2 3 4 5
disp(1:2:10) % => 1 3 5 7 9
disp(2:2:10) % => 2 4 6 8 10
disp(-2:2:9) % => -2 0 2 4 6 8
disp(0:-1:-3) % => 0 -1 -2 -3
disp(typeonfo(1:5)) % => range
余談ですが、公差0とすると空のmatrix(行列)が返ります。
第 5 問: ABC 083 B - Some Sums (200 点)
[n,a,b] = scanf("%d%d%d","C");
ans = 0;
for i = 1:n
t = i;
ds = 0;
while t
ds += rem(t,10);
t = floor(t/10);
end
if a <= ds && ds <= b;
ans += i;
end
end
disp(ans)
Octaveは文字列の処理など遅くTLEになるので、数値計算します。
(実際、base2dec関数やnum2str関数で数値と文字列の変換をするとTLEになる模様)
余りを求めるときは、mod関数かrem関数を用います。
また、/による四則演算は、整数同士の割り算であっても、小数点未満がでます。
そのため、floor関数によって切り捨ての処理を行っています。
第 6 問: ABC 088 B - Card Game for Two (200 点)
n = input('');
a = scanf("%d");
a = sort(a,'descend');
sum(a(1:2:n))-sum(a(2:2:n));
disp(ans)
AliceもBobも交互に出来るだけ大きいカードから取ります。
そのため、カードも降順(大きい順)にソート(並べ替え)します。
ベクトルaを降順ソートさせたいときは、a = sort(a,'descend');のようにします。
ベクトルaのi番目の数値は、a(i)の形で取り出します。
なお、C言語,Python,Rubyなどのメジャーな言語は配列の先頭を0番目として数えるzero-based(0オリジン)ですが、Octaveはone-based(1オリジン)で先頭を1番目として数えます。
s:d:kは、k以下の初項s・公差dの有限の等差数列を列挙します。range(範囲)というデータです。
1:2:nとすることでn以下の奇数を列挙、2:2:nとすることでn以下の偶数を列挙しています。
ベクトルは、このrange型も添字に取ることができます。a(1:2:n)とすることで、ベクトルaの奇数番目のみを抽出したベクトルを返します。このa(1:2:n)が先行のAliceの取れるカード、a(2:2:n)が後攻のBobが取れるカードとなります。
disp(1:5) % => 1 2 3 4
disp(1:2:10) % => 1 3 5 7 9
disp(2:2:10) % => 2 4 6 8 10
そして、ベクトルの要素の合計はsum関数で取れるため、sum関数で合計して返ってきた値がそれぞれの得点となります。コード上では、これらの差分を取り、明示的に何も変数に代入せず、ansという変数に答えを入れて、dips関数で表示しています。
降順ソートの部分について、別解を書きます。
d = flip(sort(a));
昇順にソートし、反転させて逆順にすることにより、降順にする方法です。
第2引数に何も指定しなかった場合のsort関数は、昇順のソートとなります。
そして、その昇順にソートしたベクトルに対してflip関数で反転させ降順にしています。
なお、flip関数は列ベクトルでも行ベクトルでも反転させますが、行列に対するflip関数は上下反転です。左右反転させたい場合には、fliplr関数を用います。最後の2文字はLeftとRightの頭文字ですね。
第 7 問: ABC 085 B - Kagami Mochi(200 点)
n = input('');
d = scanf("%d");
length(unique(d));
disp(ans)
入力部分は、input関数で1行の数値1つを読み込んだ後に、scanf("%d")で残り全ての整数をまとめて縦ベクトルの形で受け取っています。
解法は、unique関数でベクトルdの重複を削除したベクトルを受け取って、length関数でベクトルの長さを受け取ります。length関数ではなく、size関数を用いて、size関数の返り値に添字で列のサイズを取得する方法もありますが、length関数の方が見栄えが良いと思います。
評価した式が何にも代入されない場合、ansという変数に入るのがOctaveの特徴。
第 8 問: ABC 085 C - Otoshidama (300 点)
公式の解説にあるO(N^2)の解法でforループで二重ループを回すと、残念ながらTLEになります。
N枚全部1万円札でもYに足りない場合、N枚全部千円札でもYより多い場合など、明らかにあり得ないケースを最初に除外したりしてあがいてもTLEに……。
Octaveはforループを使わずにまとめて行列演算にすると速くなることがあるので、もしかしたらもっと速い書き方があるのかもしれないですが、O(N^2)の解法は諦めました。
↓
その代わり、O(N)やO(1)の解法では通ったため、O(N)の解法を書きたいと思います。
やや高度な数学的考察をしたO(1)の解法は、最終的に四則演算を駆使する形に過ぎないので省略します。
次のコードは、5000 * 9 = 10000 * 4 + 1000 * 5を利用したO(N)の解法です。
[n,y] = scanf("%d %d", "C");
y /= 1000;
for j = 0:8
for i = 0:floor(y/10)
c = y - ( 10 * i + 5 * j );
if c < 0
break
end
if i + j + c == n
disp([i j c])
quit
end
end
end
disp([-1 -1 -1])
5000 * 9 = 10000 * 4 + 1000 * 5 という等式を利用すると、五千円札9枚は一万円札と千円札に必ず交換できるため、
五千円札9枚以上の解が存在すれば、五千円札8枚以下の解も必ず存在することになります。
つまり、わざわざ五千円札9枚以上については探索をする必要がないため、五千円札は0 ~ 8枚以下で探索すれば良いのです。なんと。発想が必要なので、自力では結構難しいと思います。
コード上では、y /= 1000;と1000で割ることで単位を円→千円に変換し、扱う数値を小さくしてます。
小さい枚数から探索しており途中で目標金額y千円を超えてしまう場合、break文により1番内側のループを抜けています。
1つの答えを見つけたときは、答えを出力して、プログラムを終了させています。
プログラムを終了させるときは、quitかexitです。
第 9 問: ABC 049 C - Daydream (300 点)
s = input('','s');
s = strrep(s, "eraser", "x");
s = strrep(s, "erase", "x");
s = strrep(s, "dreamer", "x");
s = strrep(s, "dream", "x");
s = strrep(s, "x", "");
if isempty(s)
disp("YES")
else
disp("NO")
end
入力は、scanf("%s",'C');やinput('','s');で文字列として読み込みます
strlep関数を用い、与えられた文字列を4つのキーワードを適当な文字(列)への置換していきます。
注意したいのは、置換をする順番。
"eraser"→"erase"→"dreamer"→"dream"の順で削除しないと、消せたはずの"er"が残ったり、"dreamer"で先に削除してしまい"erase"や"eraser"の"er"を消しすぎたりということが起こりうる。
また、いきなり削除するのではなく適当な文字に置換する理由は、もしいきなり削除するとdreaerasemのように中央のeraseを削除した後に左右の文字が連結されて"dream"を削除することが出来てしまい誤った判定となるためです。なお、いったん適当な文字に置換しなくとも、そういったテストケースは入ってないため、嘘解法を通っちゃいます(あれ?)。
順番通りに適当な文字に置換し最後にその文字を削除し空文字列となれば判定は"YES"に。
空文字列かどうかの判定は、isempty関数やstrcmp関数を用いて判定します。
Octaveは、文字列の比較に==を使えないようでif文の条件式にs==''を使えないので注意。
第 10 問: ABC 086 C - Traveling (300 点)
a = dlmread(0,32,1,0);
d = abs(diff([0 0 0; a]));
r = d(:,1) - d(:,2) - d(:,3);
if min(r) < 0 || max(mod(r, 2)) == 1
disp("No")
else
disp("Yes")
end
TLEになりまくり大変だったのですが、最終的には綺麗にまとまったと思います。
単純に他の言語と同じようにforループ形式で実装をすると、残念ながらTLEになります。
Octaveはforループが遅いので、行列・ベクトル形式でまとめて処理することを心掛けます。
また、大量の入力データは、行列の形でまとめて受け取らないとTLEになります。
scanf("%d",[nr nc])形式やOctave独特なdlmread関数を用います。
dlmread関数は、入力通りの形で行列に落とし込んでくれる関数と考えて良いでしょう。
3通りの入力方法を書きます。
① dmlread(0);による方法
n = input("");
a = dlmread(0);
nを別個でinput("");やscanf("%d",'C');で受け取り、dmlread(0);と書いてN行3列のデータを受け取る方法です。第1引数は、ファイル名を書くところで、AtCoderでは標準入力であることを示すstdinか0を書きます。「標準の場所から入力して」というおまじないです。
② dmlread(0,32,1,0);による方法
a = dlmread(0,32,1,0);
nを用いていないため、dmlread関数でnも含めて受け取った後に、最初の1行目のnを無視して変数に代入できます。第1引数は先程と同じ標準入力であることを示すstdinか0を入れます。第2引数は区切り文字を入れるところで、ASCIIコードで32が空白文字であり、空白文字で区切って読み込むことになるため32を入れています。また、第3引数が無視をする行数で、1行目のnを無視して変数に入れるため1を入れています。第4引数は無視をする列数で、無視する列はないため0を入れています。
③ 行列の行数・列数を指定したscanf("%d",[nr,nc]);による方法
n = scanf("%d",'C');
a = scanf("%d", [3,n])';
scanf関数の第2引数を[3,n]とすることで、3行n列の行列の形で、1列目から詰める形で入力を受け取ります。
そして、'で転置しています。
入力の次ですが、forループだと遅いので、ベクトル演算・行列演算の形で計算します。
d = abs(diff([0 0 0; a]));
時間ごとの、経過時間、x方向の移動距離、y方向の移動距離を知りたい。
開始時点(t,x,y) = (0,0,0)の情報をいれて、差分をとります。
Octaveには便利なことに差分をとるdiff関数があります。
n+1行の行列を引数にとると、各行の差分をとったn行の行列を返してくれます
(なお、n+1列の行ベクトルを引数に取ると、n列の行ベクトルを返します)。
そして、差分をとったあと、abs関数でまとめて各要素の絶対値をとった行列を受け取っています。
いま、dはn行3列の行列です。
r = d(:,1) - d(:,2) - d(:,3);
d(:,1)は、全ての行の1列目のベクトルで、移動時間(＞0)
d(:,2)は、全ての行の2列目のベクトルで、x方向の最短の移動距離(絶対値)
d(:,3)は、全ての行の3列目のベクトルで、y方向の最短の移動距離(絶対値)
そして、旅行プランの移動時間から最短の移動時間を引いて余る時間を求めます。
rは、各回で寄り道しないで行ったときの余った時間の列ベクトルです。
もし負であれば、時間が足りないことを意味します。
if min(r) < 0 || max(mod(r, 2)) == 1
最短の移動距離のx,yの合計と移動時間が一致していれば、それで良い。
しかし、移動時間が足りてないところがあったり、余っている時間が2で割り切れなければちょうどよく寄り道できず、答えは"No"に。
min(r) < 0は、移動時間が足りてないのが1つでもあるという判定です。
また、max(mod(r, 2)) == 1は、1つでも2で割り切れない時間があるという判定です。
この他に、any関数を用いた判定があります。
if any(r< 0) || any(mod(r, 2))
r<0で、01で真偽値が入った行列(今回は縦ベクトル)が返るので、any(r<0)で1つでもマイナス値があれば=移動時間が足りなければを判定できます。また、any(mod(r,2))で、1つでも2で割り切れない時間があればを判定できます。
他の言語ではforループなどで時間の経過を見ていき、辿り着けないところがあれば"No"を出力してそこで打ち切るという解法が一般的かと思いますが、Octaveではまとめて処理します。
おわりに
疲れました。
冒頭でも書きましたが、趣味でプログラミング言語を齧ってるだけなので、不確かなこともあると思います。コメントなどでご指摘いただければと思います。