LoginSignup
4
1

More than 3 years have passed since last update.

@Mopepe51(雪下)

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

Last updated at Posted at 2020-09-15

はじめに

誰もやってなさそうな言語で競プロをやるシリーズ第5弾1、AtCoder Beginners Selection の問題2を、プロトタイプベースオブジェクト指向プログラミング言語「Io」で解いてみました。

競プロを知っている方向けのIoの布教記事となります。

現在のところ Io はAtCoderで使用可能な言語に含まれていないのでローカル環境でテストだけしています。
使用環境はUbuntu 18.04 LTS on WSL。環境構築については以前記事にしたのでこちらをご覧ください3。

Ioの解説

Ioは純粋なプロトタイプベースオブジェクト指向言語です。Ioの基礎的な文法は非常に単純なので、同様にプロトタイプベースで動作するJavascriptやLuaなどの言語の理解に役立つのではないかと思います。

Ioはすべての動作が「オブジェクトへのメッセージ4送信」だけで成りたっています。
オブジェクトはメッセージを受け取るとメッセージと名前の一致する「スロット」を検索します。該当するスロットが見つかればそのスロットに対応するメソッドを実行、戻り値があれば値を返します。
オブジェクトを実質的に {スロット名→その値} というハッシュテーブルだとみなすとわかりやすいでしょう。

各オブジェクトにはそのオブジェクトの「プロトタイプ」が設定されており、受け取ったメッセージに該当するスロットが存在しなければ自身のプロトタイプにメッセージをたらい回しします。

例として"Hello, world!" printという文を見てみましょう。
"Hello, world!"は文字列リテラルですが、これはSequenceというオブジェクトをプロトタイプに持ち、スロットは何もないオブジェクトです。

Io> "Hello, world!" slotNames
==> list()
// slotNamesでスロットの一覧が取得される

これにprintというメーッセージが送られていますが、printというスロットは無いのでプロトタイプのSequenceにprintを送ります。
Sequenceは

Sequence slotNames
==> list(asJson, linePrint, duplicateIndexes, pathComponent, urlDecoded, removeSeq, bitwiseAnd, asCapitalized, log, uppercase, findSeq, replaceSeq, logicalOr, +, beginsWithSeq, containsAnyCaseSeq, square, sizeInBytes, cos, byteAt, asIoPath, removeEvenIndexes, <=, endsWithSeq, validEncodings, between, preallocateToSize, asBinarySignedInteger, sqrt, asDecodedList, size, repeated, isSymbol, interpolate, setSize, copy, removeSlice, beforeSeq, cloneAppendSeq, asLowercase, alignLeftInPlace, bitCount, afterSeq, findNthSeq, abs, lstrip, asBuffer, log10, max, slice, z, print, replaceFirstSeq, translate, cPrint, <, at, reverseFindSeq, appendSeq, encoding, acos, product, atPut, setItemsToDouble, asOSPath, Max, foreach, -, stringByExpandingTilde, setItemType, asSymbol, sinh, removeAt, set, sum, betweenSeq, /=, inclusiveSlice, clipAfterSeq, addEquals, atan, reverse, unpack, splitAt, setZ, asNumber, withStruct, removeOddIndexes, alignLeft, ceil, bitwiseNot, setItemsToLong, itemCopy, orderedSplit, tanh, asList, asFixedSizeType, removeSuffix, unescape, with, removeLast, >=, asBase64, validItemTypes, asMutable, normalize, exclusiveSlice, replaceMap, inSlice, asUCS4, x, floor, clipBeforeSeq, isUppercase, percentEncoded, lowercase, rootMeanSquare, asUppercase, alignCenter, sort, convertToFixedSizeType, asFile, append, isZero, empty, +=, toBase, rangeFill, cloneAppendPath, asin, sequenceSets, asStruct, zero, lastPathComponent, setEncoding, min, occurancesOfSeq, convertToItemType, split, itemSize, Min, capitalize, y, asSimpleString, strip, pack, findSeqs, percentDecoded, isEmpty, setY, *=, >, -=, asBinaryNumber, contains, /, splitNoEmpties, asBinaryUnsignedInteger, .., asUTF8, itemType, justSerialized, cosh, makeFirstCharacterLowercase, atInsertSeq, fromBase, clipBeforeEndOfSeq, sin, bitAt, meanSquare, negate, mean, prependSeq, containsSeq, slicesBetween, removePrefix, *, reverseInPlace, asString, isEqualAnyCase, whiteSpaceStrings, escape, bitwiseXor, alignRight, tan, urlEncoded, leaveThenRemove, interpolateInPlace, fileName, isLowercase, isMutable, fromBase64, distanceTo, insertSeqEvery, clipAfterStartOfSeq, hash, appendPathSeq, pathExtension, asHex, asMessage, makeFirstCharacterUppercase, exSlice, dotProduct, bitwiseOr, asUCS2, rstrip, setX)

