池沼みたいな問題解いた(AOJ 2362 Chicken or the Egg)
ブログを更新するような内容がない生活を送ってます。こむぎ娘です。
あまりにも書くことがないので、最近AOJで解いた問題についてちょっと書いてみようかなと思います。
当然解法とかを含むので、まだ解いてない人やこれから解こうと思ってる人は見ない方がいいかもしれません。
ヾ(๑╹◡╹)ﾉ"
以下、考え方・解法を含みます。
何故この問題？
まず、この問題が普通と違う点は、何をすればいいか明確に与えられていないという点だと思います。問題に目を通しただけでは、何をすればいいか分からない人も多いような気がします(私もそうでした)。
とりあえず、サンプルを考えながら、どのようにして解くかを考えてみました。
考え方 - サンプルを見ながら
- "eggchicken" -> chicken
- "eggchickenchickenegg" -> chicken
- "eggchickenegg" -> egg
- "chickeneggeggchicken" -> egg
- "eggeggchicken" -> chicken
ちょっと何を言ってるのかよく分からないのですが、条件で同じものが続く時に区切る、みたいなことが書いてあったので、それは後回しにして、同じものが続かないパターンでの答えを考えてみましょう。
- "eggchicken" -> chicken
- "eggchickenegg" -> egg
つまり、後ろにある方が先に生まれた、ってことなんじゃないでしょうか？
次に、同じものが続くパターンで、その場所で区切ってみましょう。
- "eggchickenchickenegg" -> ["eggchicken", "chickenegg"] -> chicken
- "chickeneggeggchicken" -> ["chickenegg", "eggchicken"] -> egg
- "eggeggchicken" -> ["egg", "eggchicken"] -> chicken
先ほどのパターンから、後ろの方が先となるはずですし、問題文には、
どうやら同じ時代として産まれたものの内，より文の前方に書かれた方が先に産まれたようだ．
という記述もあるので、上2つのパターンはなんとなく分かるような気がします。しかし最後のパターンに疑問が残ります。
ここで、問題文の以下の点に注目しました。
調査をする内に，文は同一単語が連続で出てきたときに分割されることがわかった． "eggchickenchickenegg"であれば，"eggchicken"と"chickenegg"という文に分割される． 複数の文がある場合は，先頭の単語から順番に同じ時代に産まれたことを表すらしい．
分割された複数の文が並行的(？)に解釈されるのかな？
例: "eggchickenchickeneggchickeneggeggchickeneggeggchickeneggchicken"
- > ["eggchicken", "chickeneggchickenegg", "eggchickenegg", "eggchickeneggchicken"]
"eggchicken" -> chicken(length:2)
"chickeneggchickenegg" -> egg(length:4)
"eggchickenegg" -> egg(length:3)
"eggchickeneggchicken" -> chicken(length:4)
ここでのlengthは要素の連鎖数(chicken, eggをそれぞれ1要素とする)である。つまりどれだけ昔か、という基準であるとする。
4つのうち、連鎖数が一番大きいのは2番目と4番目であるが、前方にある方が先に生まれた、というルールに則ると、一番最初に生まれたのは2番目の要素の最後のeggとなる。
解法 - どうすればいい？
以下のルールに従うことにしよう。
- まず同じ単語が連続で出てくる箇所で分割する。
- 次に、分割した要素ごと、単語の数を数える。
- 単語の数が一番大きい要素の中で、一番最初にあるものの最後の単語が答えとなる
これを適用すると、先ほどのいくつかの例を全て満たす。
うまく実装して提出したらACしました。コードは酷いものなので見せられません。
٩(๑╹ω╹)۶？
なんかよく分からない問題でした。サンプルを読みながら直感でコードを書いたら通ってしまったので何とも言えません。
でもこれ、A問題相当らしいけど絶対違うでしょ…
これから少しずつ問題を解いて、気になる問題があったらまたここに投稿しようかなと思います。
