Go to Qiita Advent Calendar 2024 Top
LoginSignup
7
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@bo9chan

R言語でAtCoderの問題を解いてみた

Last updated at Posted at 2023-08-18

1. 概要

先日のジャッジシステムのアップデートで、AtCoderでR言語が使えるようになりました1。R言語を使って何問か解いてみましたので、得られた知見を共有します。

なお筆者はR言語については5、6年ほど前に統計学の勉強の過程で触った程度です。便利なパッケージや最近の記法などは把握していませんので悪しからず。

【更新】2024-4-21 第4.1.4節を追記、第5.5節を追記修正

2. 実施内容

以下の3つのコンテストのA問題からF問題までを解いてみました2。

結果は下表の通りです。R言語の計算速度が遅くTLE（制限時間超過）になるなどの理由から、多くの問題を解くことができませんでした。なお結果の記載のない5問はいずれもTLEになると推測できたため実施していません。

問題 新ジャッジコン ABC314 ABC315
A AC AC AC
B AC AC AC
C AC TLE → AC AC
D TLE → AC - → AC TLE
E - → TLE AC - → AC
F TLE → AC - - → TLE

表中の記号はジャッジステータスです。

2023.12.30 表中の赤字部分については記事執筆後、第5節に示す方法などを使って再挑戦した結果です。

参考：R言語の環境構築について

筆者のローカルPCでの場合です。既にRStudio3を導入されている場合はそれで構わないと思いますが、ジャッジシステムとのR言語のバージョン等の差異には気をつけてください。

  • Windows 11にWSL2 + Ubuntuを導入、エディタはVSCodeを使っています。
  • R言語のUbuntuへのインストールコマンドはLanguage Test 202301冒頭部の「こちらのスプレッドシート」の「最終版」タブに記載のあったものをそのまま使ったと思います。
sudo apt install r-base r-base-dev
sudo Rscript -e "install.packages(c('Rcpp', 'stringr', 'purrr', 'magrittr', 'sets', 'dequer', 'zeallot', 'lubridate', 'readr'))"

以上の環境構築が面倒くさければ、AtCoder Easy Test v2を使えばよいかと思います。

3. 結論

まとめると以下の通りです。正直、競技プログラミングで戦える言語ではないという印象ですが、R言語の勉強目的でやる分には問題ないかなと思いました5。

  • 入出力は問題なくできる。インタラクティブ問題も大丈夫。
  • for文が重いため、$10^5$オーダーの処理はTLE（制限時間超過）になる場合がある。
  • 整数型は32bitなので、64bit整数が必要な際はbit64パッケージを使う。ただし計算速度は遅いので、$10^{14}$程度までであればdouble型での代用が現実的。
  • ジャッジシステムへのdequerパッケージのインストールに失敗していると思われる。

4. 結論の説明

4.1 入出力

4.1.1 入力

以下のような書き方で問題なく入力できることが分かりました。なお後者の行数を指定して読み込む方法についてはブログ記事を参考にしました。

# 入力を一括で読み込む
input <- readLines("stdin")

# 入力行数を指定して読み込む
# connectionを作成し`readLines`関数に渡さないとエラーになる
conn <- file("stdin", open="r")

N <- readLines(conn, n=1) |> as.integer()  # N: 整数
vec <- readLines(conn, n=N)                # vec: 要素数Nの文字列ベクトル

close(conn)

なお、AtCoderでは「空白区切りの数値等を指定行数だけ読み込む」処理が多いので、筆者は以下のようなrl関数を作成し利用しています。

rl <- function(n=1) {
    # n行読み込んでベクトル化
    ret <- readLines(conn, n=n) |> strsplit(" ") |> unlist()
    return(ret)
}

# 以下のような1行の入力を読み込み、要素数Mのベクトル`vec`に変換：
# A_1 A_2 ... A_M
vec <- rl() |> as.integer()

