コンテンツへスキップ

【Ruby基礎】AtCoder Beginner Contest 023 B – 手芸王

■はじめに

Rubyの基礎的な問題をたくさん解くことで基本的な考え方やメソッドの使い方を定着させたい。
基本的にはAtCoderというプログラミングコンテスト(競技プログラミング)の過去問を使う。(AtCoderは難易度が分かれており、難易度の低いA問題かB問題を解いていく)

(5/23時点の方針)
メソッドの切り分け方や値の受け渡しを練習するために、コード長の短さについては気にせずに書くことにする。

(2022/10/17時点の方針)
しばらくはB問題を小さい番号の方からやっていく。たまにA問題もやるかも。

■問題

●出典

AtCoder Beginner Contest 023のB問題
https://atcoder.jp/contests/abc023/tasks/abc023_b

●問題文

高橋君は趣味でアクセサリーを作っている。

アクセサリーは a, b, c のいずれか 1 文字が書かれたブロックを横 1 列に並べることで作成できる。

高橋君は、以下の手順でアクセサリーの作成を行う:

  • 手順 0 : 高橋君は b 1 文字からなるアクセサリーを作成する。

以降の手順では、既にあるアクセサリーの両端にブロックを 1 つずつ追加することでアクセサリーを改造する。

  • 手順 3n+1(n≧0) : 手順 3n で完成したアクセサリーの左端に文字 a が書かれたブロックを、右端に文字 c が書かれたブロックを付け足す。
  • 手順 3n+2(n≧0) : 手順 3n+1 で完成したアクセサリーの左端に文字 c が書かれたブロックを、右端に文字 a が書かれたブロックを付け足す。
  • 手順 3n(n≧1) : 手順 3n−1 で完成したアクセサリーの左端に文字 b が書かれたブロックを、右端に文字 b が書かれたブロックを付け足す。

高橋君はアクセサリーの作成を好きな手順の直後に終了することができる。終了した場合、アクセサリーには、アクセサリーを構成するブロックに書かれた文字を左から右に読んだものと同じ名前が付けられる。

例えば、手順 0, 1, 2, 3 それぞれの直後にアクセサリーの作成を終了した場合、アクセサリーの名前は順に、b, abc, cabca, bcabcab となる。

文字列 S が与えられるので、その文字列がアクセサリーの名前として考えられるかを判定し、考えられるなら何番目の手順の直後にアクセサリーの作成を終了したのかを求めよ。

●入力

入力は以下の形式で標準入力から与えられる。

N
S
  • 1 行目には、文字列 S の長さを表す整数 N(1≦N≦100) が与えられる。
  • 2 行目には、半角の小文字アルファベットのみからなる文字列 S が与えられる。

●出力

文字列 S が手順 K の直後にアクセサリーの作成を終了したときのアクセサリーの名前と等しいような整数 K が存在する場合は整数 K を、いつアクセサリーの作成を終了してもアクセサリーの名前が S とならないときは −1 を 1 行に出力せよ。出力の末尾にも改行を入れること。

■回答

●愚直に書く

うーん全然わからない、涙。

Nは100以下、つまり100文字以下なので、もう全部洗い出しちゃうとかでもできるのかな…。

ええっと、abcを33個並べたとして
abcabcabc.........abcという99文字の文字列ができる。
それで、

a0 = abc...abcabca b cabcabc...abc
# 左に49文字、中央に1文字、右に49文字
a1 = abc...abcabc abc abcabc...abc
# 左に48文字、中央に3文字、右に48文字
a2 = abc...abcab cabca bcabc...abc
# 左に47文字、中央に5文字、右に47文字
a3 = abc...abca bcabcab cabc...abc
# 左に46文字、中央に7文字、右に46文字
a4 = abc...abc abcabcabc abc...abc
# 左に45文字、中央に9文字、右に45文字
:
a44 =  abcabcabcabc...abcabcabcabc 
# 左に0文字、中央に99文字、右に0文字

という法則で考えることができる。

なので、abcabc...abcabcという99文字の文字列を3つに分割して、その分割の位置を1つずつずらしてい苦ことで、45パターンの文字列ができて、それが標準入力の2行目の文字列と合致するものがあれば条件としては適合する、という感じのはず。。。

なのだけど、これを叶えるためのコードを書けない涙。
今回はギブアップ。

●他の方の回答例

上位の方々の回答を見ても正直ピンとこない。。。
色々と見て、下記の回答を読み解く、という形で今回は理解を試みることにする。

n = gets.to_i / 2
s = gets.chomp
a = "b"
(1..n).each do |i|
  a = "a#{a}c" if i % 3 == 1
  a = "c#{a}a" if i % 3 == 2
  a = "b#{a}b" if i % 3 == 0
end
puts a == s ? n : -1

まず1行目の標準入力Nを/2して変数nに入れる。問題の、「整数K」が存在する場合はNが奇数になるはずなので、小数点を切り捨てた数値がnに入る。

で、2行目の変数sは一旦取得だけしておいて、最後に使うのか。

続いて、「整数K」が存在する場合は文字列の中央が必ずbになることはわかっているので、変数aにbを入れる。ふむふむ。

そして肝心の箇所。初めに作った変数n回分をeachで回す。その中身は、

  • nを割ったあまりが1なら両サイドにそれぞれacを追加
  • nを割ったあまりが2なら両サイドにそれぞれcaを追加
  • nを割ったあまりが0なら両サイドどちらにもbを追加

なるほど、このeachを回すことで変数aが、最終的にあるべき姿(って言えばいのか?)に変化する。

最後にこの変数aと変数sを比較して等しければ変数nを出力、等しくなければ-1を出力。

う〜〜〜ん、なんとなくわかったような気もする…!

●出てきたメソッド等

公式リファレンスを見る訓練。

今回は特に無し。

■振り返りなど

めっちゃ難しかった。
こういう類の問題を解けるだけの能力がまだ足りないんだなと痛感。