のように文字列の様々な機能が実装されたスロットが存在します。ここにprintスロットも存在し、自身を標準出力に出力するメソッドが対応していますので、Hello, world!が出力されます。

メソッドによって値が返されればそのオブジェクトに更にメッセージを送ることでメソッドチェーンが実現可能です。例：9. ABC 049 C - Daydream

文字列にtypeというメッセージを送ると"Sequence"と帰ってきます。つまり文字列のtypeは「Sequence」なのですが、これはSequenceクラスがあるわけではありません。Ioに「クラス」と「インスタンス」の区別はなく、全て等しく「プロトタイプ」です。

Io>"Hello, world!" type
==> Sequence

では何故"Hello, world!" typeは"Sequence"なのかというとSequenceがスロットtypeを持っていてその値が"Sequence"だからです。Ioでは大文字で始まるオブジェクトを作成すると自動でその変数名を持ったtypeスロットが作成されます。これであるオブジェクトのクローン(そのオブジェクトをプロトタイプに持つ新たなオブジェクト)を小文字で作れば「子」は同じtypeを持つようになるので「種類」が規定され、大文字でクローンすればメソッドを継承した新しい「種類」ができるという意味をつけ、判別しやすくしていますが、結局操作の方法は同じです。

ジャッジ方法

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


$ EXE="hoge"
$ PTH="fuga"
$ (/usr/bin/time -f "${EXE} ${PTH}: %U s, %M kB" io ${EXE}.io < ../testcases/${EXE}/in/${PTH}.txt) 2>> ./resultout.txt | diff - ../testcases/${EXE}/out/${PTH}.txt

のようにdiffで正答と比較し、timeで実行時間と使用メモリをチェックしていきます。timeの出力は標準エラー出力に出るので、うまいことdiffの結果はコンソールに、timeの結果は./res/"${EXE}-${PTH}_out.txt"に

0 ex1: 0.01s, 5000 kB

のように出力されます。diffの出力なし、かつtimeの結果が制約以内ならばACとみなします。（一部答えが複数存在するものがあるのでこれは適宜対応）

解法

0. practice contest A - Welcome to AtCoder 

readln := method(
    File standardInput readLine
)
a := readln asNumber
l := readln split
b := l at(0) asNumber
c := l at(1) asNumber
s := readln
writeln(a + b + c, " ", s)

まずは出入力の確認ということで0番。ちょっと長いので一行読み込みのメソッドを作成しました。

トップレベルに定義した変数は実はプロトタイプチェーンの一番根本のオブジェクトである「Objectのプロトタイプ」のスロットとして定義されています。:=はスロット作成の演算子です。

Io> Object proto
==>  Object_0x68c6d0:
  Lobby            = Object_0x68c6d0
  Protos           = Object_0x68c470
  _                = Object_0x68c6d0
  exit             = method(...)
  forward          = method(...)
  set_             = method(...)

だったのがプログラムの実行後は

