はじめに
paizaスキルチェック見本問題をSwiftで解いてみました。
各問題のタイトルをクリックすると問題ページに飛ぶことができます。
実際のスキルチェックの難易度より全体的に簡単な問題が多いという印象でした。特にSランクの問題は実際よりもかなり簡単に感じました。
私はこの夏休みに競技プログラミングをかじり始めた新参者です。今回、初めてのブログを作成してみたくて書いてみました。
わかりにくいところ、改善点などあればご指摘ください。
Dランク 掛け算
ポイント: 改行区切りで入力された数値の読み取り
Swiftで標準入力から一行の文字列を受け取る際には以下のように書きます。「!」をつけることを忘れないようにしましょう。
let input_line = readLine()!
しかし文字列のままでは扱いにくいのでInt型に型変換することを考えましょう。Int型に変換するためには以下のように書きます。
let input_line = readLine()!
let a = Int(input_line)!
一行にまとめて書く事もできます。
let a = Int(readLine()!)!
では今回の問題の場合はどのように書けばいいでしょうか？
答えは簡単で同じことをもう一度書けばいいのです。つまり...
let a = Int(readLine()!)!
let b = Int(readLine()!)!
とすることで、a、bに値を代入することができました。あとはa×bの答えを標準出力するだけですね!
解答
let a = Int(readLine()!)!
let b = Int(readLine()!)!
print(a*b)
Dランク 足し算
ポイント: 空白区切りで入力された数値の読み取り
空白区切りで入力された値の読み取りは、一つ前の改行区切りで入力された値と同じように読み取ろうとしてもうまくいきません。
そこで、一行を文字列として読み取ったあとに空白で区切られた部分で分割して文字列の配列を作るという操作を行います。実際に書いてみましょう。
let input_line = readLine()!
let strings = input_line.split(separator: " ")
stringsには文字列の配列が格納されています。それでは格納された文字列をInt型に直してみましょう。
今回は2つの値が空白区切りで入力されることがわかっているのでstrings[0]とstrings[1]に格納された値をそれぞれaとbとします。
let strings = readLine()!.split(separator: " ")
let a = Int(strings[0])!
let b = Int(strings[1])!
先ほどと同じように、１行にまとめて書くこともできます。
あとはa＋bの答えを出力するだけですね。
解答
let strings = readLine()!.split(separator: " ")
let a = Int(strings[0])!
let b = Int(strings[1])!
print(a+b)
Dランク 一番小さな値
ポイント: letとvarの違い、for文、if文
与えられる5つの数どれよりも大きいことが保証される数（この問題では101以上）の値をansに格納しておき、ansより小さな値が入力されるたびにansの値を更新していくと考えましょう。
この時、ansの値は変化するのでletではなく、varを使うことに注意してください。
swiftではfor文を次のように書きます。以下は0以上5 未満の数を出力するコードです。
for i in 0..<5 {
print(i)
}
ちなみに0以上5 以下の値を出力するコードは次のように書きます。
for i in 0...5 {
print(i)
}
解答
var ans = 101
for _ in 0..<5 {
let a = Int(readLine()!)!
if(a < ans) {
ans = a
}
}
print(ans)
Dランク 文字の一致
ポイント: 文字列の比較
swiftの文字列の比較は簡単です。
解答
let a = readLine()!
let b = readLine()!
if(a == b) {
print("OK")
}
else {
print("NG")
}
Dランク 数の並び替え
ポイント: ソート、配列に数値を代入
改行区切りで入力されたｎ個の値を配列に格納することを考えます。今回は空の配列aを用意して、aに数値を足していくと考えましょう。
let n = Int(readLine()!)!
var a: [Int] = []
for _ in 0..<n {
a.append(Int(readLine()!)!)
}
配列に数値を格納することができました！！それでは、aをソートして出力しましょう。
解答
let n = Int(readLine()!)!
var a: [Int] = []
for _ in 0..<n {
a.append(Int(readLine()!)!)
}
a.sort()
for i in 0..<n {
print(a[i])
}
Cランク Fizz Buzz
ポイント: for文、if文
1以上n以下とするところに注意してください。
解答
let n = Int(readLine()!)!
for i in 1...n {
if(i % 15 == 0) {
print("Fizz Buzz")
}
else if(i % 3 == 0) {
print("Fizz")
}
else if(i % 5 == 0) {
print("Buzz")
}
else {
print(i)
}
}
Bランク 長テーブルのうなぎ屋
ポイント: for文、if文、Array
うなぎ食べたい。うなぎというより回転寿司だと思うのは私だけ?
座席が埋まっているかどうかを表す配列seatを始めに用意します。
m個のグループについて座ることができるかどうかを判定し、座ることができたらansの値を+1していきます。最終的にansの値が答えとなります。
それでは、i番目のグループが座ることができるかどうかはどのように判定するのでしょうか?
i番目のグループが座りたい座席番号は b[i] 以上 a[i] + b[i] 未満の位置であることがわかります。この中に１席でも埋まっている席があったらcanSitをfalseにするとしましょう。
ここで、座席の位置jがnとなった場合には座席番号0が、n+1の場合には座席番号1...と対応していきます。よって、座席の位置jをnで割ったあまりの位置について調べればいいということがわかります。
var canSit = true
for j in b[i]..<a[i]+b[i] {
if(seat[j%n] == true) {
canSit = false
}
}
canSitがfalseの場合にはお客さんを逃した、trueの場合にはお客さんが入店したとわかります。
お客さんが入店した場合には、b[i] 以上 a[i] + b[i] 未満の座席が埋まったのでseatの値を更新しましょう。
var canSit = true
for j in b[i]..<a[i]+b[i] {
if(seat[j%n] == true) {
canSit = false
}
}
if(canSit) {
ans += a[i]
for j in b[i]..<a[i]+b[i] {
seat[j%n] = true
}
}
それでは解答です。
解答
let input_line = readLine()!
let split = input_line.split(separator: " ")
let n = Int(split[0])!
let m = Int(split[1])!
var a: [Int] = [], b: [Int] = []
for _ in 0..<m {
let input_line_s = readLine()!
let s = input_line_s.split(separator: " ")
a.append(Int(s[0])!)
b.append(Int(s[1])!)
}
var seat: [Bool] = Array(repeating: false, count: n)
var ans = 0
for i in 0..<m {
var canSit = true
for j in b[i]..<a[i]+b[i] {
if(seat[j%n] == true) {
canSit = false
}
}
if(canSit) {
ans += a[i]
for j in b[i]..<a[i]+b[i] {
seat[j%n] = true
}
}
}
Aランク じゃんけんの手の出し方
ポイント: for文、5*P + 2*C == m
Sランクまで含めて一番むずかしいと思います！複雑な問題になればなるほど落ち着いて考えましょう。
グー、チョキ、パーの出す順番は関係がありません。そこで、相手が出した手に対して、自分が勝てる手の数の合計をそれぞれg、c、pに格納しましょう。
例えば、相手がパーを5回出したら、自分はチョキを５回出すことで５回勝利することができるので、ｃ=5となります。
自分が出した手を計算していきます。自分が出したての本数がm本となるためには
$$(パーを出した回数) × ５ + (チョキを出した回数) × 2 = m$$
となっていればよいです。そこで、パーを出した回数Pとチョキを出した回数Cをfor文で全探索して指の本数の合計がm本となったときだけ、勝負に勝った回数を計算しましょう。
なお、自分が出した手を大文字のG,C,P(グー、チョキ、パー）でそれぞれ表します。この時
$$ G = n-P-C $$
が成り立ちます。
for P in 0...m/5 {
for C in 0...m-P*5/2 {
if(5*P + 2*C == m && n-P-C >= 0) {
// 勝負に勝った回数の計算をここで行う
}
}
}
勝負に勝った回数はどのように計算すればいいでしょうか?
ちょっと混乱してきました??そんなときは例を用いて考えましょう。
自分がチョキを出して勝てた回数を考えます。
相手がパーを出した回数を3回、自分がチョキを出す回数が5回だとします。
この時、 c=3, C=5 です。
自分がチョキを5回出したとしても勝利した回数は、相手がパーを出した3回のみなので勝利回数は3回です。
逆に、自分がチョキを出した回数のほうが多い場合を考えてみましょう。
相手がパーを出した回数を5回、自分がチョキを出す回数が3回だとします。
この時、 c=5, C=3 です。
相手はパーを５回出してくれたので、チョキを５回出せば勝利回数は5回となります。しかしチョキは3回しか出さなかったので勝利回数は3回です。
以上より、自分がチョキを出して勝てた回数はcとCの最小値であるとわかります。
ansを答えの値とすると、ansの値をできるだけ大きくしたいので、以下のように書くことができます。
for P in 0...m/5 {
for C in 0...m-P*5/2 {
if(5*P + 2*C == m && n-P-C >= 0) {
ans = max(ans, min(p, P) + min(c, C) + min(g, n-P-C))
}
}
}
解答です。
解答
let input_line = readLine()!
let split = input_line.split(separator: " ")
let n = Int(split[0])!
let m = Int(split[1])!
var ans = 0
let string = readLine()!
var c=0, g=0, p=0
for i in string {
if(i == "C") {
g += 1
}
else if(i == "G") {
p += 1
}
else if(i == "P") {
c += 1
}
}
for P in 0...m/5 {
for C in 0...m-P*5/2 {
if(5*P + 2*C == m && n-P-C >= 0) {
ans = max(ans, min(p, P) + min(c, C) + min(g, n-P-C))
}
}
}
print(ans)
別解
はじめはこっちでやりました。解答のほうが鮮やかかな？
別解ははじめに
(パーを出した回数) × ５ + (チョキを出した回数) × 2 = m
となる組み合わせを一つ見つけてきて、そこから数値をずらしていって計算しています。
let input_line = readLine()!
let split = input_line.split(separator: " ")
let n = Int(split[0])!
let m = Int(split[1])!
var ans = 0
let string = readLine()!
var c=0, g=0, p=0
for i in string {
if(i == "C") {
g += 1
}
else if(i == "G") {
p += 1
}
else if(i == "P") {
c += 1
}
}
var P = m / 5
while((m - P*5) % 2 != 0) {
P -= 1
}
var C = (m - P*5) / 2
while(true) {
let G = n - P - C
if(G < 0 || P < 0 || C < 0) {break}
ans = max(ans, min(p, P) + min(c, C) + min(g, G))
P -= 2
C += 5
}
print(ans)
Sランク mod7占い
ポイント: for文、mod
異なる３枚の組み合わせすべてを計算しても時間内に終えることはできないでしょう。そこで、カードに書かれた整数の値を7で割ったあまりを計算し、それぞれの個数を配列aに格納します。
let n = Int(readLine()!)!
var a = Array(repeating: 0, count: 7)
var ans = 0
for _ in 0..<n {
let A = Int(readLine()!)!
a[A%7] += 1
}
a[i]は7で割ったあまりがiとなるカードの枚数を表します。
あとは、0以上7未満の3つの整数の和が7の倍数となるすべての組み合わせについて、起こりうる場合の数を計算すればいいとわかります。
3つの整数の組み合わせをi, j, kをおいた時、同じ値がある場合には場合分けが発生することに注意してください。
パターン１ ( i == j == k)
_{a[i]}C_{3}
パターン2 ( i == j, j != k)
_{a[i]}C_{2} × a[k]
パターン3 ( i != j, j == k)
a[i] × _{a[j]}C_{2}
パターン4 ( i != j, j != k)
a[i] × a[j] × a[k]
解答
let n = Int(readLine()!)!
var a = Array(repeating: 0, count: 7)
var ans = 0
for _ in 0..<n {
let A = Int(readLine()!)!
a[A%7] += 1
}
for i in 0..<7 {
for j in i..<7 {
for k in j..<7 {
if((i+j+k) % 7 == 0) {
if(i == j && j == k && a[i] >= 3) {
ans += a[i] * (a[i]-1) * (a[i]-2) / 6
}
else if (i == j && j != k && a[i] >= 2) {
ans += a[i] * (a[i]-1) / 2 * a[k]
}
else if (i != j && j == k && a[j] >= 2) {
ans += a[i] * a[j] * (a[j]-1) / 2
}
else if (i != j && j != k) {
ans += a[i] * a[j] * a[k]
}
}
}
}
}
print(ans)
Sランク 島探し
ポイント: 再帰関数、Queue、幅優先探索、構造体
有名問題です。解法は他にもっと詳しく説明したサイトがあるので省略します。
...さて、有名問題と言いながらこの問題は一般的な深さ優先探索では満点をとることができません。試しに次のコードを提出してみてください。
let input_line = readLine()!
let split = input_line.split(separator: " ")
let w = Int(split[0])!
let h = Int(split[1])!
var mp: [[Int]] = Array(repeating: Array(repeating: 0, count: h), count: w)
for i in 0..<h {
let input_line_mp = readLine()!
let split_mp = input_line_mp.split(separator: " ")
for j in 0..<w {
mp[j][i] = Int(split_mp[j])!
}
}
var ans = 0
let dx = [-1,1,0,0]
let dy = [0,0,-1,1]
func search (x:Int, y:Int) {
for i in 0..<4 {
let nx = x + dx[i]
let ny = y + dy[i]
if(nx >= 0 && nx < w && ny >= 0 && ny < h && mp[nx][ny] == 1) {
mp[nx][ny] = 0
search(x: nx, y: ny)
}
}
}
for y in 0..<h {
for x in 0..<w {
if(mp[x][y] == 1) {
ans += 1
search(x: x, y: y)
}
}
}
print(ans)
なぜ満点を取ることができないのでしょうか？原因は再帰関数の実行回数が増えすぎてしまったことです。(これに気づくのに時間かかってしまった...)
では再帰関数を使わずに問題を解いてみましょう。このまま深さ優先探索で解くためにはStackを使いますが今回は別の方法を取ります。
幅優先探索を用いて解いてみましょう。そのためにはQueueを使うので、構造体でQueueを自作しました。
ここまで来たら、定石通り?に解答するだけです!!(Queue自作している時点で定石とは呼べない気がする...)
解答
import Foundation
struct Point {
var x: Int
var y: Int
}
struct Queue {
var que: [Point], head: Int, tail: Int, MAX: Int
init (size: Int) {
MAX = size
que = Array(repeating: Point(x:-1,y:-1), count: MAX)
head = 0
tail = 0
}
mutating func push(_ point: Point) {
if(is_full()) {
print("This queue is full")
exit(1)
}
que[tail] = point
tail += 1
if(tail == MAX) {
tail %= MAX
}
}
mutating func pop() {
if(is_null()) {
print("This queue is null")
exit(1)
}
head += 1
if(head+1 == MAX) {
head %= MAX
}
}
func front() -> Point {
return que[head]
}
func is_null() -> Bool {
return tail == head
}
func is_full() -> Bool {
return head == (tail + 1) % MAX
}
}
let input_mp_size = readLine()!.split(separator: " ")
let w = Int(input_mp_size[0])!
let h = Int(input_mp_size[1])!
var mp = Array(repeating: Array(repeating: 0, count: h), count: w)
for i in 0..<h {
let input = readLine()!
let s = input.split(separator: " ")
for j in 0..<w {
let a = Int(s[j])!
mp[j][i] = a
}
}
var que = Queue(size: 1000001)
var ans = 0
let dx = [-1,1,0,0]
let dy = [0,0,-1,1]
func search (x:Int, y:Int) {
que.push(Point(x: x, y: y))
mp[x][y] = 0
while(!que.is_null()) {
let point = que.front()
que.pop()
mp[x][y] = 0
for i in 0..<4 {
let nx = point.x + dx[i]
let ny = point.y + dy[i]
if (0 <= nx && nx < w && 0 <= ny && ny < h && mp[nx][ny] == 1) {
que.push(Point(x: nx, y: ny))
mp[nx][ny] = 0
}
}
}
}
for y in 0..<h {
for x in 0..<w {
if(mp[x][y] == 1) {
ans += 1
search(x: x, y: y)
}
}
}
print(ans)
まとめ
Aランク じゃんけんの手の出し方がやっぱりいちばん難しかったでしょうか?
Sランク 島探しもQueueの自作などしていたため時間がかかってしまいました。