Résolution de la 4ème question d'AtCoder ARC104 avec Scala, C ++, Java, Ruby, Perl, Elixir. J'ai pu comparer la vitesse de traitement pour chaque langue.
| Langue | résultat |
|---|---|
| Scala | TLE |
| C++ | AC 1830ms |
| Java | AC 2995ms |
| Scala de type Java | AC 2991ms |
| Ruby | TLE |
| Perl | TLE |
| Elixir | TLE |
La relation entre la sélection de la langue et la vitesse de traitement dans la programmation concurrentielle a été mentionnée dans le tweet suivant.
https://twitter.com/chokudai/status/1171321024224186369
Selon ce tweet, C ++ et Java sont corrects, mais d'autres langages semblent être durs pour les problèmes de calcul exigeants.
Pendant la compétition, il a fallu du temps pour trouver une solution, et après l'avoir su, je l'ai écrite dans Scala, mais il a fallu du temps pour corriger le bogue et je n'ai pas pu atteindre AC (bonne réponse). J'ai continué après la compétition, mais je n'ai pas pu me débarrasser du TLE avec un temps d'exécution limité à 4 secondes.
Quand j'ai abandonné et écrit la même logique en C ++, je pouvais facilement obtenir AC.
Donc, je l'ai écrit dans différentes langues et comparé si je pouvais obtenir AC.
Scala était TLE au début, mais si j'écrivais Scala qui traduisait Java après avoir pris AC avec Java, je pourrais obtenir AC avec Scala.
Le reste de cet article est le code source de chaque langue.
Scala
C'est un code Scala de type Java à mi-chemin, comme utiliser ʻArray`, mais c'est un code que j'ai abandonné parce que je ne pouvais pas résoudre TLE.
object Main extends App {
val sc = new java.util.Scanner(System.in);
val n, k, m = sc.nextInt();
val table = (0 until n).map(i => Array.fill(i*(i+1)*k/2+2)(0));
table(0)(0) = 1;
(1 until n).foreach { i =>
val j_max = i * (i+1) * k / 2;
val t1 = table(i - 1);
val t2 = table(i);
(0 to j_max).foreach { j =>
val a1 = (((j - (i - 1) * i * k / 2) + i - 1) / i) max 0;
val a2 = (j / i) min k;
val s = (a1 to a2).map { a =>
t1(j - a * i).toLong;
}.sum % m;
t2(j) = s.toInt;
}
}
val table2 = Array.fill(n+1)(0);
(1 to n).foreach { x =>
if (x <= (n + 1) / 2) {
val (n1, n2) = (x - 1, n - x);
val s = (0 to (n1 * (n1+1) * k / 2)).map { i =>
table(n1)(i).toLong * table(n2)(i) % m;
}.sum % m;
val answer = ((m.toLong + s * (k+1) - 1) % m).toInt;
table2(x) = answer;
println("%d".format(answer));
} else {
val answer = table2(n + 1 - x);
println("%d".format(answer));
}
}
}
Après avoir obtenu AC avec Java, qui sera décrit plus tard, lorsque j'ai écrit un code qui traduisait Java en Scala, c'était 2991ms, ce qui est presque le même que Java. La conclusion est que Java est assez fin pour écrire un tel code dans Scala et que Scala n'est pas adapté aux problèmes exigeants en termes de calcul. Scala est facile à écrire pour moi, je vais donc continuer à l'utiliser correctement.
object Main extends App {
val sc = new java.util.Scanner(System.in);
val n, k, m = sc.nextInt();
val table = new Array[Array[Int]](n);
table(0) = new Array[Int](2);
table(0)(0) = 1;
var i: Int = 1;
while (i < n) {
val j_max = i * (i+1) * k / 2;
val t1 = table(i - 1);
val t2 = new Array[Int](i*(i+1)*k/2+2);
table(i) = t2;
var j: Int = 0;
while (j <= j_max) {
val a1 = (((j - (i - 1) * i * k / 2) + i - 1) / i) max 0;
val a2 = (j / i) min k;
var s: Long = 0L;
var a: Int = a1;
while (a <= a2) {
s += t1(j - a * i).toLong;
a += 1;
}
t2(j) = (s % m).toInt;
j += 1;
}
i += 1;
}
val table2 = new Array[Int](n+1);
var x: Int = 1;
while (x <= n) {
if (x <= (n + 1) / 2) {
val (n1, n2) = (x - 1, n - x);
var s: Long = 0L;
var i: Int = 0;
var max = (n1 * (n1+1) * k / 2);
while (i <= max) {
s += table(n1)(i).toLong * table(n2)(i) % m;
i += 1;
}
s = s % m;
val answer = ((m.toLong + s * (k+1) - 1) % m).toInt;
table2(x) = answer;
println("%d".format(answer));
} else {
val answer = table2(n + 1 - x);
println("%d".format(answer));
}
x += 1;
}
}
C++
Quand j'ai réécrit la même logique en C ++, j'ai obtenu AC en 1830ms.
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, k, m;
cin >> n >> k >> m;
vector<vector<int>> table(n);
table[0] = vector<int>(2);
table[0][0] = 1;
for (int i = 1; i < n; i++) {
auto t1 = table[i-1];
auto t2 = vector<int>(i*(i+1)*k/2+2);
int j_max = i * (i+1) * k / 2;
for (int j = 0; j <= j_max; j++) {
int a1 = ((j - (i - 1) * i * k / 2) + i - 1) / i;
if (a1 < 0) a1 = 0;
int a2 = j / i;
if (a2 > k) a2 = k;
long s = 0;
for (int a = a1; a <= a2; a++) {
s += t1[j - a * i];
}
s = s % m;
t2[j] = (int)s;
}
table[i] = t2;
}
auto table2 = vector<int>((n + 1) / 2 + 1);
for (int x = 1; x <= (n + 1) / 2; x++) {
int n1 = x - 1;
int n2 = n - x;
long s = 0;
for (int i = 0; i <= n1 * (n1+1) * k / 2; i++) {
s += (long)table[n1][i] * table[n2][i] % m;
}
int answer = (int)(((long)m + s * (k+1) - 1) % m);
table2[x] = answer;
printf("%d\n", answer);
}
for (int x = (n + 1) / 2 + 1; x <= n; x++) {
printf("%d\n", table2[n + 1 - x]);
}
}
Java
J'ai obtenu AC avec C ++ et j'ai trouvé que la solution était correcte, alors je l'ai écrite en Java ensuite. J'ai eu AC en 2995ms. Plus lent que C ++, mais plus rapide que Scala sur la même JVM. Je pensais que ce qui peut être fait avec JVM devrait être possible avec Scala s'il est écrit d'une manière Java, mais comme mentionné ci-dessus, AC a également été obtenu avec Scala.
import java.util.Scanner;
class Main {
public static void main(String[] args) {
var sc = new Scanner(System.in);
var n = sc.nextInt();
var k = sc.nextInt();
var m = sc.nextInt();
var table = new int[n][];
table[0] = new int[2];
table[0][0] = 1;
for (int i = 1; i < n; i++) {
var t1 = table[i-1];
var t2 = new int[i*(i+1)*k/2+2];
int j_max = i * (i+1) * k / 2;
for (int j = 0; j <= j_max; j++) {
int a1 = ((j - (i - 1) * i * k / 2) + i - 1) / i;
if (a1 < 0) a1 = 0;
int a2 = j / i;
if (a2 > k) a2 = k;
long s = 0;
for (int a = a1; a <= a2; a++) {
s += t1[j - a * i];
}
s = s % m;
t2[j] = (int)s;
}
table[i] = t2;
}
var table2 = new int[(n + 1) / 2 + 1];
for (int x = 1; x <= (n + 1) / 2; x++) {
int n1 = x - 1;
int n2 = n - x;
long s = 0;
for (int i = 0; i <= n1 * (n1+1) * k / 2; i++) {
s += (long)table[n1][i] * table[n2][i] % m;
}
int answer = (int)(((long)m + s * (k+1) - 1) % m);
table2[x] = answer;
System.out.printf("%d\n", answer);
}
for (int x = (n + 1) / 2 + 1; x <= n; x++) {
System.out.printf("%d\n", table2[n + 1 - x]);
}
}
}
Ruby
C'était TLE.
n, k, m = gets.strip.split(" ").map(&:to_i)
table = [[1]]
for i in 1..n-1
t1 = table[i-1]
t2 = []
for j in 0 .. i * (i+1) * k / 2
a1 = ((j - (i - 1) * i * k / 2) + i - 1) / i;
a1 = 0 if a1 < 0
a2 = j / i;
a2 = k if a2 > k
s = 0;
for a in a1 .. a2
s += t1[j - a * i]
end
s = s % m
t2.push(s)
end
table.push(t2)
end
table2 = [0]
for x in 1 .. (n + 1) / 2
n1 = x - 1
n2 = n - x
s = 0
for i in 0 .. n1 * (n1+1) * k / 2
s += table[n1][i] * table[n2][i] % m;
end
answer = (m + s * (k+1) - 1) % m
table2.push(answer)
p answer
end
for x in (n + 1) / 2 + 1 .. n
p table2[n + 1 - x]
end
Perl
C'était TLE.
use strict;
use warnings;
use integer;
my $nkm = <STDIN>;
$nkm =~ s/\n\z//;
my ($n, $k, $m) = split(/ /, $nkm);
my $table = [[1]];
for (my $i = 1; $i < $n; $i++) {
my $t1 = $table->[$i - 1];
my $t2 = [];
my $j_max = $i * ($i + 1) * $k / 2;
for (my $j = 0; $j <= $j_max; $j++) {
my $a1 = (($j - ($i - 1) * $i * $k / 2) + $i - 1) / $i;
$a1 = 0 if $a1 < 0;
my $a2 = $j / $i;
$a2 = $k if $a2 > $k;
my $s = 0;
for (my $aa = $a1; $aa <= $a2; $aa++) {
$s += $t1->[$j - $aa * $i];
}
$s = $s % $m;
push(@$t2, $s);
}
push(@$table, $t2);
}
my $table2 = [0];
for (my $x = 1; $x <= ($n + 1) / 2; $x++) {
my $n1 = $x - 1;
my $n2 = $n - $x;
my $s = 0;
for (my $i = 0; $i <= $n1 * ($n1+1) * $k / 2; $i++) {
$s += $table->[$n1]->[$i] * $table->[$n2]->[$i] % $m;
}
my $answer = ($m + $s * ($k+1) - 1) % $m;
push(@$table2, $answer);
printf("%d\n", $answer);
}
for (my $x = ($n + 1) / 2 + 1; $x <= $n; $x++) {
printf("%d\n", $table2->[$n + 1 - $x]);
}
Elixir
C'était TLE.
defmodule Main do
def main do
[n, k, m] = IO.read(:line) |> String.trim() |> String.split(" ") |> Enum.map(&String.to_integer/1)
table = Enum.reduce(1 .. n, [[1, 0]], fn i, acc ->
[t1 | _] = acc
j_max = div(i * (i+1) * k, 2);
t2 = Enum.map(0 .. j_max, fn j ->
a1 = max(div((j - div((i - 1) * i * k, 2)) + i - 1, i), 0)
a2 = min(div(j, i), k)
rem(Enum.reduce(a1 .. a2, 0, fn a, acc3 ->
acc3 + Enum.at(t1, j - a * i)
end), m)
end)
[Enum.reverse(t2) | acc]
end) |> Enum.reverse
table2 = (1 .. div(n + 1, 2)) |> Enum.map(fn x ->
[n1, n2] = [x - 1, n - x]
s = Enum.reduce(0 .. div(n1 * (n1 + 1) * k, 2), 0, fn i, acc ->
rem((table |> Enum.at(n1) |> Enum.at(i)) * (table |> Enum.at(n2) |> Enum.at(i)) + acc, m)
end)
rem(m + s * (k+1) - 1, m)
end)
(1 .. n) |> Enum.each(fn x ->
if x <= div(n + 1, 2) do
IO.puts(Enum.at(table2, x - 1))
else
IO.puts(Enum.at(table2, n - x))
end
end)
end
end
Recommended Posts