Io> Object proto
==>  Object_0x68c6d0:
  Lobby            = Object_0x68c6d0
  Protos           = Object_0x68c6d0
  _                = Object_0x68c6d0
  a                = 1
  b                = 2
  c                = 3
  exit             = method(...)
  forward          = method(...)
  l                = list(2, 3)
  readln           = method(...)
  s                = "test"
  set_             = method(...)

のようにプログラム中で定義した変数がスロットに加わっていることがわかります。6

引数0の関数呼び出しではメンバ変数のようにカッコが要らないのが特徴的ですね。
配列のインデックスアクセスにはat(1引数メソッド)、文字列の結合は..(2項演算子7)を使います。

結果： AC / 0.04s, 5984 kB

個別ケース結果
0 ex1: 0.04 s, 5988 kB
0 ex2: 0.04 s, 5984 kB

1. ABC 086 A - Product 

l := File standardInput readLine split
a := l at(0) asNumber
b := l at(1) asNumber
if(a * b % 2 == 0) then(
  "Even" println
) else(
  "Odd" println
)

もちろん標準入力読み込みのメソッドを作らず1行で書くこともできます。

条件分岐はこんな感じに書きます。
ifもObjectのスロットに定義されているメソッドです。徹底していますね。

標準出力は#0ではwriteln(hoge)と書きましたが、<Object> printlnのようにオブジェクトが持っているprintlnメソッドを呼び出すことでも可能です。

結果： AC / 0.06 s, 5996 kB

個別ケース結果
1 0_000: 0.06 s, 5996 kB
1 0_001: 0.04 s, 5996 kB
1 1_002: 0.04 s, 5996 kB
1 1_004: 0.04 s, 5992 kB
1 1_005: 0.04 s, 5992 kB
1 1_006: 0.04 s, 5996 kB

2. ABC 081 A - Placing Marbles 

s := File standardInput readLine
r := 0
for(i, 0, s size - 1,
  r = r + if(s at(i) == "1" at(0), 1, 0)
)
r println

繰り返しはこんな感じ。
ifは3つ引数を与えると第1,2引数の値を返す、つまりif式として使うことができます。
ちなみにforも式で、繰り返し最後の文の値を返します。

結果： AC / 0.03 s, 5988 kB

個別ケース結果
2 00_example_01: 0.01 s, 5988 kB
2 00_example_02: 0.03 s, 5984 kB
2 01: 0.03 s, 5988 kB
2 02: 0.01 s, 5988 kB
2 03: 0.01 s, 5988 kB
2 04: 0.01 s, 5988 kB
2 05: 0.03 s, 5988 kB
2 06: 0.00 s, 5992 kB

3. ABC 081 B - Shift Only 

readln := method(
  File standardInput readLine
)
n := readln asNumber
l := readln split
a := list()
m := 100
for(i, 0, n - 1,
  a := l at(i) asNumber; c := 0;
  while(a % 2 == 0,
    a = a / 2 floor; c = c + 1
  );
  m = m min(c)
)
m println

forの第4引数のところのように、式を複数続けて実行するときは;で繋ぎます。

結果： AC / 0.06 s, 6016 kB

個別ケース結果

3 sample1: 0.04 s, 6012 kB
3 sample2: 0.04 s, 6016 kB
3 sample3: 0.04 s, 6016 kB
3 1: 0.04 s, 6016 kB
3 2: 0.04 s, 6008 kB
3 3: 0.04 s, 6012 kB
3 4: 0.04 s, 6012 kB
3 5: 0.06 s, 6012 kB
3 6: 0.04 s, 6012 kB
3 7: 0.04 s, 6012 kB

4. ABC 087 B - Coins 

readln := method(
  File standardInput readLine
)
a := readln asNumber
b := readln asNumber
c := readln asNumber
x := readln asNumber / 50
result := 0
for(i, 0, a,
  for(j, 0, b,
    if(0 <= x - i * 10 - j * 2 and x - i * 10 - j * 2 <= c, result = result + 1)
  )
)
result println

結果： AC / 0.06 s, 5988 kB