# 以下のようなN行の入力を読み込み、N行2列の行列`mat`に変換：
# A_1 B_1
# A_2 B_2
# ...
# A_N B_N
mat <- rl(n=N) |> as.integer() |> matrix(ncol=2, byrow=TRUE)

また、zeallotパッケージが利用可能ですので、代入演算子%<-%を使い以下のように読み込むことができます。

library(zeallot)

# "3 5"のような空白区切りの数値を変数A, Bに代入
# パイプ演算子`|>`を使わない場合、右辺全体にかかる括弧は不要
c(A, B) %<-% (readLines(conn, n=1) |> strsplit(" ") |> unlist() |> as.integer())

ただし、動作が重いのでforループ内での使用は非推奨です。
以下、ABC314 C問題での検証結果です。22行目のifブロック内のみ変えています。

筆者提出コード（forループ内で%<-%を使用） : TLE
筆者提出コード（同不使用） : AC

4.1.2 出力

cat関数で問題なさそうです。

# "42\n"を出力
answer <- 42
cat(answer)
cat("\n")

なお、インタラクティブ問題（新ジャッジコン C問題）については

出力を行うたびに標準出力をflushしてください。

と問題文中にありますが、cat("\n")でflushされるようです。なおflush.console()ではうまくいきませんでした。

筆者提出コード（新ジャッジコン C問題）

他の注意点として、出力する値が大きいときに指数表記（1e+9等）で出力されてしまうことがあるとのことです。そのようなことを避けるために、

options(scipen=100)

とコードの冒頭に忘れずに書いておきましょう。サンプルケースでは答えの大きさが2-3桁と小さいことが多いため、テストケースで指数表記で出力されてしまった場合は大変気づきにくいです。

4.1.3 ベクトルの出力

空白区切りでベクトルを出力する際、ベクトルの要素数が多いと遅くなるようです。

# 素直に書くと遅い
vec <- 1:100000
cat(vec)
cat("\n")

解決策として、一旦文字列に変換してから出力することで高速に出力できます。

# 要素同士を空白で結合
cat(paste(vec, collapse=" "))
cat("\n")

別のケースとして、改行区切りでの出力の際は次のようになります。

# 遅い
for (i in 1:length(vec)) {
    cat(vec[i])
    cat("\n")
}

# 速い
cat(paste(vec, collapse="\n"))
cat("\n")

4.1.4 行列の出力

例えば$N$行2列の行列を出力する場合（例：ABC350 C問題）、以下のように工夫することで出力を高速化できます。行列の値、半角スペースおよび改行文字を$N$行4列の行列tmpに代入し、paste関数で結合して一気に出力しています。

# N行2列の行列を作成
N <- 10000
mat <- matrix(1:(2 * N), ncol=2, byrow=TRUE)

# 遅い
for (i in 1:N) {
    mat[i, ] |> paste(collapse=" ") |> cat()
    cat("\n")
}

# 速い
tmp <- matrix(' ', nrow=N, ncol=4)
tmp[, 1] <- mat[1:N, 1] |> as.character()
tmp[, 3] <- mat[1:N, 2] |> as.character()
tmp[, 4] <- '\n'
tmp |> t() |> paste(collapse="") |> cat()

4.2 for文が重い

R言語はfor文が重いです。あくまで筆者の感覚ですが、

  • 計算量が$O(10^5)$以下：注意して実装しないとTLEになる場合がある
  • 計算量が$O(10^6)$以上：どう頑張ってもTLEになるケースが出てくる

といった具合です。実行時間の高速化については第5節で説明します。

4.3 64bit整数について

記事執筆当初は「64bit整数は使えない」としていました。訂正します。

R言語では整数型は符号付き32bitのため、符号付き64bit整数が必要な場合はbit64パッケージを読み込む必要があります。

library(bit64)

x <- as.integer64("3141592653589793238")
x <- 2 * x
# `cat(x)`では正常に出力されない
cat(as.character(x))  # 6283185307179586476

