LoginSignup
16
12

More than 3 years have passed since last update.

@daigakupotato

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

Last updated at Posted at 2020-04-01

はじめに

@drkenさんの AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～　
をDartで解いてみました。
（2020/4/8: ABC086 C - Traveling の解説、コードを修正しました。）

AtCoderでは、次の言語アップデートでDartが使用可能になることが予定されており、
現在テストが行われています。

そのため、Language Test 202001において確認を行っています。

注意点

  • Dartの使用経験が浅いため書き方、説明が適切でない場合があります。そのような部分を発見した方は指摘していただけると幸いです。
  • 解法自体についてはほとんど解説を行いません。上記記事を参照ください。

ABC086 A - Product

import "dart:io";

void main(List<String> args) {
  List ab = stdin.readLineSync().split(" ").map((x) => int.parse(x)).toList();
  int product = ab[0] * ab[1];
  if (product % 2 == 0) {
    print("Even");
  } else {
    print("Odd");
  }
}

aとbの積の偶奇が判定できればOKです。
Dartでの標準入出力はstdin.readLineSync()を使えば良さそうです(公式ドキュメント)。
しかしながら、入力の行数が多い場合には他の方法を用いる必要があります。

ABC081-A - Placing Marble

import "dart:io";

main(List<String> args) {
  List<int> s = stdin.readLineSync().split("").map((x) => int.parse(x)).toList();
  int ans = s.reduce((a, b) => a + b);
  //int ans = s.fold(0, (a, b) => a + b);
  print(ans);
}

Dartにおいてリストの総和を求める場合には、上記のようにreduceを使うか、foldを使う方法があります。

reduceは初期値として最初の値を用いる一方で, foldは初期値を与える事ができます。

ABC081 B - Shift Only

import "dart:io";
import "dart:math";

main(List<String> args) {
  final int N = int.parse(stdin.readLineSync());
  List<int> A =
      stdin.readLineSync().split(" ").map((x) => int.parse(x)).toList();

  int ans = A.reduce(max);
  for (var x in A) {
    int count = 0;
    while (x % 2 == 0) {
      x ~/= 2;
      ++count;
    }
    ans = min(ans, count);
  }
  print(ans);
}

dart:mathをインポートすることで、min()などのメソッドも使用できます。
dart:math library

ABC087 B - Coins

import "dart:io";

main(List<String> args) {
  int A = int.parse(stdin.readLineSync());
  int B = int.parse(stdin.readLineSync());
  int C = int.parse(stdin.readLineSync());
  int X = int.parse(stdin.readLineSync());
  int ans = 0;
  for (var i = 0; i <= A; i++) {
    for (var j = 0; j <= B; j++) {
      for (var k = 0; k <= C; k++) {
        if (X == 500 * i + 100 * j + 50 * k) ans++;
      }
    }
  }
  print(ans);
}

全探索ですね。特に問題なく書けました。

ABC083 B - Some Sums

import "dart:io";

main(List<String> args) {
  List NAB = stdin.readLineSync().split(" ").map((x) => int.parse(x)).toList();
  int N = NAB[0];
  int A = NAB[1];
  int B = NAB[2];
  int ans = 0;
  for (var i = 1; i <= N; i++) {
    int tmp = i;
    int sum = 0;
    while (tmp > 0) {
      sum += tmp % 10;
      tmp ~/= 10;
    }
    if (sum >= A && sum <= B) ans += i;
  }
  print(ans);
}

1からNまでの整数について桁の和を求め、A以上B以下かを判定します。

ABC088 B - Card Game for Two

import 'dart:io';

main(List<String> args) {
  int N = int.parse(stdin.readLineSync());
  List<int> a =
      stdin.readLineSync().split(" ").map((x) => int.parse(x)).toList();

  a.sort((x, y) => y - x);
  int Alice = 0;
  int Bob = 0;
  for (var i = 0; i < N; i++) {
    if (i % 2 == 0) {
      Alice += a[i];
    } else {
      Bob += a[i];
    }
  }
  print(Alice - Bob);
}

降順にソートして奇数番目の和と偶数番目の和について差を求めます。

Dartにおけるsortに関して、公式ドキュメントには、

A Comparator function represents such a total ordering by returning
a negative integer if a is smaller than b,
zero if a is equal to b, and
a positive integer if a is greater than b.

と記載されており、
左側の値のほうが小さいとき（ソートの結果左側に来るとき）に負の値に、
逆のときに正の値を返す関数がComparatorとして指定できるようです。

そのため、
a.sort((x, y) => y - x);
上記のように書くことで降順のソートを行うことができます。

また、0を返したときにはソート後の順番は保証されないようです。