個別ケース結果
4 sample01: 0.04 s, 5988 kB
4 sample02: 0.04 s, 5992 kB
4 sample03: 0.04 s, 5988 kB
4 01: 0.04 s, 5988 kB
4 02: 0.04 s, 5988 kB
4 03: 0.04 s, 5988 kB
4 04: 0.06 s, 5988 kB
4 05: 0.04 s, 5988 kB
4 06: 0.04 s, 5984 kB
4 07: 0.06 s, 5984 kB
4 08: 0.03 s, 5988 kB
4 09: 0.04 s, 5988 kB
4 10: 0.04 s, 5988 kB

5. ABC 083 B - Some Sums 

ketawa := method(num,
  num asString asList map(asNumber) sum
)
l := File standardInput readLine split
n := l at(0) asNumber
a := l at(1) asNumber
b := l at(2) asNumber
result := 0
for(i, 1, n,
  w := ketawa(i)
  if(a <= w and w <= b, result = result + i)
)
result println

ketawaは数字の各桁の和を求めるメソッドです。いい感じにメソッドチェーンがつながって気持ちいいですね。

結果： AC / 0.59 s, 6296 kB

個別ケース結果
5 s1: 0.06 s, 5988 kB
5 s2: 0.04 s, 5988 kB
5 s3: 0.04 s, 5992 kB
5 01: 0.59 s, 6280 kB
5 02: 0.23 s, 6292 kB
5 03: 0.56 s, 6292 kB
5 04: 0.59 s, 6292 kB
5 05: 0.50 s, 6288 kB
5 06: 0.53 s, 6284 kB
5 07: 0.56 s, 6296 kB
5 08: 0.48 s, 6288 kB

6. ABC 088 B - Card Game for Two 

readln := method(
  File standardInput readLine
)
n := readln asNumber
lst := readln split map(asNumber) sort reverse
alice := 0
bob := 0
for(i, 0, n - 1,
  if(i % 2 == 0,
    alice = alice + lst at(i),
    bob = bob + lst at(i)
  )
)
(alice - bob) println

listの各要素に処理を加え、戻り値のリストを得ることができる"高階関数"8、mapも存在します。

結果： AC / 0.06 s, 6012 kB

個別ケース結果
6 ex1: 0.06 s, 6004 kB
6 ex2: 0.03 s, 6008 kB
6 ex3: 0.04 s, 6012 kB
6 random: 0.04 s, 6008 kB

7. ABC 085 B - Kagami Mochi 

readln := method(
  File standardInput readLine
)
n := readln asNumber
lst := list()
for(i, 0, n - 1,
  lst push(readln asNumber)
)
lst unique size println

listオブジェクトのuniqueメソッドは重複を取り除いたリストを返します。

結果： AC / 0.04 s, 5992 kB

個別ケース結果
7 ex1: 0.04 s, 5988 kB
7 ex2: 0.04 s, 5992 kB
7 ex3: 0.04 s, 5984 kB
7 random: 0.04 s, 5988 kB

8. ABC 085 C - Otoshidama 

l := File standardInput readLine split
n := l at(0) asNumber
y := l at(1) asNumber
result := "-1 -1 -1"
for(i, 0, n,
  for(j, 0, n - i,
    if(10 * i + 5 * j + n - i - j == y / 1000,
      result = i asString .. " " .. j asString .. " " .. (n - i - j) asString
    )
  )
)
result println

$O(N^2)$なので間に合う想定の解なのですが、Io自体の速度の問題でsample4では12秒もかかってしまいました。

結果： TLE / 11.79 s, 5992 kB

個別ケース結果
8 ex1: 0.04 s, 5988 kB
8 ex2: 0.03 s, 5980 kB
8 ex3: 2.81 s, 5992 kB
8 ex4: 11.79 s, 5988 kB

仕方がないので$O(1)$の解法で解きました。参考