ただし、上記コードの通りcatで出力する際には一旦文字列に変換する必要があるなど、通常のintegerやdouble型と同様に記述できない点がいくつか存在します。また、計算速度もintegerやdouble型に比べて遅く、計算回数が多い場合はTLEの原因となり得ます。従ってどうしても必要な時に限って使うのが良さそうです。取り扱う値の最大値が$10^{14}$程度までであれば、double型で代用することもできます6。

以下リンク先のコードでは64bit整数を使用しています。

筆者提出コード（新ジャッジコン B問題）

4.4 利用可能なパッケージ

新ジャッジシステムにおいて、各言語で使用できるパッケージの一覧は以下のリンク先から確認することができます。
https://img.atcoder.jp/file/language-update/language-list.html

これによると、R言語で利用できるパッケージは次の通りです。

  • Rcpp 1.0.9
  • stringr 1.5.0
  • purrr 1.0.1
  • magrittr 2.0.3
  • sets 1.0-21
  • dequer 2.0-2
  • zeallot 0.1.0
  • lubridate 1.9.2
  • readr 2.1.4

実際に何が使えるのかは、コードテストでlibrary()と打って実行することで確認することができます。実行後しばらくすると標準出力の欄に利用可能なパッケージの一覧が表示されます。

image.png
image.png

上記一覧に記載のなかったbit64が利用可能であるのが分かる一方、インストールされているはずのdequerパッケージが表示されていません。CRANのdequerのページを確認するとdequerがどうやらCRANから削除されてしまっているようです。そのため新ジャッジシステムへインストールに失敗したのではないかと推測します。

一方、いろいろと便利なパッケージを入れていただいているようですので、問題を解く前に各パッケージの内容を一度確認しておいた方が良いと思います。

5. 実行速度の高速化

上述の通り、ABCのC問題以降は実行速度が十分でないためTLEとなるケースが出てきます。しかし一部の問題では工夫をすることで制限時間内に間に合わせることができます。

5.0 高速化って2種類あんねん

200種類はないので安心してください（笑）

  1. 計算量改善
  2. 定数倍高速化

の2つです。
計算量改善はR言語に限らずどの言語でも必要で、高速なC++でもこれが出来ていないと容赦なくTLEになります。次の例は計算量が$O(N^2)$で、$N^2 = 10^{10}$ですのでNGです。sum関数の計算量が$O(N)$であることに注意。

# 計算量: O(N^2)
N <- 100000
vec <- 1:N
ans <- rep(0, N)
for (i in 1:N) {
    ans[i] <- sum(vec[-i])
}

ここから計算量改善をすると次のようになります。sum関数をforループの外側に出すことで実行回数をN回から1回に減らし、計算量は$O(N)$に改善しました。高速な言語ならこれだけで十分ですが、R言語ではさらに定数倍高速化が必要になる場合があります。

# 計算量: O(N)
N <- 100000
vec <- 1:N
ans <- rep(0, N)
vec.sum <- sum(vec)
for (i in 1:N) {
    ans[i] <- vec.sum - vec[i]
}

上のコードをさらに定数倍高速化すると次のようになります。forループをベクトル演算に置き換えました。計算量は変わらず$O(N)$ですが、計算速度は改善します（$N$が小さいため実際はほぼ差がありませんが、$N = 10^7$程度にすると差が出てきます）。

# 計算量: O(N) + 定数倍高速化
N <- 100000
vec <- 1:N
ans <- sum(vec) - vec

まとめると、C++のような高速な言語では計算量改善だけやれば十分なケースが多いですが、R言語ではそれに加えて定数倍高速化もやらなければいけません。競技プログラミングではC++やPython（PyPyで簡単に高速化できる）ユーザーが多い理由の一つです。もうPythonでええやん・・・

以降ではR言語における定数倍高速化について主に話をしていきます。

5.1 高速化のための基本事項

計算速度の測定はAtCoderのコードテストで行うのがおすすめです。以下のコードを実行してみて下さい。

  • ベクトル演算や組み込み関数等を使ってfor文を減らす
# 遅い
arr <- 1:3000000
val <- 0
for (e in arr) if (e %% 3 == 0) val <- val + e

