【Ruby基礎】AtCoder Beginner Contest 025 A – 25個の文字列

INDEX

■はじめに

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

■問題

●出典

AtCoder Beginner Contest 025のA問題
https://atcoder.jp/contests/abc025/tasks/abc025_a

●問題文

高橋君は短めの呼び名を考えています。呼び名は半角小文字アルファベット 2 文字で構成されます。
高橋君には好きな 5 種類のアルファベットがあります。高橋君は、以下の条件を満たす長さ 2 の文字列すべてを考え、それらの集合を「呼び名候補の集合」と呼ぶことにします。

条件 : 文字列の 1 文字目も 2 文字目も高橋君が好きな 5 種類のアルファベットのいずれかである。

ここで、2 つの長さ 2 の異なる文字列 S,T に関して、S が T よりも辞書順で先に来るというのは、以下の条件のうちのいずれかが満たされたときです。

文字列 S の 1 文字目と文字列 T の 1 文字目が異なり、かつ文字列 S の 1 文字目が文字列 T の 1 文字目よりもアルファベット順 (ABC 順) で先である。
文字列 S の 1 文字目と文字列 T の 1 文字目が同じで、かつ文字列 S の 2 文字目が文字列 T の 2 文字目よりもアルファベット順 (ABC 順) で先である。

例えば、好きなアルファベットが a, b, c, d, e のとき、「呼び名候補の集合」に含まれる文字列は、辞書順に、aa, ab, ac, ad, ae, ba, bb, bc, bd, be, ca, cb, cc, cd, ce, da, db, dc, dd, de, ea, eb, ec, ed, ee となります。
「呼び名候補の集合」を構成する文字列は全部で 25 個あります。高橋君はそれらの文字列を辞書順に並べたときに先頭から N 番目となる文字列を最終的な呼び名にすることにしました。
あなたの課題は、高橋君が定めた最終的な呼び名を求めることです。

●入力

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

S
N

1 行目には、長さ 5 の文字列 S が与えられる。S の各文字はいずれも半角小文字アルファベットであり、S に使われている文字には重複がなく、かつ昇順に並んでいる。すなわち文字列 S の左から i(1≦i≦5) 文字目の文字を ci としたとき、ci≠cj (i≠=j) であり、i＜j ならアルファベット ci はアルファベット cj よりもアルファベット順で前である。
2 行目には、整数 N(1≦N≦25) が与えられる。

●出力

高橋君が定めた最終的な呼び名を 1 行に出力せよ。出力の末尾に改行を入れること

■回答

●愚直に書く

問題文がやたらややこしいけど、要は辞書順の話か。
25個の文字列を昇順に配列にできさえすれば解けるかな？入力値の5個のアルファベットはあらかじめ昇順になっているとのことなので、1-1、1-2、・・・5-4、5-5というように文字列のindexを2つ取ってこればできそうな気がする。
いや、文字列のindexを使うよりもまず5つのアルファベットを配列にして、二重配列にするとかでできるのかな…？頭の中だけではちょっとわからないので書いてみる。

ary = gets.chomp.split("").map(&:to_s)
n = gets.to_i

ary.each do |x|
  ary.each do |y|
    names = x + y
    puts names
  end
end

上記で、25個の組み合わせをズラーっと縦に表示することはできたのだけど、その中からn番目を表示させるというのができない…。
30分くらい経ってしまったのでギブアップ。

●リファクタリング／別アプローチ

ギブアップしたのでリファクタリングも無し。

●他の方の回答例

上位の方々の回答が皆さんこんな感じでn/5とn%5を使っている。

s = gets.chomp
n = gets.to_i - 1
puts s[n/5] + s[n%5]

n/5とn%5って何？？どうしてこれで出せるのか…？

nの方で-1してるのはインデックスが0から始まることの調整か。

仮に入力が

abcde
8

だとして、
まずn/5というのは、7/5なので1になる。これは、1文字目が2番目の文字（ここではb）になることを示す。
続いてn%5というのは7%5なので2になる。これは2文字目が3番目の文字（ここではc）になることを示す。

ということで、出てきた結果が正答になるのはわかったけど、なんでこれで良いのかがまだわかっていない。
パズルのピースがはまりそうでまだちゃんとハマっていない感じ…。

色々考えた結果、
5行5列に並んだ要素の中から、n/5で何行目かを指定して、n%5で何列目かを指定している、という感じな気がする。下記の表がイメージ。

-	a	b	c	d	e
a	aa	ab	ac	ad	ae
b	ba	bb	bc	bd	be
c	ca	cb	cc	cd	ce
d	da	db	dc	dd	de
e	ea	eb	ec	ed	ee

なるほど〜。上位層の結構たくさんの方々はこの書き方だけど、一般的な考え方なのかな…全然思いつかなかったしまだ100%スッキリはできていない…。

●出てきたメソッド等

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

特に無し

■振り返りなど

今回は特に難しかった。解き方が分かっていればコード自体はシンプル。