Seleniumにおける待ち合わせの概念
Selenium
- このページの重要な点を翻訳
Implicit Wait(暗黙的待ち合わせ)
Explicit Wait(明示的待ち合わせ)
- 明示的待ち合わせは、コードを実行する前に特定の状態になるまでWebdriverのインスタンスのために設定、実装されるコードのこと
- WebDriverWaitとExpectedConditionで定義される特定のメソッドと状態は明示的待ち合わせを実装するための一つの手法です
プロジェクトオイラーProblem 12を解いてみた
今回はほとんど自力では解けてないので、翻訳実装しただけです。
問題
三角数の数列は自然数の和で表わされ, 7番目の三角数は 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 である. 三角数の最初の10項は: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ... となる. 最初の7項について, その約数を列挙すると, 以下のとおり. 1: 1 3: 1,3 6: 1,2,3,6 10: 1,2,5,10 15: 1,3,5,15 21: 1,3,7,21 28: 1,2,4,7,14,28 これから, 7番目の三角数である28は, 5個より多く約数をもつ最初の三角数であることが分かる. では, 500個より多く約数をもつ最初の三角数はいくつか.
解答
五角数を求めるのも、その約数を求めるのも至極簡単なのですが500を超える約数を愚直に求めるとプログラムの実行が終わりません。
結局私はそこの工夫の仕方が思いつかなかったので他者の回答を読むことにしました。
参考にした解答
解答の方法はリンク先の方々に任せるとして、ポイントを載せる。
問題のポイント
アルゴリズム上の工夫:
- 一度計算した約数の個数は、保存しておいて再利用する
- もし、nや(n+1)/2等の数が、再び m(m+1)のかたちで表せるなら、前出の式が再び適用できる(このパターンは意外に多い)
メモ
- 約数F(n)F(m)は互いに素(!)なので、掛け算で求められる。
- ここはマジで思いつかなかった、掛け算で求められるので約数自体を保存しておく必要はなく数だけ数えればよい。
- nや(n+1)/2等の数が、再び m(m+1)のかたちで表せる
- これを求める方法がわからなかったのだが、コードを見れば一目瞭然、nの平方根を求め+1で掛け算したときnになるか見ている
ソースコード
@fact = {1=>1,2=>2} def num_factors(n) return @fact[n] if @fact.has_key?(n) r = Math.sqrt(n).to_i num = 0 if r*(r+1)==n num = num_factors(r)*num_factors(r+1) else i=1 while i<r if n % i==0 num +=1 end i+=1 end num *= 2 num += 1 if r*r==n end @fact[n] = num return num end n = 2 loop { if n.even? fn = num_factors(n/2) * num_factors(n+1) else fn = num_factors(n) * num_factors((n+1)/2) end if fn >= 500 printf "%d = (%d * %d)/2, it has %d factors", n*(n+1)/2, n, n+1, fn break end @fact[n*(n+1)/2] = fn n+=1 }
AtCoder Beginner Contest 009 (辞書式順序ふたたび) を解いてみた
ABC 009 C問題に使われるアルゴリズム要素は貪欲法です。貪欲法自体は定型のアルゴリズムがあるわけではないので、知識ではなく地頭を問う問題です。
- 問題文
- 文字列Sとその長さN、そして入れ替えしていい文字数Kが与えられる
- K文字だけ入れ替えて辞書順で最小になる文字列を求めよ
考え方
7 2 atcoder
の場合、2文字入れ替え可能。答えはactoderになる。文字列を前から順に見ていって、辞書順で最小になるようにすればよい。
疑似コード
- 解説にある疑似コードをもう少し詳細に書き下してみた
(解説の疑似コード) T ← "" for i in 0 to N-1 for c in (使用可能な文字を辞書順で) if (T+cにして大丈夫なら) T ← T + c break (書き下し) def available(t) Sの文字列からtの文字列を除いてソートしたもの T ← "" for i in 0 to N-1 for c in available(t) T ← T + c // T[i] = c k = i文字目まででの変更数 switch_count, t_tmp = 残り文字列を埋めた時の変更数と文字列を返す if k + switch_count == K t_tmpを表示して終了 elsif k + switch_count > K # 次の文字を試す else # 次のiを試す break end
考えるべきだったこと
- 辞書順=貪欲法までは思いつくべき
- 解いてみると意外と愚直なソースになる
- Kと変更数の関係でバグらせまくった。これは単純に経験不足か…