# 速い
arr <- 1:3000000
val <- sum(arr[arr %% 3 == 0])
  • ベクトルに要素を追加していく際は、あらかじめ領域を確保する7 
# 遅い
N <- 30000
arr <- c()
for (i in 1:N) arr <- c(arr, 3 * i)

# 速い
N <- 30000
arr <- rep(0, N)
for (i in 1:N) arr[i] <- 3 * i
  • リストに要素を追加していく際は、位置を指定して追加する7 
# 遅い
N <- 30000
li <- list()
for (i in 1:N) {
    li <- append(li, 3 *i)
}

# 速い
N <- 30000
li <- list()
for (i in 1:N) {
    n <- length(li) + 1
    li[[n]] <- 3 * i
}
  • 文字列処理の際は必要に応じて、あらかじめ1文字のベクトルに変換する
# ベクトルに変換し、文字aの数を数える
s <- "abracadabra"
arr <- s |> strsplit("") |> unlist()
val <- sum(arr == "a")
  • bit64パッケージの64bit整数やzeallotパッケージの代入演算子%<-%は重いため、forループ等での使用は必要最小限にする
# 遅い
library(zeallot)
N <- 10000
mat <- matrix(1:(2*N), nrow=N, ncol=2)
for (i in 1:N) {
    c(l, r) %<-% mat[i, ]
}

# 速い
N <- 10000
mat <- matrix(1:(2*N), nrow=N, ncol=2)
for (i in 1:N) {
    l <- mat[i, 1]
    r <- mat[i, 2]
}
  • 不要なパッケージは読み込まない
# これだけで数百ミリ秒を消費する
library(readr)

5.2 動的計画法のベクトル演算による高速化

ABC317 D問題は2次元動的計画法で解く問題で、$N$回のforループと$S := \sum^N_{i=1}Z_i$回のforループによる二重ループで計算します。制約は$1 \le N \le 100$および$S \le 10^5$ですので、後者のforループが原因でTLEになってしまいます。

解決策として$S$回のforループの部分をベクトル計算に置き換えます。公式解説の実装例21-23行目をR言語で書き直すと、

# このままではTLE!
for (j in (z_sum+1):(z+1)) {
    dp[j] <- min(dp[j], dp[j - z] + w)
}

のようになりますが、forループ内は$j$番目と$j - z$番目の要素の比較となっており常に$z$だけずれています。したがって次のようにdpを正の方向に$z$だけずらし、空いた部分をinfで埋めたベクトルdp2を作成し、pmin関数でベクトルの要素ごとに最小値を求めることでfor文をベクトル計算化することができます。

dp2 <- c(array(inf, z), dp[1:(z_sum + 1 - z)]
dp <- pmin(dp, dp2 + w))

なお、この問題では答えが大きくなるため、dpはinteger型ではなくdouble型にしました。

筆者提出コード（ABC317 D問題）

5.3 グラフ問題

ABC270 C問題を例に説明します。
グラフ問題では通常、入力したデータを隣接リスト化します。R言語では例えば以下のようにlistを使うことで実現できます。

# ABC270 C問題
conn <- file("stdin", open="r")
rl <- function(n=1) {
    # n行読み込んでベクトル化
    ret <- readLines(conn, n=n) |> strsplit(" ") |> unlist()
    return(ret)
}

### データ入力 ###
inp <- rl() |> as.integer()
N <- inp[1]
X <- inp[2]
Y <- inp[3]
tmp <- rl(N - 1) |> as.integer() |> matrix(ncol=2, byrow=TRUE)

### 隣接リスト作成 ###
G <- list()
for(i in 1:N) {
    G[[i]] <- list()
}
for(i in 1:(N-1)) {
    a <- tmp[i, 1]
    b <- tmp[i, 2]
    n <- length(G[[a]]) + 1
    G[[a]][[n]] <- b
    n <- length(G[[b]]) + 1
    G[[b]][[n]] <- a
}