A Comparator may compare objects as equal (return zero), even if they are distinct objects. The sort function is not guaranteed to be stable, so distinct objects that compare as equal may occur in any order in the result:

sort method
Comparator typedef

ABC085 B - Kagami Mochi

import 'dart:io';

main(List<String> args) {
  int N = int.parse(stdin.readLineSync());
  Set d = {};

  for (int i = 0; i < N; i++) {
    d.add(int.parse(stdin.readLineSync()));
  }
  print(d.length);
}

入力の値を連想配列に入れて長さを出力します。

ABC085 C - Otoshidama

import 'dart:io';

main(List<String> args) {
  List NY = stdin.readLineSync().split(" ").map((x) => int.parse(x)).toList();
  int N = NY[0];
  int Y = NY[1];
  int k = 0;
  bool flag = false;
  for (var i = 0; i <= N; i++) {
    for (var j = 0; j <= N - i; j++) {
      k = N - i - j;
      if (i * 10000 + j * 5000 + k * 1000 == Y) {
        print([i, j, k].join(" "));
        flag = true;
        break;
      }
    }
    if (flag) break;
  }
  if (!flag) print("-1 -1 -1");
}

お札の組み合わせを全探索します。
空白区切りでの出力の綺麗な方法はjoinでいいのでしょうか・・・？

ABC049 C - Daydream

import 'dart:io';

main(List<String> args) {
  String S = stdin.readLineSync();
  int N = S.length;
  int id = N;
  bool flag = true;
  while (id > 1) {
    S = S.substring(0, id);
    if (S.endsWith("dreamer")) {
      id -= 7;
    } else if (S.endsWith("eraser")) {
      id -= 6;
    } else if (S.endsWith("dream") || S.endsWith("erase")) {
      id -= 5;
    } else {
      flag = false;
      break;
    }
  }
  if (flag) {
    print("YES");
  } else {
    print("NO");
  }
}

後ろからどの文字列と一致するかを調べて、文字数分前に進めていきます。
Dartでは文字列について、
substring(start, end)を使用して部分文字列の切り出しを行うことができます。
また、endsWith("hoge")を使用して、指定した文字列で終了しているか否かの判定を行うことができます。

ABC086 C - Traveling

まずは、上記で紹介した方法で実装を行ってみます。

import 'dart:io';

main(List<String> args) {
  int N = int.parse(stdin.readLineSync());
  List txy = [];

  int diff = 0;
  int dis = 0;
  bool flag = true;
  List<int> prev = [0, 0, 0];
  for (var i = 0; i < N; i++) {
    txy = stdin.readLineSync().split(" ").map((x) => int.parse(x)).toList();
    diff = txy[0] - prev[0];
    dis = (txy[1] - prev[1]).abs() + (txy[2] - prev[2]).abs();
    if (diff >= dis && (diff - dis) % 2 == 0) {
      prev = txy;
    } else {
      flag = false;
      break;
    }
  }
  if (flag) {
    print("Yes");
  } else {
    print("No");
  }
}

このような書き方をした場合には、入力がボトルネックとなって制限時間に間に合いません。

(2020/4/8: 修正)
このように、readLineSync()を複数行の入力に対して使用すると非常に遅いため、非同期に入力を受けてみます


import 'dart:convert';
import 'dart:io';
import 'dart:async';

main() async {
  var N = int.parse(stdin.readLineSync());
  var lines = stdin.transform(utf8.decoder).transform(LineSplitter());

  List<int> txy = [];
  bool flag = true;
  int count = 1;
  List<int> prev = [0, 0, 0];
  int diff = 0;
  int dis = 0;
  await for (var line in lines) {
    txy = line.split(" ").map((x) => int.parse(x)).toList();
    diff = (txy[0] - prev[0]);
    dis = ((txy[1] - prev[1]).abs() + (txy[2] - prev[2]).abs());
    if (diff >= dis && diff % 2 == dis % 2) {
      count++;
      if (count > N) break;
    } else {
      flag = false;
      break;
    }
  }
  if (flag) {
    print("Yes");
  } else {
    print("No");
  }
}

このように、Streamとasync/awaitを使用することで、非同期に入力を処理することができます。
入力が終わった段階でbreakを行うことで、入力の受け付けを終了することができます。

非同期処理を行うことで、Dartでも大量の入力を処理することができます。
Judge System Update Test Contest 202004において確認を行ったところ、readLinesync()を使用した場合には、
本問のように行数が多い場合だけでなく、１行に大量の入力が与えられる場合にも非常に時間がかかるようです。

おわりに

Dartについてもっと色々な書き方を勉強して、他の問題についても挑戦してみたいと思います。
言語アップデートが楽しみです。

16
12
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
16
12