26 Dec 2015, 11:25

AOJ へ Emacs から投稿するスクリプトをみつけた

AOJ の問題を最近解いているのだが、 Emacs から投稿するスクリプトがないかなと探していたら、見つけた.

aoj-submit をうつと、web に投稿してくれる。これは便利だ..

ここからが Hack. できれば、ローカルでテストケースを実行したい.

そのためのスクリプトを見つけた.

たとえば、問題番号 1147 のテストをしたいとき、 以下を実行すると、テストケースをダウンロードしてきてローカルで実行してくれる.

oj.py --aoj -i 1147.py 1147

ソースを読むと、html をスクレイピングしてるようなトリッキーなことをしていた.

これを Emacs から叩けるように、メソッドを追加してみた.

(defcustom aoj-ojpy-path nil "Your oj.py path")

(defun aoj-test ()
  (interactive)
  (shell-command (concat aoj-ojpy-path " --aoj -i "
                         (file-name-nondirectory (buffer-file-name)) " " (aoj--problemNO))))

これで、Emacs からテスト実行 -> 提出ができるようになった.

12 Dec 2015, 08:05

Pythonでナップザック問題(AOJ)

今日は、ナップザック問題を勉強しました.

今回は、AOJの問題をPythonで解いてみます.

ナップザック問題については、以下のサイトを参考にしました.

以下、記号の意味などは、上記サイトを参照願いします.

深さ優先探索

[sourcecode language=”python” title=”” ]
N, W = map(int, raw_input().split())

v = [0] * N
w = [0] * N

for i in range(N):
v[i], w[i] = map(int, raw_input().split())

def rec(i, j):
if i == N:
res = 0
elif j < w[i]: res = rec(i + 1, j) else: res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i]) return res print(rec(0, W)) [/sourcecode]

