前書き
AtCoderを始めるにあたってとても参考になる@drkenさんの記事
「AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～」
で紹介されている過去問10問をやってみましょう。
様々な方がいろんな言語で解答されていますが、R言語が見当たらないのでRでやります。
注意
- 問題文を引用していますが、制約条件などの部分を省略しています。問題へのリンクを貼っていますので詳しくはそちらでご確認を
- R言語、AtCoderでは利用できないので手元のみで動作確認しています
- 通常、AtCoderのような競技プログラミングでは外部ライブラリとか使わないと思いますが、コードの見やすさのためmagrittrだけ使っています
-
func2(func1(data))がdata %>% func1 %>% func2というパイプ的な表記に変えられるやつです - 処理順番がわかりやすくてよろしい
-
- アルゴリズムの解説は元の記事におまかせして、R言語的なTipsがあれば書いています
R言語での解答一覧
第１問
【問題概要】
二つの正整数 a, b が与えられます。 a と b の積が偶数か奇数か判定してください。[入力]
入力は以下の形式で標準入力から与えられる。
a b[出力]
積が奇数なら Odd と、 偶数なら Even と出力せよ。
library(magrittr)
line <- readLines(n=1)
sp_line <- strsplit(line,' ') %>% unlist
a <- sp_line[1] %>% as.numeric()
b <- sp_line[2] %>% as.numeric()
ifelse(a * b %% 2 == 0, "Even", "Odd") %>% cat
R Tips
- readLinesの引数n=1で標準入力から何行読み込むかを設定できます。
- 文字列をsplitするstrsplit関数は結果がListで返ってくるので[[1]]を参照するか、unlistで展開する必要があります。
- Rの文字列処理はちょっとめんどくさいところが多いです。
第２問
【問題概要】
すぬけ君は1,2,3 の番号がついた 3つのマスからなるマス目を持っています。 各マスには 0 か 1 が書かれており、マス iには si が書かれています。
すぬけ君は 1 が書かれたマスにビー玉を置きます。 ビー玉が置かれるマスがいくつあるか求めてください。[入力]
s1s2s3
例） 110[出力]
答えを出力
library(magrittr)
line <- readLines(n=1)
sp_line <- strsplit(line,'') %>% unlist
sum(sp_line == 1) %>% cat
R Tips
- Rのようなベクトル計算に強い特性が役に立った例
- strsplitでセパレータに''を指定すると１文字ずつに分解されます
- 例えば'110'なら[1, 1, 0]というベクトルになります
- そして
sp_line == 1とするとベクトルのそれぞれの要素と判定が行われ、[True, True, False]という評価がされます - sum()するとベクトル内のTrueの数が数えられ、2という出力が得られる、という流れです
第３問
【問題概要】
黒板に N 個の正の整数 A1,...,AN が書かれています．
すぬけ君は，黒板に書かれている整数がすべて偶数であるとき，次の操作を行うことができます．
黒板に書かれている整数すべてを，2 で割ったものに置き換える．
すぬけ君は最大で何回操作を行うことができるかを求めてください．[入力]
N A1 A1 ... AN[出力]
すぬけ君は最大で何回操作を行うことができるかを出力せよ．
library(magrittr)
N <- readLines(n=1) %>% as.numeric
A <- readLines(n=1)
A.vec <- strsplit(A,' ') %>% unlist %>% as.numeric
tmp <- A.vec
cnt <- 0
while (T) {
is.all.even <- sum(tmp %% 2 == 0) == N
if (is.all.even){
tmp <- tmp / 2
cnt <- cnt + 1
}else{
break
}
}
cat(cnt)
R Tips
- これまたベクトル演算に強くて楽できているパターン
- 配列（Rではベクトル）の中で2で割り切れるものがN個ある時という処理は
sum(tmp %% 2 == 0) == Nで一発
第４問
【問題概要】
あなたは、500 円玉を A 枚、100 円玉を B 枚、50 円玉を C 枚持っています。 これらの硬貨の中から何枚かを選び、合計金額をちょうど X 円にする方法は何通りありますか。
同じ種類の硬貨どうしは区別できません。2通りの硬貨の選び方は、ある種類の硬貨についてその硬貨を選ぶ枚数が異なるとき区別されます。[入力]
入力は以下の形式で標準入力から与えられる。A B C X[出力]
硬貨を選ぶ方法の個数を出力せよ。
library(magrittr)
A <- readLines(n=1) %>% as.numeric
B <- readLines(n=1) %>% as.numeric
C <- readLines(n=1) %>% as.numeric
X <- readLines(n=1) %>% as.numeric
cnt <- 0
for(a in 0:A){
for(b in 0:B){
for(c in 0:C){
m <- a * 500 + b * 100 + c * 50
if(m == X){
cnt <- cnt + 1
}
}
}
}
cat(cnt)
R Tips
- for文多用はあんまりRっぽくないですが許して下さい
第５問
【問題概要】
1 以上 N 以下の整数のうち、10 進法で各桁の和が A 以上 B 以下であるものについて、総和を求めてください。[入力]
入力は以下の形式で標準入力から与えられる。
N A B[出力]
1 以上 N 以下の整数のうち、10 進法での各桁の和が A 以上 B 以下であるものの総和を出力せよ。
library(magrittr)
s <- readLines(n=1)
s_sp <- strsplit(s, ' ') %>% unlist %>% as.numeric
N <- s_sp[1]
A <- s_sp[2]
B <- s_sp[3]
cnt <- 0
for(i in 1:N){
temp <- as.character(i) %>% strsplit('') %>% unlist %>% as.numeric %>% sum
if(A <= temp && temp <= B){
cnt <- cnt + i
}
}
# Filter(function(x){
# temp <- as.character(x) %>% strsplit('') %>% unlist %>% as.numeric %>% sum
# A <= temp && temp <= B
# }, 1:N) %>% sum -> cnt
cat(cnt)
R Tips
- アルゴリズムとしては問題をそのままコードにしたような形
- 今回の場合はシンプルなのでfor文のような形でもよいですが、FilterやMapを使うと見やすくなる場合もあります
- Filterを使った例をコメントアウト部分に記述
- フィルターする条件をfunctionに書くとその条件に当てはまる要素のみが返ってくるのでそのままsum()するという流れ
第６問
【問題概要】
N 枚のカードがあります. i 枚目のカードには, ai という数が書かれています.
Alice と Bob は, これらのカードを使ってゲームを行います. ゲームでは, Alice と Bob が交互に 1 枚ずつカードを取っていきます. Alice が先にカードを取ります.
2 人がすべてのカードを取ったときゲームは終了し, 取ったカードの数の合計がその人の得点になります. 2 人とも自分の得点を最大化するように最適な戦略を取った時, Alice は Bob より何点多く取るか求めてください.[入力]
入力は以下の形式で標準入力から与えられる.N a1 a2 a3 ... aN[出力]
両者が最適な戦略を取った時, Alice は Bob より何点多く取るかを出力してください.
library(magrittr)
N <- readLines(n=1) %>% as.numeric
s <- readLines(n=1)
s_sp <- strsplit(s, ' ') %>% unlist %>% as.numeric
sorted <- sort(s_sp, decreasing = T)
alice <- 0
bob <- 0
for(i in 1:N){
if(i%%2==0){
bob <- bob + sorted[i]
}else{
alice <- alice + sorted[i]
}
}
# alice.idx <- 1:ceiling(N/2) * 2 - 1
# bob.idx <- 1:floor(N/2) * 2
# alice <- sorted[alice.idx] %>% sum
# bob <-sorted[bob.idx] %>% sum
cat(alice - bob)
R Tips
- 「最適な戦略を取る」とあるので、常に最大の値を取っていけばよく、ソートして順番に振り分けています
- コメントアウト部分でR言語っぽく（ベクトル処理っぽく）やろうとした例を書きましたがかえってややこしくなった印象
- ソート結果の1,3,5...番目部分と2,4,6...部分の合計を出すという流れ
第７問
【問題概要】
X 段重ねの鏡餅 (X≥1) とは、X 枚の円形の餅を縦に積み重ねたものであって、どの餅もその真下の餅より直径が小さい（一番下の餅を除く）もののことです。例えば、直径 10、8、6 センチメートルの餅をこの順に下から積み重ねると 3 段重ねの鏡餅になり、餅を一枚だけ置くと 1 段重ねの鏡餅になります。
ダックスフンドのルンルンは N 枚の円形の餅を持っていて、そのうち i 枚目の餅の直径は di センチメートルです。これらの餅のうち一部または全部を使って鏡餅を作るとき、最大で何段重ねの鏡餅を作ることができるでしょうか。[入力]
入力は以下の形式で標準入力から与えられる。N d1 d2 ... dN[出力]
作ることのできる鏡餅の最大の段数を出力せよ。
library(magrittr)
N <- readLines(n=1) %>% as.numeric
l <- NULL
for(i in 1:N){
l <- c(l, readLines(n=1) %>% as.numeric)
}
unique(l) %>% length %>% cat
（辞書構造を使う場合）
library(magrittr)
N <- readLines(n=1) %>% as.numeric
dict <- list()
for(i in 1:N){
dict[readLines(n=1)] <- 1
}
dict %>% length %>% cat
R Tips
- データ量が少ない場合はuniqueしてしまえばOK
- データ量が大量になる場合は辞書構造などを使うことでメモリ量を削減可能
- Rの場合、list()を準備しておき、連想配列のようなイメージで詰め込む
第８問
【問題概要】
日本でよく使われる紙幣は、10000 円札、5000 円札、1000 円札です。以下、「お札」とはこれらのみを指します。
青橋くんが言うには、彼が祖父から受け取ったお年玉袋にはお札が N 枚入っていて、合計でY 円だったそうですが、嘘かもしれません。このような状況がありうるか判定し、ありうる場合はお年玉袋の中身の候補を一つ見つけてください。なお、彼の祖父は十分裕福であり、お年玉袋は十分大きかったものとします。[入力]
入力は以下の形式で標準入力から与えられる。
N Y[出力]
N 枚のお札の合計金額が Y 円となることがありえない場合は、-1 -1 -1 と出力せよ。
N 枚のお札の合計金額が Y 円となることがありうる場合は、そのような N 枚のお札の組み合わせの一例を「10000 円札 x 枚、5000 円札 y 枚、1000 円札 z 枚」として、x、y、z を空白で区切って出力せよ。複数の可能性が考えられるときは、そのうちどれを出力してもよい。
library(magrittr)
s <- readLines(n=1)
s_sp <- s %>% strsplit(' ') %>% unlist %>% as.numeric
N <- s_sp[1]
Y <- s_sp[2]
A <- B <- C <- -1
flag <- F
for(a in 0:N){
for(b in 0:(N-a)){
ans <- 10000 * a + 5000 * b + 1000 * (N - a - b)
if(ans == Y){
A <- a
B <- b
C <- N - a - b
flag <- T
break
}
}
if(flag) break
}
sprintf("%s %s %s", as.character(A), as.character(B), as.character(C)) %>% cat
R Tips
- これまたあまりRらしさがないです。sprintfでフォーマットを指定して出力できます。
第９問
【問題概要】
英小文字からなる文字列 S が与えられます。 Tが空文字列である状態から始め、以下の操作を好きな回数繰り返すことで S=T とすることができるか判定してください。
- T の末尾に dream dreamer erase eraser のいずれかを追加する。[入力]
入力は以下の形式で標準入力から与えられる。
S[出力]
S=Tとすることができる場合'YES'を、そうでない場合'NO'を出力せよ。
library(magrittr)
s <- readLines(n=1)
STR <- c('dream', 'dreamer', 'erase', 'eraser')
flag <- T
temp <- s
while(flag){
flag <- F
for (str in STR) {
if(0 < regexpr(paste0(str,'$'), temp)){
temp <- gsub(paste0(str,'$'), "", temp)
flag <- T
}
}
}
ifelse(nchar(temp)==0, "YES", "NO") %>% cat
R Tips
- 元記事でも解説されていますが、今回の問題の場合は後ろから検索することで問題が解けますが、高難易度の問題では解けない場合もあるので注意
- Rではifelseやif文も値を返すようになっているのでそのままcatすると結果が表示できます
第１０問
【問題概要】
シカのAtCoDeerくんは二次元平面上で旅行をしようとしています。 AtCoDeerくんの旅行プランでは、時刻 0 に 点 (0,0) を出発し、 1 以上 N 以下の各 i に対し、時刻 ti に 点 (xi,yi) を訪れる予定です。
AtCoDeerくんが時刻 t に 点 (x,y) にいる時、 時刻 t+1 には 点 (x+1,y), (x−1,y), (x,y+1), (x,y−1) のうちいずれかに存在することができます。 その場にとどまることは出来ないことに注意してください。 AtCoDeerくんの旅行プランが実行可能かどうか判定してください。[入力]
入力は以下の形式で標準入力から与えられる。N t1 x1 y1 t2 x2 y2 ... tN xN yN[出力]
旅行プランが実行可能なら'Yes'を、不可能なら'No'を出力してください。
library(magrittr)
N <- readLines(n=1) %>% as.numeric
t <- x <- y <- 0
flag <- T
for(i in 1:N){
str_sp <- readLines(n=1) %>% strsplit(' ') %>% unlist %>% as.numeric
tt <- str_sp[1]
xx <- str_sp[2]
yy <- str_sp[3]
dis <- abs(xx - x) + abs(yy - y)
time <- tt - t
if(time < dis || (time - dis)%%2==1){
flag = F
}
# 追加修正
t <- tt
x <- xx
y <- yy
}
ifelse(flag, "Yes", "No") %>% cat
R Tips
- 到着できない判定として、「時間が距離より少ない（１ずつしか動けないので到達しない）場合」と「最短で到着できる時間から奇数時間余る」場合をチェック
- 偶数時間余るならゴールとその隣を行ったり来たりすれば良いので到着できることに注意
- Rっぽくはない...
[追記｜2021/4/15]
間違いを発見。
1つ前の地点から移動できるかどうかを判定する必要があるので、t,x,yを更新する必要あり。
おわりに
Rは競プロには向いてない、、、たまに便利だけど。