まず、所感から入る。
難解だ。
何を言っているのか分からない。東西に走る車の通過数を答えろ、というような設問だが、何を答えればいいのか判然としない。
どうしても分からないため、答えを参考に、設問の意味の理解に努めた。
すると、ようやく分かった。
例えば、以下の配列が与えられたとする。
A[0] = 0
A[1] = 1
A[2] = 0
A[3] = 1
A[4] = 1
このとき、A[0] ～ A[4] まで５つの車が存在し、それぞれの車が東に向かう（[0]）か、西に向かう
（[1]）かが示されている。
例えば、A[0] = 0 は、１台目の車が東に向かうことを意味し、A[1] = 0 は、２台目の車が西に向かうことを意味する。
なので、この時点で一つの組が生まれる。それは、(0, 1) になる。なぜなら、１台目と２台目がpassing (≒行き違う）しているからである。残りの A[2] ～ A[4] においても行き違う車の組を探し、組の数を数える、という問題。
1st
今回は、上記答えのコードを見て設問の意味を理解したため、コード自体が頭に残っており、自分でコードを考えても、どうしても先人のコードが脳裏をよぎり、その考え方から離れられなかったため、考え方は先人のコードのものとなっている。
| 正確性 | 性能 | スコア |
|---|---|---|
| 100% | 100% | 100% |
function solution($A) {
$cnt = 0;
$east = 0;
foreach($A as $value) {
// Count cars traveling east
if(0 == $value) {
$east++;
// Count pairs of cars passing
} else {
$cnt += $east;
// If the number of pairs exceeds 1,000,000,000, return -1
if($cnt > 1000000000) {
return -1;
}
}
}
return $cnt;
}
考え方は先人と同じで、先人のコードは java で書かれていたためforループだったが、このコードはPHP なので、foreachを使った、というのが唯一の違い。（変数名も少し違う。）
この考え方は、東に向かう車(east)が増えた分、西に向かう車(west)と行き違う数も増えるため、加算代入によって west += east とするもの。配列の要素の値が 0 のときはもちろん east++ となるだけ。
かなりシンプルで分かりやすい考え方。
対して、最初に筆者が考えたのは、組み合わせとして解けないか、というもの。配列のすべての要素を異なる値ととらえ、考えられる (0, 1) の組み合わせをすべて数えれば、答えになるはず。だが、この場合、恐らく O(N^2) の計算量となるため、性能要件でアウト。というより、そもそもコードに表現し切れない気がする。ぱっと調べた感じ、C言語では、再帰的関数を使って実現しているよう。
まあ、こういう難しそうを一つずつ解決していくことでスキルが向上していくんやろうけど。
悲しいかな、やる気が出ない。