これだと、時間制限に引っかかって、テストが通らない

  <div id="outline-container-orgheadline2" class="outline-2">
    <h2 id="orgheadline2">
      メモ化再帰
    </h2>

    <div class="outline-text-2" id="text-orgheadline2">
      <p>
        深さ優先探索を改良.
      </p>

      <p>
        メモ化のためのテーブル dp を宣言する.
      </p>

      <p>
        rec(i,j)の結果は、(i,j)によって一意に決まるため、計算結果の dp[i][j]を返す.
      </p>

      <p>
        [sourcecode language=&#8221;python&#8221; title=&#8221;&#8221; ]<br /> N, W = map(int, raw_input().split())
      </p>

      <p>
        v = [0] * N<br /> w = [0] * N<br /> dp = [[-1 for i in range(W + 1)] for j in range(N + 1)]
      </p>

      <p>
        for i in range(N):<br /> v[i], w[i] = map(int, raw_input().split())
      </p>

      <p>
        def rec(i, j):<br /> if dp[i][j] != -1:<br /> return dp[i][j]
      </p>

      <p>
        if i == N:<br /> res = 0<br /> elif j < w[i]: res = rec(i + 1, j) else: res = max(rec(i + 1, j), rec(i + 1, j - w[i]) + v[i]) dp[i][j] = res return res print(rec(0, W)) [/sourcecode] </div> </div> 

        <div id="outline-container-orgheadline3" class="outline-2">
          <h2 id="orgheadline3">
            動的計画法
          </h2>

          <div class="outline-text-2" id="text-orgheadline3">
            <p>
              漸化式を解く.
            </p>

            <p>
              [sourcecode language=&#8221;python&#8221; title=&#8221;&#8221; ]<br /> N, W = map(int, raw_input().split())
            </p>

            <p>
              v = [0] * N<br /> w = [0] * N<br /> dp = [[0 for i in range(W + 1)] for j in range(N + 1)]
            </p>

            <p>
              for i in range(N):<br /> v[i], w[i] = map(int, raw_input().split())
            </p>

            <p>
              for i in range(N &#8211; 1, -1, -1):<br /> for j in range(W + 1):<br /> if j < w[i]: dp[i][j] = dp[i + 1][j] else: dp[i][j] = max(dp[i + 1][j], dp[i + 1][j - w[i]] + v[i]) print(dp[0][W]) [/sourcecode] </div> </div> 

              <div id="outline-container-orgheadline4" class="outline-2">
                <h2 id="orgheadline4">
                  Special Thanks
                </h2>

                <div class="outline-text-2" id="text-orgheadline4">
                  <ul class="org-ul">
                    <li>
                      <a href="http://www.itmedia.co.jp/enterprise/articles/1005/15/news002.html">最強最速アルゴリズマー養成講座:病みつきになる「動的計画法」、その深淵に迫る (1/4) &#8211; ITmedia エンタープライズ</a>
                    </li>
                  </ul>
                </div>
              </div>

05 Dec 2015, 06:55

リスト探索(線形探索・二分探索) – Python

こんにちは。今日は、AOJ の問題に取り組むことで、探索の勉強をしてみました!

線形探索

[sourcecode language=”text” title=”” ]
リストや配列に入ったデータに対する検索を行うにあたって、
先頭から順に比較を行い、それが見つかれば終了する.
[/sourcecode]

ALDS1_4_A:

<div class="outline-text-3" id="text-orgheadline2">
  <p>
    サンプル問題(AOJ): <a href="http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_A&lang=jp">http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_A&lang=jp</a>
  </p>

  <p>
    [sourcecode language=&#8221;python&#8221; title=&#8221;&#8221; ]<br /> n = int(input())<br /> S = list(map(int, input().split()))<br /> q = int(input())<br /> T = list(map(int, input().split()))
  </p>

  <p>
    def linearSearch(A, n, key):<br /> i = 0<br /> A.append(key) # 番兵<br /> while A[i] != key:<br /> i += 1<br /> A.pop()<br /> return i != n
  </p>

  <p>
    count = 0
  </p>

  <p>
    for i in range(q):<br /> if linearSearch(S, n, T[i]):<br /> count += 1
  </p>

  <p>
    print(count)<br /> [/sourcecode]
  </p>
</div>

二分探索

ソート済み配列に対する探索アルゴリズムの一つ

[sourcecode language=”text” title=”” ]
ソート済みのリストや配列に入ったデータ(同一の値はないものとする)に対する検索を行うにあたって、
中央の値を見て、検索したい値との大小関係を用いて、
検索したい値が中央の値の右にあるか、左にあるかを判断して、
片側には存在しないことを確かめながら検索していく
[/sourcecode]

ALDS1_4_B:

<div class="outline-text-3" id="text-orgheadline4">
  <p>
    サンプル問題(AOJ): <a href="http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B&lang=jp">http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_4_B&lang=jp</a>
  </p>

  <p>
    [sourcecode language=&#8221;python&#8221; title=&#8221;&#8221; ]<br /> n = int(input())<br /> S = list(map(int, input().split()))<br /> q = int(input())<br /> T = list(map(int, input().split()))
  </p>

  <p>
    def binary_search(A, key):<br /> left = 0<br /> right = n<br /> while left < right: mid = int((left + right)/2) if A[mid] == key: return True elif key < A[mid]: right = mid else: left = mid + 1 return False cnt = 0 for i in T: if binary_search(S, i): cnt += 1 print(cnt) [/sourcecode] </div> </div> </div> 

    <div id="outline-container-orgheadline5" class="outline-2">
      <h2 id="orgheadline5">
        Pythonの(文字列)探索ライブラリ
      </h2>

      <div class="outline-text-2" id="text-orgheadline5">
        <p>
          find, indexがある.
        </p>

        <ul class="org-ul">
          <li>
            <a href="http://python.civic-apps.com/string-find/">文字列検索系メソッド find, index, startswith, endswidth » Python Snippets</a>
          </li>
        </ul>
      </div>
    </div>