提出結果は次の通りですが、制限時間2秒に対して実行時間は1953 msとギリギリです。この問題ではACすることができたものの、これでは他の問題でも同様にACできるのか、かなり怪しいところです。

筆者提出コード（隣接リスト） : AC / 1953 ms

更に高速化することはできないのでしょうか。実は、隣接リストを行列およびベクトルで実装することでで可能になります。下図右に示すように、まず$M$本の辺のデータとして頂点$u$, $v$のペアを$2M$行$2$列（無向グラフの場合。有向グラフなら$M$行$2$列）の行列$mat$に格納し、$u$で昇順にソートします。次に、行列$mat$での頂点$u$の開始位置を要素数$N+1$のベクトル$idx$に格納します。

隣接リスト.jpg

そして頂点$u$に隣接する頂点$v$は次のように探索できます。

i1 <- idx[u]
i2 <- idx[u + 1] - 1L
# i1 > i2のとき、uに隣接する頂点はなし
if (i1 <= i2) {
    for (i in i1:i2) {
        v <- mat[i, 2]
    }
}

以下に提出結果および隣接リスト作成部分のコードを示します。実行時間は1188 msと前回の半分近くまで削減することができましたが、listで実装する場合に比べ、かなり煩雑になってしまいます・・・。

筆者提出コード（隣接リストのベクトル化） : AC / 1188 ms

# ABC270 C問題　隣接リストを行列とベクトルで実装
# `rl`関数の定義は上記に同じ

### データ入力 ###
inp <- rl() |> as.integer()
N <- inp[1]
X <- inp[2]
Y <- inp[3]
tmp <- rl(N - 1) |> as.integer() |> matrix(ncol=2, byrow=TRUE)

### 隣接リスト（ベクトル化）作成 ###
# M: 辺の本数
M <- N - 1
# mat: 辺のデータ
mat <- array(0L, c(2 * M, 2))
# u -> v辺を代入
mat[1:M,] <- tmp
# v -> u辺を代入
mat[(M + 1):(2 * M), ] <- tmp[,c(2, 1)]
# uで昇順ソート
mat <- mat[order(mat[,1]), ]
# idx : matにおける頂点uの開始位置
idx <- array(0L, N + 1)
# "番兵"
idx[N + 1] <- 2 * M + 1
uprev <- 0L
for (i in 1:(2 * M)) {
    u <- mat[i,1]
    if (u != uprev) {
        idx[u] <- i
        uprev <- u
    }
}
# uから伸びる辺が1本もない場合は頂点u+1と同じ開始位置にする
for (u in N:1) {
    if (idx[u] == 0L) {
        idx[u] <- idx[u + 1]
    }
}

5.4 readrパッケージの利用

第4.1.1節でも述べた通り、行列形式のデータは以下のようにして読み込むことができ、これで問題になることはあまりありません。

rl <- function(n=1) {
    # n行読み込んでベクトル化
    ret <- readLines(conn, n=n) |> strsplit(" ") |> unlist()
    return(ret)
}

# N行の入力を読み込み、N行2列の行列`mat`に変換：
mat <- rl(n=N) |> as.integer() |> matrix(ncol=2, byrow=TRUE)

別の方法として、readrパッケージのread_table関数を使うことでも同様に処理をすることができます。パッケージの読み込み（1行目）で数百ミリ秒余分に消費してしまう点と、なによりコードが煩雑になるデメリットがあるのですが、問題によってはこちらの方が速いケースがあることを確認しています8。

library(readr)

# N行読み込む
input <- readLines(conn, n=N)
# 1行の時は末尾に"\n"を連結
if (N == 1) input <- paste(input, "\n", sep="")
# tibble型に変換
df <- read_table(paste(input, collapse="\n"),
                 col_types=list("i", "i"),
                 col_names=FALSE,
                 progress=FALSE
                )
# matrix型に変換
mat <- as.matrix(df)
# 列名を削除
colnames(mat) <- NULL

筆者提出コード（ABC315 C問題）

