AtCoder Beginner Contest 137に参加しました。【PHP】

競技プログラミング

2019年8月10日(土)21:00~22:40に開かれました。AtCoder Beginner Contest 137に参加しました。

AtCoder Beginner Contest(ABC)はプログラミングには興味あるけど、何をしていいわからない、そんな人のためのコンテンツです。

問題はAからFまでありだんだんと難しくなっていきます。

今回で3回目の参戦になります。

前回のABC136ではCまでクリアし、Dを解いている最中に終了であったため、今回もそこまではいきたいところです。

ですが、結果としてはCを解いている最中に終了してしまいました泣

A:+-×

整数A,Bの和、差、積から最大の数を出力する問題

A+B,A-B,A*Bを変数に代入してmax関数で値を返せばOK

max関数は配列を渡せば配列内で最大のものを返すし、複数パラメータを渡せば、その中で最も大きいものを返してくれる。

B:One Clue

連続する数列Kが与えられ、あるKが存在する座標Xが指定されたときにKの取り得る値の範囲を求める問題

求める範囲で取り得る最小の値は、X-K+1、最大の値はX+K-1なのでfor分でその最小から最大まで一つずつ出力すれば終わり。

C:Green Bin

文字列sのアナグラムを見つける問題。

結論から言うと考えは間違っていなかったものの、TLEとなってしまいその後、どうしたらいいかわからずタイムアップ!

その後ほかの方の解答を見させていただき再挑戦しました。他の解答を見てどうやればよかったのかわかるのがいいところですね。

  1. 文字列sをstr_splitで一文字ずつに分け、配列に格納
  2. 格納した配列をsortを用いてソート
  3. ソートした文字列をimplodeを用いて再び配列に格納

例(s=youarecute)

  1. str_split(youarecute) → array[y,o,u,a,r,e,c,u,t,e]
  2. sort(array) → array[a,c,e,e,o,r,t,u,u,y]
  3. implode(array) → s[aceeortuuy]

当初の考え

文字列をソートした後、for分を用いてs[i]とs[j]で比較し、イコールであればカウントを増やす方針でプログラムを組んだ。(i<j)

しかし、計算量が多いのかTLEになってしまい、クリアできなかった。
for分で繰り返される回数はiとjの二重構造になっていたためN!=N(N-1)(N-2)2*1回になっている。

解答を見てから

文字列をソートし終わった配列をさらにソートすることでソート後の同じ文字列、すなわちアナグラムになっている文字列をまとめることができることを知った。(すごい!)

この方法で行けば配列の文字列を一時的に保存して次が同じであればカウント、異なればアナグラム終了とすることでアナグラムとなる文字列が何個あるかわかる。個数Xが分かればその組み合わせはXC2=X*(X-1)/2で求められるのでこれをansに+=を用いて代入。

ということでCを解くところまでやって果てました。

Dも取り組もうと思ったのですが、解答を見ても理解できなかったのでこれにて終了です。

今回の成績

Cまで解けなくてもわずかながら上がりますね~

段級が12級から11級になりました。ありがとうございます!

それではまた次回のコンテストで

コメント

タイトルとURLをコピーしました