l := File standardInput readLine split
n := l at(0) asNumber
y := l at(1) asNumber
t := (y - 1000 * n) / 1000
a := t % 4
b := (t - 9 * (t % 4)) / 4
kmin := list((- a / 4) ceil, ((a + b - n) / 5) ceil) max
kmax := (b / 9) floor
if(kmin <= kmax,
  (4 * kmin + a) asString .. " " .. (-9 * kmin + b) asString .. " " .. (n - 4 * kmin - a + 9 * kmin - b) asString,
  "-1 -1 -1") println

結果： AC / 0.04 s, 6012 kB

個別ケース結果
8_2 ex1: 0.04 s, 6012 kB
8_2 ex2: 0.04 s, 6004 kB
8_2 ex3: 0.04 s, 6008 kB
8_2 ex4: 0.04 s, 6012 kB

9. ABC 049 C - Daydream

この問題では eraser→erase→dreamer→dream の順で置換しすると判定ができます。置換があれば一番簡単なのでまずはこれで解いてみます。

if(File standardInput readLine asMutable replaceSeq("eraser", "!") replaceSeq("erase", "!") replaceSeq("dreamer", "!") replaceSeq("dream", "!") replaceSeq("!", "") == "", "YES", "NO") println

そのままの文字列はImmutableSequenceなのでreplaceSeqが使えません。asMutableでMutableば文字列に変換します。

結果： AC / 0.18 s, 6088 kB

個別ケース結果
9 subtask0_0: 0.04 s, 5980 kB
9 subtask0_1: 0.03 s, 5980 kB
9 subtask0_2: 0.04 s, 5984 kB
9 subtask1_0: 0.14 s, 6080 kB
9 subtask1_10: 0.15 s, 6084 kB
9 subtask1_11: 0.17 s, 6088 kB
9 subtask1_12: 0.17 s, 6084 kB
9 subtask1_13: 0.17 s, 6084 kB
9 subtask1_14: 0.09 s, 6084 kB
9 subtask1_15: 0.12 s, 6084 kB
9 subtask1_1: 0.12 s, 6080 kB
9 subtask1_2: 0.04 s, 6080 kB
9 subtask1_3: 0.17 s, 6080 kB
9 subtask1_4: 0.17 s, 6076 kB
9 subtask1_5: 0.18 s, 6080 kB
9 subtask1_6: 0.17 s, 6080 kB
9 subtask1_7: 0.17 s, 6076 kB
9 subtask1_8: 0.17 s, 6080 kB
9 subtask1_9: 0.17 s, 6080 kB

公式解説の通りに、後ろから順に判定していく解法もあります。

s := File standardInput readLine
len := s size
i := len
flag := true
while(i > 0,
  if("erase" == s exSlice(i - 5, i)) then(
    i = i - 5
  ) elseif("eraser" == s exSlice(i - 6, i)) then(
    i = i - 6
  ) elseif("dream" == s exSlice(i - 5, i)) then(
    i = i - 5
  ) elseif("dreamer" == s exSlice(i - 7, i)) then(
    i = i - 7
  ) else(
    flag = false;
    break
  )
)
if(flag, "YES", "NO") println

部分文字列はexSliceで取得します。sliceも存在しますがdeprecatedだそうです。

結果： AC / 0.07 s, 6248 kB

個別ケース結果
9 subtask0_0: 0.04 s, 5980 kB
9 subtask0_1: 0.04 s, 5984 kB
9 subtask0_2: 0.04 s, 5980 kB
9 subtask1_0: 0.07 s, 6216 kB
9 subtask1_10: 0.07 s, 6224 kB
9 subtask1_11: 0.06 s, 6248 kB
9 subtask1_12: 0.04 s, 6220 kB
9 subtask1_13: 0.07 s, 6248 kB
9 subtask1_14: 0.06 s, 6248 kB
9 subtask1_15: 0.07 s, 6220 kB
9 subtask1_1: 0.06 s, 6216 kB
9 subtask1_2: 0.07 s, 6216 kB
9 subtask1_3: 0.06 s, 6220 kB
9 subtask1_4: 0.06 s, 6216 kB
9 subtask1_5: 0.06 s, 6216 kB
9 subtask1_6: 0.06 s, 6216 kB
9 subtask1_7: 0.06 s, 6220 kB
9 subtask1_8: 0.06 s, 6212 kB
9 subtask1_9: 0.06 s, 6220 kB