5.5 ハッシュテーブル

5.5.1 environment

Pythonのdictに相当することをR言語で行うには、Qiitaの検証記事によるとenvironmentが高速とのことで良さそうです。使い方を以下にまとめます。

# 作成
H <- new.env()
# 要素の挿入。キーは文字列型のみ
H[["taro"]] <- 42
H[["jiro"]] <- "yamada"
H[["saburo"]] <- 1:5
# 要素の取得
value <- H[["jiro"]]
# 要素数の取得
length(H)  # 3
# keyの存在判定
is.null(H[["shiro"]])  # TRUE
# keyのベクトルを取得。keyは辞書順になる
keys <- ls(H)  # c("jiro", "saburo", "taro")
# 要素の削除。遅い
rm(list="taro", envir=H)
# 複数要素の一括削除。forループで1個ずつ削除するよりずっと速い
rm(list=c("jiro", "saburo"), envir=H)

ハッシュテーブルの練習問題である競技プログラミングの鉄則 演習問題集 A54がR言語で解けることを確認しました。ただ計算速度はそれほど早くなく、TLEを回避できない問題も残念ながらいくつか存在します。

筆者提出コード（鉄則本A54）

5.5.2 %in%演算子

%in%演算子を使うと、左辺のベクトルの各要素が右辺のベクトルに存在するかどうかを高速に判定することが可能です。

vec <- c(1, 3, 5, 7, 9)
values <- 1:10 * 3  # 3の倍数

res <- vec %in% values
cat(res)  # FALSE TRUE FALSE FALSE TRUE
cat("\n")

vec、valuesのサイズをそれぞれ$N$, $M$とすると、見かけ上の計算量は$O(NM)$ですが、実際はずっと高速で$O(N+M)$と思われます。このテクニックはABC344 C問題で威力を発揮します。

5.6 その他

他に気づいたことをメモとして以下に残します。

  • 再帰関数は5000階層弱しか潜れないようです。options(expressions=1e+5)を宣言しても少ししか増えず。エラーが出る場合は頑張って非再帰で書きましょう。
  • e1071パッケージにあるbincombinations, permutations関数が便利そうです。次回のジャッジシステム更新時に入れてもらいましょう。また、gtoolsパッケージにも似たような関数があり、こちらも要検討です。
  • UnionFindがかなり遅いです。代替が効かないことがかなりあるので、どうしたものか・・・。
  • integer型の代わりにdouble型を使うと、遅くなるどころか僅かに速くなるような気がするのですが、気のせいでしょうか。

6. さいごに

以上、現状解ける問題は限られますが、本記事がこれからR言語でAtCoderにトライされる方の一助になれば幸いです。

  1. 記事執筆時点では2023/8/6以降に開催されたコンテストのみ（ヒューリスティックを除く）。いずれ過去問題でも利用できるようになるそうです。 2023/9/4より利用可能になりました。 ↩

  2. いずれも本番終了後に実施。 ↩

  3. RStudioでのサンプルテストは例えば次の手順です: 1. エディタでコーディングしてファイルに保存 2. TerminalからRscript {filename}.Rを実行 3. Terminalにサンプルの入力をコピペ。 ↩

  4. サンプルテストのコマンドはoj t -c "Rscript {filename}.R"です。 ↩

  5. ABCでは300点以上の問題では計算量が多い問題が出る傾向にあるため、TLEになる可能性が出てきます。R言語の勉強にはA, B問題が良さそうです。 ↩

  6. ±9,007,199,254,740,992 (=$2^{53}$)の範囲内であればdouble型で整数を表現できるはずですが、確信が持てません・・・。 ↩

  7. 速度に差が出るのは計算量が異なるからだと思われます。前者は$O(N^2)$、後者は$O(N)$なのでしょう。 ↩ ↩2

  8. 逆に遅くなる問題も複数確認しており、ケースバイケースです。なおABC314 D問題は筆者がやる限りではread_tableを使うことでTLEを回避することができました。 ↩

7
3
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
7
3

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?