コンテンツへスキップ

【Ruby基礎】AtCoder Beginner Contest 032 B – 高橋君とパスワード

INDEX

■はじめに

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

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

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

■問題

●出典

AtCoder Beginner Contest 032のB問題
https://atcoder.jp/contests/abc032/tasks/abc032_b

●問題文

高橋君の会社には、秘密の金庫があります。この金庫にはパスワードをかけているのですが、高橋君はそのパスワードを忘れてしまいました。 しかし、幸運なことに、手元にはパスワードのヒントが以下のように書かれていました。

  • パスワードは、この紙に書かれている文字列 s の長さ k の部分文字列(※)のどれかである。

高橋君は、ありうるパスワードを全部試せば金庫を開けられる！と喜びました。 しかし、文字列 s はとても長い可能性があるし、しかも同じ部分文字列が複数個文字列 s 中に存在する可能性もあります。明らかに、重複したパスワードを繰り返し試す必要はありません。 そこで、手動で全てのパスワードを試す前に、試す必要がある異なるパスワードの数がいくつあるかを数えることにしました。

あなたの仕事は、文字列 s の内容が与えられるので、試す必要がある異なるパスワードの数がいくつあるかを高橋君に教えてあげることです。

(※)文字列 s の「部分文字列」とは、文字列 s に含まれるある区間を取り出した文字列のことです。 例えば、abc の部分文字列として a,b,c,ab,bc,abc などが挙げられます。 ac や ba などは部分文字列ではないことに注意してください。

●入力

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

s
k
  • 1 行目には、ヒントの紙に書かれている文字列 s(1≦∣s∣≦300) が与えられる。s は英小文字(a-z)のみから成る。∣s∣ は文字列 s の長さを表す。
  • 2 行目には、パスワードとしてありうる整数 k(1≦k≦300) が与えられる。 k は ∣s∣ よりも大きいことがある。

●出力

出力は以下の形式で標準出力に行うこと。
1 行目に、パスワードとして考えられる文字列の数を出力せよ。末尾の改行を忘れないこと。

■回答

●愚直に書く

これは苦手なやつだ…。

標準入力としては1行目の文字列を取り、2行目の整数を取る。

その後にループ処理の中で文字列の中から必要な文字数分だけ順番に要素を取り出してそれを配列に入れていき、最後に重複を省いてカウントすれば良さそう。

と、文字で書くのは良いとしてどうやってコードに落とし込むか…。

（下記に至るまでかなりの試行錯誤があった）

ループの回数は何回だろう？初めの例から考えると、
abcabcで6文字あってその中で2文字の部分文字列を取り出すから、愚直に数え上げると['ab', 'bc', 'ca', 'ab', 'bc']を取り出す。つまり5個取り出す。
全部で6文字ある中から5個取り出す
→全部の文字数 - 部分文字列の文字数 + 1、という感じか。

文字列の中から、n番目からl文字取り出すにはどうすればいいんだろう？
るりまによると、self[nth, len]でnth 文字目から長さ len 文字の部分文字列を新しく作って返します。とのこと。

str = gets.chomp
l = gets.to_i

array = []
(str.length - l + 1).times do |i|
  array << str[i, l]
end

puts array.uniq.size

通った！

●メソッド化して書く

メソッドを作る練習のために、あえてそういう書き方をする。
今日は割愛。

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

これも今日は割愛。
他の方の回答例から学ぶアプローチにする。

●他の方の回答例

上位の方々の回答をざっと眺めた。
ポイントは以下の2つ。

  • .cahrsで文字列を配列に分解する
  • each_consで配列の要素を重複ありで区切っていき、to_aで新しく配列にまとめる

なるほど〜。

整理した回答がこちら。

str = gets.chomp.chars
l = gets.to_i

puts str.each_cons(l).to_a.uniq.size

これで通ることを確認できた。

●出てきたメソッド等

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

■振り返りなど

今日は難しかったけど、まずはこれくらいの難易度をモタつかずに解けるようになりたい。