10. ABC 086 C - Traveling 

readln := method(
  File standardInput readLine
)
n := readln asNumber
preT := 0
preX := 0
preY := 0
flag := true
for(i, 1, n,
  l := readln split;
  t := l at(0) asNumber;
  x := l at(1) asNumber;
  y := l at(2) asNumber;
  dt := t - preT;
  dl := (x - preX) abs + (y - preY) abs;
  if(dl > dt or dl % 2 != dt % 2, flag = false)
)
if(flag, "Yes", "No") println

この問題でも制約を超えてしまいました。
頑張って並列化すれば速くなるんじゃないかとも思ったんですが、どうも入力の読み込みにほとんどの時間がかかっているようです。IoなのにIOが遅い こればっかりはちょっと手がつけられないので諦めました……

結果： TLE / 3.06 s, 6184 kB

個別ケース結果
10 0_000: 0.04 s, 5996 kB
10 0_001: 0.06 s, 5980 kB
10 0_002: 0.06 s, 6000 kB
10 1_003: 0.04 s, 5992 kB
10 1_004: 3.06 s, 6108 kB
10 1_005: 3.00 s, 6132 kB
10 1_006: 2.96 s, 6184 kB
10 1_006: 3.00 s, 6524 kB
10 1_007: 0.50 s, 6184 kB
10 1_008: 0.03 s, 6000 kB
10 1_009: 0.67 s, 6188 kB
10 1_010: 0.06 s, 5996 kB
10 1_011: 0.42 s, 6184 kB
10 1_012: 0.04 s, 6416 kB
10 1_012: 0.07 s, 6420 kB

まとめ

ちょっと遅いですがなかなかおもしろい言語です。
競プロではなかなか使う機会がありませんが、Ioは非同期処理がとても得意です。（例えばメッセージに@をつけるだけでFutureオブジェクトを生成し、オブジェクトをアクターとするのでとても簡単に書けます。）
プログラミングの基礎を学ぶ言語としては大変ポテンシャルのある言語なんじゃないかと思います。

惜しむらくは異常にググラビリティが低いこと、そして流行ったのがそこそこ昔（2000年代初頭）なため、当時あった日本語文献もほぼ散逸してしまい調べるのがとても大変なことです。
本記事も 『7つの言語 7つの世界』（オーム社、B. A. Tate著、まつもとゆきひろ 監訳、田和勝 訳）と「Rubyist のための他言語探訪 【第 3 回】 Io」を頼りに公式ドキュメントをひーこら読みながら書きました（公式ドキュメントもそんなに詳しくない）。

AtCoderには無いけどAnarGolfにはジャッジがあるのでやってみてください。

  1. 過去の記事は 「AtCoderに登録したら解くべき精選過去問10をTeXで解いてみた」、「〃JSFuck」、「〃プロデル」、「〃LabVIEW」となっています ↩

  2. AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～(@drken さん) にて紹介されている過去問題 ↩

  3. 環境構築記事の通り、プロジェクトをクローンしてきてmakeする方法だと一部パッケージが正常に読み込めないため「#バイナリからのインストール」の項に従ってインストールしています。 ↩

  4. 以下太字はテクニカルタームとしての語を意味します。 ↩

  5. 使用したテストケースデータは https://github.com/Yukishita26/abs-solve/tree/master/testcases にまとめました。 ↩

  6. つまりビルトインのオブジェクトに変更を加えられるということです。Rubyのオープンクラスのようなメタプログラミングが可能です。 ↩

  7. 「2項演算子」は1引数メソッドのシュガーシンタックスです。 ↩

  8. 実際の処理としては各要素に、引数に与えた「メッセージ」を送っているだけなので関数型言語のように関数オブジェクトを扱っているわけではありません。 ↩

4
1
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
4
1