競プロの問題を使ってRcppの練習をしてみた

競プロとは

競プロとは競技プログラミングの略称で、出題される問題に対し、プログラミングによって解決をし、その速さ、正確さを競うものです。

日本で競プロのコンテストを開催しているサイトといえばAtCoder(https://atcoder.jp/)が代表的だと思います。

私は基本的に競プロではC++を使っています。だったらRcppの練習がてら競プロの問題を使ってみるのも面白いかなと思ってこの記事を書いてみようと思いました。

Rcppとは

RcppとはRでC++というプログラミング言語をあつかえるようにするパッケージです。一番特徴的なのは静的型付け言語であるということだと思います。

そこで、C++でコードを書こうとすると型を意識する必要があります。普段C++標準の型はわかっているのですが、Rcppでコードを書くとなったとき、Rのベクトルなどはどうなるのかなどの理解も必要になってきます。

とはいえ競プロの問題をRcppで書くという場合はほとんどのそのようなことを意識することはないかもしれないです。

今回はAtCoderで開催されたコンテスト、ABC176(https://atcoder.jp/contests/abc176)の問題をRcppで書いていきたいと思います。

library(magrittr)
library(magrittr)

今回記載するコードで読み込んでいるパッケージです。

実際にやってみた（A問題）

まずはA問題から。整数N、X、Tを読み込んだらあとは簡単な四則演算で解答を実現できます。

なお、せっかくなのでRとの連携も考えて、入力の読み込みはR側で行うことにします。

cppFunction('
int solve_A(int n, int x, int t) {
  return (n + x - 1) / x * t;
}
')

Rcppの関数の実装部分。

"20 12 6" %>% 
  strsplit(" ") %>% 
  purrr::pluck(1) %>%
  as.integer() %>% 
  as.list() %>% 
  purrr::set_names(c("n", "x", "t")) %>% 
  purrr::invoke(.f = solve_A) %>% 
  cat("\n")
##> 12

入力をCppの関数に引数として渡し結果を出力。

ここまで簡単な問題だと、C++の部分のコードは特に変わったことはないですね。引数に int 型を指定した場合はR側で要素数１の数値ベクトルを渡すことができます。

ちなみに上記はABC176 A問題の入力例１を試していますが、標準入力から読む場合は最初の部分を readLines(n = 1) などどすれば良いです。

続いてB問題

cppFunction('
String solve_B(String s) {
  std::string ss = s;
  int tmp = 0;
  for (unsigned int i = 0; i < ss.size(); ++i) {
    tmp += ss.at(i) - \'0\';
    tmp %= 9;
  }
  if (tmp == 0) return("Yes");
  else return("No");
}
')
"123456789" %>% 
  strsplit(" ") %>% 
  purrr::pluck(1) %>%
  as.list() %>% 
  purrr::set_names(c("s")) %>% 
  purrr::invoke(.f = solve_B) %>% 
  cat("\n")
##> Yes

今度はちょっと素のC++とは違う部分が入っています。最初が大文字の String 型はRcpp特有の型でRの文字列を表しています。

この型には .size() というメソッドがないっぽいので一回 std::stirng 型の変数に代入することで型変換を行っています。

この型変換が行えるので、引数の型を std::string としても問題なさそうです。

最後にC問題

cppFunction('
long long solve_C(int n, IntegerVector a) {
  long long ans = 0;
  int a0 = 0;
  for (int i = 1; i < n; ++i) {
    if (a.at(i) < a.at(i-1)) {
      ans += a.at(i-1) - a.at(i);
      a.at(i) = a.at(i-1);
    }
  }
  return ans;
}
')
c("5", "2 1 5 4 3") %>% 
  strsplit(" ") %>% 
  purrr::map(as.integer) %>% 
  purrr::set_names(c("n", "a")) %>% 
  purrr::invoke(.f = solve_C) %>% 
  cat("\n")
##> 4

C++側の引数にある IntegerVector はRの整数ベクトルの型を表しています。この型（クラス）には、.at メソッドによって各要素にアクセスすることができます。なのでC++の vector<int> を扱うような感覚で使うことができます。

とまあこんな感じでRcppを使うことができました。

Rcppの使いどころとしては例えばベクトル化した演算ができないけどループ処理しなければならないときとかに速度を上げるために使うのかなと個人的には思っています。

ですので、グラフを扱う問題のようなもう少し複雑なアルゴリズムを扱うときは役に立つのかもしれません。とはいえRはパッケージが豊富なので大抵のことはパッケージでできそうなきはしますね。