コンテンツへスキップ

【Ruby基礎】AtCoder Beginner Contest 007 B – 辞書式順序

  • by

INDEX

■はじめに

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

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

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

■問題

●出典

AtCoder Beginner Contest 007のB問題
https://atcoder.jp/contests/abc007/tasks/abc007_2

●問題文

文字列 A が与えられる。小文字アルファベット(a-z)のみを使って辞書順比較したとき文字列 A より小さいものを1つ何でも良いので出力せよ。ただし、文字列は 1 文字以上 100 文字以下でなければならない。もし存在しない場合は "-1" を出力せよ。

ただし、ある文字列 S=S1 S2 ... Sn と T=T1 T2 ... Tm について、辞書順比較した際に S<T であるとは、次のどちらか一方の状態が成り立っていることを言う。

  • ある整数 i(1≦i≦min(n,m)) に関して、 1≦j≦i−1 を満たすどの整数 j に関しても Sj =Tj が成立し、かつ Si <Ti が成立する
  • 任意の整数 i(1≦i≦min(n,m)) に関して、 常に Si =Ti が成立し、かつ ∣S∣<∣T∣ である。ただし ∣X∣ は文字列 X の長さを表すものとする。

なにやら頭が痛くなる記述だが、言い換えると次の通りである。

  • それぞれの文字列の同じ位置同士を先頭から比較していって、初めて不一致になったら、その文字同士の(アルファベットでの)比較結果が文字列の全体の比較結果である。 例えば、"abcd" と "ax" を比較すると、2 文字目で、 ′b′ < ′x′ となるので、"abcd"<"ax" である。
  • もし、比較している途中で片方の文字列が尽きてしまったら、文字列の長さが短い方が小さい。例えば "ab"<"abc"である。

●入力

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

A
  • 1 行目には、文字列 A(1≦∣A∣≦11) が与えられる。∣A∣は文字列 ∣A∣ の長さを表す。Aは小文字アルファベット(a-z)のみから成る。

●出力

文字列 A より小さい文字列を 1 つ 1 行に出力せよ。ただし、小文字アルファベット(a-z)のみを用いており、長さは1以上100以下でなければならない。解が複数ある場合はどれを出力しても良い。存在しない場合は、代わりに "-1" を出力すること。出力の末尾に改行をいれること。

■回答

●愚直に書く

これは…。問題文がものすごくややこしそうだけど回答はパッと出せる系では。
要は、aが入力されたら-1で、それ以外の入力に関しては何が来ようとaと返せば条件は満たすのではないだろうか。

a = gets.chomp
puts a == "a" ? "-1" : "a"

通った!!

う〜んこれはメソッド化とかリファクタリングも無くて良いかも…。

●他の方の回答例

上位の皆さんも考え方としては同じだった。

面白かった回答としては下記。

puts gets=="a\n"?-1:?a

chompしない代わりにa\nを条件にしている。今回はこれもアリなのか、なるほど。結構多くの方がこうしていた。

●出てきたメソッド等

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

今回は特に無し。

■振り返りなど

1つ前の問題との難易度の差がすごかった。