20 Dec 2015, 08:16

プロコンをはじめたので今後の対策方法について考えた

ひまですることもないし、プログラミングにも興味がなくなってしまったので、 競技プログラミングの勉強をはじめた. プログラミングコンテストの対策についてまとめる.

以前、モチベーションについてはまとめた.

プロコンの動機について

プロコン参加の理由は、以下の通りだ.

  • 素早くコーディングする技術を身につけることができる.
  • プログラミングの基礎体力を身につけることができる.
  • TOEIC のように点数があるので自分の成長を実感できる.
  • 転職活動に利用できる.
  • プロダクトのクソコードから離れて自分の美学を貫いたコードがかける.

それから、Python でプログラミングをしている. 理由は、美しくコードがかけるからだ. C++という選択肢は捨てがたいが、C++よりも Python のほうがシンプルにかける. しかし、Python でプロコンをするのはまだ少数派のため、解答例を見つけるのが難しい,

TopCoder を中心に学習を進めていくつもりだ. 最終目標は TopCoder でイエローコーダになること。 そのためには、まず Div1 に上がること.

プロコンの対策について

プロコンの対策について、 こうすればよいというネット上のリソースをいろいろと検索したものの、よいものが見つからない. TOEIC などはみつかるのに。以下、検索結果を列挙.

現在、以下の本をもっている. 以下、簡単に所感を述べる.

  • 最強最速アルゴリズマー養成講座.(チーター本)

TopCoder の過去問を中心に演習問題が並んでいる.TopCoder 専用問題集.

  • プログラミングコンテストチャレンジブック.(蟻本)

北京オンラインジャッジの過去問を中心に演習問題が並んでいる. 解答例が C++なので、Python で読むには苦痛が伴うところが難点. プロコンで必要なアルゴリズムが網羅されている. 有名な対策本.

  • プログラミングコンテスト攻略のためのアルゴリズムとデータ構造.(ALDS)

アルゴリズムの基礎が、会津オンラインジャンジを利用して学習できる. タイトルに反して、どちらかというと基礎がための要素が強く、 プロコン向けではない気がしている.

Web 上のリソースには以下がある.

最強最速アルゴリズマー養成講座

実践・最強最速のアルゴリズム勉強会:

TopCoder のページにある対策記事(英語)

Python の対策には以下がよい.

効率のよい学習方法は、典型問題の暗記だと思っている. 受験数学をどうすれば解けるようになるか、考えてみると、典型問題を暗記することが 効率がよかったという、高校生のときの体験がある. 数学は暗記だ. 解法パターンを暗記してしまおう.

今後の学習計画について

どう進めればよいものか、なやんでいる. 心にもやもやしているものを書き出してみる.

  • 蟻本 蟻本を読むのが王道な気がするが、Python で取り組むには解答例に乏しい.
  • AOJ 会津オンラインジャッジは素晴らしいシステムだ。Python による解答例も見つかるので、 自分のコードと比較することで勉強にもなる. しかし、解答に対する解説がない問題は、学習の投資に対する効果が薄い.
  • TopCoder 過去問 TopCoder には、Editorial という過去問に対する解説がある. http://apps.topcoder.com/wiki/display/tc/Algorithm+Problem+Set+Analysis

    しかし、英語なので、困る. 日本語でないと、 理解するのに時間がかかるのだ.余計な労力をつかいたくない.

  • プログラミングコンテスト参加 TopCoder, Codeforce, AtCoder…たくさんのコンテストがある。 コンテストに参加すると、モチベーションが高まるのでよいが、 自分のペースで学習することができない点がデメリット. また、体系的に学習できない.

Conclusion

コツコツと続けられて、成果を振り返って確認できるものがよい. そうすると、とにかく無作為に数をこなすよりも、書籍による学習がよいと考えた. ここ数週間のメニューは以下の通りとする.

  • 蟻本を Python で解いで、基礎知識を身につける.
  • TopCoder の過去問を解いて、問題にとにかくなれる.(1日1題目標)
  • 可能な限りプロゴラミングコンテストに参加する。そして、復習する.

追記

<div class="outline-text-3" id="text-orgheadline5">
  <p>
    蟻本、挫折した.ムズかしい. もっと簡単なもので対策をしなければ. 難易度順に問題が並んでいるサイトをみつけた. ICPC-AOJ というサイト.
  </p>

  <ul class="org-ul">
    <li>
      <a href="http://ichyo.jp/aoj-icpc/">http://ichyo.jp/aoj-icpc/</a>
    </li>
  </ul>

  <p>
    AOJ による採点ができる & 難易度順に問題がならんでいる ということで、これを順に解いていくことにするよ..
  </p>

  <p>
    ACM-ICPC のサイトにおすすめ問題が載っている。これを解いていこう. おすすめ. サイトのリンクは POJ だけれども、AOJ で検索すると対応する問題が載っている.
  </p>

  <ul class="org-ul">
    <li>
      <a href="http://www.deqnotes.net/acmicpc/">http://www.deqnotes.net/acmicpc/</a>
    </li>
  </ul>
</div>

追記 2

<div class="outline-text-3" id="text-orgheadline6">
  <p>
    TopCoder の練習方法についてかかれた記事.
  </p>

  <ul class="org-ul">
    <li>
      <a href="https://www.quora.com/How-should-I-practice-so-that-I-will-be-at-a-level-where-I-can-approach-TopCoders-Div1-500-problems-with-confidence">How should I practice so that I will be at a level where I can approach TopCoder&#8217;s Div1-500 problems with confidence? &#8211; Quora</a>
    </li>
  </ul>

  <p>
    TopCoder のチュートリアルがいいらしい.
  </p>

  <ul class="org-ul">
    <li>
      <a href="https://www.topcoder.com/community/data-science/data-science-tutorials/">https://www.topcoder.com/community/data-science/data-science-tutorials/</a>
    </li>
  </ul>
</div>

追記 3

<div class="outline-text-3" id="text-orgheadline7">
  <p>
    twitter の対策方法まとめ
  </p>

  <ul class="org-ul">
    <li>
      <a href="http://togetter.com/li/729445">http://togetter.com/li/729445</a>
    </li>
  </ul>
</div>

19 Dec 2015, 04:57

TopCoder SRM 676 Div2 550 BoardEscapeDiv2(参加)

問題

アリスとボブは、r行およびc列のグリッドに分割された矩形ボードを持っています。 グリッドは、String []型sで記述されています。 Sの各文字は、一つのセルを表します。cellには4つのタイプがあります。

  • ‘E’は終了を表しています。任意の数の終了、おそらくゼロがあるかもしれません。
  • ‘T’は正方形は単一のトークンが含まれていることを意味します。最初はボード全体に正確に一つのトークンが存在することになります。
  • ‘#’は、障害物を表します。
  • ‘。’空のセルを表します。

アリスとボブはこのボード上のゲームをプレイします。 ゲームはintkによってパラメータ化されます。トークンは、最初にその上に数kを持っています。 プレイヤーはアリスから始まる、ターンを交互にかかります。プレイヤーのターンは、以下のステップで構成されています。

  • プレイヤーは、下、左、または右のトークン1平方を上に移動します。トークンは、ボードの端に行くことができない、それが障害物をcellに入力することはできません。
  • このトークンが出口にある場合、それはボードから消えます。
  • それ以外の場合は、トークンの数から1を引きます。トークンの数がゼロの場合、ボードから取り外します。

行動を起こすことができない最初のプレーヤーがゲームを失います。 (すでにボードを去ったとき、トークンにもこだわっているときに発生します。)

アリスとボブの両方を最適にプレイすると仮定すると、あなたはString[]型のを与えられ、intkは、ゲームの勝者を計算します。 当選者の名前を返します:「アリス」または「ボブ」のいずれか。戻り値は、大文字と小文字が区別されることに注意してください。

方針

プレイヤーが2人いて、お互いに最適な戦略を取ったとき勝つのはどちらか、 みたいな問題は、WL-Algorithmsというものを利用して解くらしい.

[sourcecode language=”cpp” title=”” ]
boolean isWinning(State pos){
State[] nextStates = { posから到達できる全ての次の状態 };
for(State s : nextStates){
if(!isWinning(s)) return true;
}
return false;
}
[/sourcecode]

  • 相手を必ず負けさせるような手が存在するなら現在の位置では勝ち決定。
  • そのような手がないないのであれば負け。

参考リンクをはっておく. あとで勉強しよう.

今回は、このアルゴリズムにメモ化再帰を適用した.

解答

[sourcecode language=”python” title=”” ]
MAXN = 200

vx = [1, -1, 0, 0]
vy = [0, 0, 1, -1]
memo = [[[-1 for i in range(MAXN)] for j in range(MAXN)] for k in range(MAXN)]

class BoardEscapeDiv2:
def isWinning(self, s, x, y, move):
n = len(s)
m = len(s[0])

if move == 0: return False
if s[x][y] == ‘E’: return False
if memo[x][y][move] != -1: return memo[x][y][move]

for i in range(4):
nx = x + vx[i]
ny = y + vy[i]
if nx < 0 or ny < 0 or nx >= n or ny >= m or s[nx][ny] == ‘#’:
continue
if not self.isWinning(s, nx, ny, move – 1):
memo[x][y][move] = True
return True

memo[x][y][move] = False
return False

def findWinner(self, s, k):
n = len(s)
m = len(s[0])

for i in range(n):
for j in range(m):
if s[i][j] == ‘T’:
x = i
y = j

return “Alice” if self.isWinning(s, x, y, k) else “Bob”
[/sourcecode]

おわりに

本番では解けなかった. こういう問題をさらりととけないと Div1には上がれないのか… 道は遠いな.

18 Dec 2015, 17:52

TopCoder SRM 676 Div2 250 FarmvilleDiv2(参加)

問題

n個の植物がある. それぞれ time[i]秒成長するのにかかる.

cost[i]をbudgetのなかから支払うと、1秒成長を早めることができる.

time, cost, budgetが与えられる. 植物を育てることのできる時間の最小値をかえせ.

方針

costを昇順にソーティング. costの低い順に時間を計算

  • budgetがまだあるときは、total時間は加算しない.
  • budgetがないときは、time分 total時間を加算する.

解答

timeとcostをインデックスをそろえながらソーティングするよい方法が思い つかなかったので、自力でソーティングアルゴリズムを実装した。

なにかよい方法はないものか。他の人の解答をみて研究することにする.

[sourcecode language=”python” title=”” ]
class FarmvilleDiv2:
def insertion_sort(self, time, cost, N):
for i in range(1, N):
v1 = time[i]
v2 = cost[i]
j = i – 1
while j >= 0 and cost[j] > v2:
time[j + 1] = time[j]
cost[j + 1] = cost[j]
j -= 1
time[j + 1] = v1
cost[j + 1] = v2
return time, cost

def minTime(self, time, cost, budget):
time = list(time)
cost = list(cost)
time, cost = self.insertion_sort(time, cost, len(cost))

ret = 0

for t, c in zip(time, cost):
for i in range(t):
if budget – c >= 0:
budget -= c
else:
ret += 1

return ret
[/sourcecode]

18 Dec 2015, 10:31

TopCoder SRM 575 Div2 250 TheSwapsDivTwo (練習)

TopCoder

問題

int型配列が与えられる。 2個の数値の位置を入れ替える場合、得られるユニークな数列が何通りあるか.

方針

全通り swapしてみて、ユニークな数列の数を数える.

回答

[sourcecode language=”python” title=”” ]
class TheSwapsDivTwo:
def find(self, sequence):
s = set()
n = len(sequence)

for i in range(n – 1):
for j in range(i + 1, n):
l = list(sequence)
l[i], l[j] = l[j], l[i]
s.add(tuple(l))

return len(s)
[/sourcecode]

18 Dec 2015, 03:04

TopCoder SRM 672 Div2 500 SubstitutionCipher

問題

可換暗号の問題. 暗号化のために可換テーブルを利用する。

ところが、この可換テーブルがなくなってしまった。

a,b, y が与えられるので a -> b の変換を手がかりにして、 暗号化されたy から 復号化された文字列xを求めよ。

方針

可換テーブルを b->aの複合ルールから求めてそれを y に適用する.

文字が25文字のとき、全てのアルファベットの中で利用されていない 文字を調べてテーブルに追加する必要がある.

回答

[sourcecode language=”python” title=”” ]
allchar = list(“ABCDEFGHIJKLMNOPQRSTUVWXYZ”)
class SubstitutionCipher:
def notIn(self, s):
return “A”

def decode(self, a, b, y):
cipher = {}

for i in range(len(a)):
cipher[b[i]] = a[i]

if len(cipher) == 25:
remain_a = list(set(allchar) – set(a))[0]
remain_b = list(set(allchar) – set(b))[0]
cipher[remain_b] = remain_a

x = “”
for i in range(len(y)):
if y[i] not in cipher:
return “”
x += cipher[y[i]]

return x
[/sourcecode]

18 Dec 2015, 01:46

TopCoder SRM672 Div2 Easy SetPartialOrder

TopCoder

問題

Intの配列AとBが与えられる。

  • 等しいなら”EQUAL”、
  • AがBのサブセットなら”LESS”、
  • BがAのサブセットなら”GREATER”、
  • それ以外なら”INCOMPARABLE”と返す。

方針

setを使う. サブセットは < で比較するのを始めて知った. issubset というメソッドもあるらしい.

回答

[sourcecode language=”python” title=”” ]
class SetPartialOrder:
def compareSets(self, a, b):
a = set(a)
b = set(b)

if a == b:
return “EQUAL”
elif a < b: return "LESS" elif a > b:
return “GREATER”
else:
return “INCOMPARABLE”
[/sourcecode]

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>

11 Dec 2015, 14:55

TopCoder SRM 675 Div2 500

問題

https://community.topcoder.com/stat?c=problem_statement&pm=14091&rd=16625

n個の街がある。二つの街を移動するには、dist[i][j]時間かかる.

また、k magic pointが与えられる。 magic pointをつかうと移動時間を半分にすることができる.

街0から1への最小の移動時間を求めよ.

方針

ダイクストラ法をつかうのだと思った.

以下のリンクを参考に実装してみた.

ポイントは、magic pointをk回つかうことで、最小の移動時間が変動すること. 0から1へk回 magic pointをつかった結果を記憶しておいて、 最後に、その結果のなかでの最小値を求める.

で、いいのかな?? よくわからず、もう5時間くらい悩んでいるのだけれども。。。

回答

10 Dec 2015, 15:31

TopCoder SRM 675 Div2 250

2年ぶりに TopCoder に参加しました。

以前はC++erだったけど、Pythonに武器を持ち替えて参戦.

事前準備のために20時間くらいトレーニングを積んだ.

結果、easy問題すら解けませんでした。システムテストで落とされました。

落とされた原因を延々と考えていて、ようやく分かった!

Python3だとテストが成功するのだけれども、Python2だと失敗することに気づく.

TopCoderのPythonのバージョンは2系です!!

割り算をすると、python3は、勝手にfloat型になったのでテストが通ったけど、 python2はint型のままなので、小数点以下が計算されなかったという落ち. そして、float型なんて考慮していなかったという別の盲点もあった.

middle 問題は、解けなかった。

09 Dec 2015, 10:42

TopCoderで動的計画法とメモ化再帰の問題を解いてみる(Python)

以下の参考書を元に、TopCoderの対策をしています。

今日は、動的計画法とメモ化再帰について勉強しました.

動的計画法(Dynamic Programming)

[sourcecode language=”text” title=”” ]
対象となる問題を複数の部分問題に分割し、
部分問題の計算結果を記録しながら解いていく手法を総称してこう呼ぶ
[/sourcecode]

分類

<div class="outline-text-3" id="text-orgheadline2">
  <p>
    動的計画法には、トップダウン方式、ボトムアップ方式の二つがある. 以下のように呼ばれることが多い.
  </p>

  <ul class="org-ul">
    <li>
      再帰関数のメモ化 ・・・メモ化再帰、メモ化、トップダウン方式
    </li>
    <li>
      漸化式 + ループ ・・・動的計画法、分割統治法、ボトムアップ方式
    </li>
  </ul>
</div>

トップダウン方式(メモ化再帰)

<div class="outline-text-3" id="text-orgheadline3">
  <p>
    一度計算した結果を覚えておいて、 同じ計算をしようとしたときに記憶していた値を利用する.
  </p>

  <p>
    再帰関数を利用することで、問題を解く.
  </p>
</div>

ボトムアップ方式(漸化式)

<div class="outline-text-3" id="text-orgheadline4">
  <p>
    漸化式を立てて、順々に漸化式を解いていく.
  </p>

  <p>
    for文を回すことで、問題を解く.
  </p>
</div>

問題

SRM413 Div1 Medium

<div class="outline-text-3" id="text-orgheadline5">
  <p>
    以下の問題をPythonで解いてみる.
  </p>

  <ul class="org-ul">
    <li>
      <a href="http://www.itmedia.co.jp/enterprise/articles/1003/06/news002_3.html">最強最速アルゴリズマー養成講座:アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった (3/5) &#8211; ITmedia エンタープライズ</a>
    </li>
    <li>
      <a href="https://community.topcoder.com/stat?c=problem_statement&pm=9922&rd=13504">https://community.topcoder.com/stat?c=problem_statement&pm=9922&rd=13504</a>
    </li>
  </ul>
</div>

<div id="outline-container-orgheadline6" class="outline-4">
  <h4 id="orgheadline6">
    動的計画法
  </h4>

  <div class="outline-text-4" id="text-orgheadline6">
    <p>
      <b>まとめらる処理をまとめて、同じ計算を行わないようにする</b>
    </p>

    <p>
      途中経過をメモしておいて、次の計算で使うというのが動的計画法. ここでは、i を順に計算していく.
    </p>

    <p>
      [sourcecode language=&#8221;python&#8221; title=&#8221;&#8221; ]<br /> class InfiniteSequence2:<br /> def calc(self, n, p, q, x, y):<br /> dp = [0 for i in range(n + 1)]<br /> dp[0] = 1
    </p>

    <p>
      for i in range(1, n + 1):<br /> nexta = i / p &#8211; x<br /> nextb = i / q &#8211; y
    </p>

    <p>
      if nexta <= 0: a = 1 else: a = dp[nexta] if nextb <= 0: b = 1 else: b = dp[nextb] dp[i] = a + b return dp[n] [/sourcecode] </div> </div> 

      <div id="outline-container-orgheadline7" class="outline-4">
        <h4 id="orgheadline7">
          深さ優先探索
        </h4>

        <div class="outline-text-4" id="text-orgheadline7">
          <p>
            トップダウンで探索をしていく.
          </p>

          <p>
            [sourcecode language=&#8221;python&#8221; title=&#8221;&#8221; ]<br /> class InfiniteSequence2:<br /> def calc(self, n, p, q, x, y):<br /> return self.dfs(n, p, q, x, y)
          </p>

          <p>
            def dfs(self, n, p, q, x, y):<br /> if n <= 0: return 1 return self.dfs(n / p - x, p, q, x, y) + self.dfs(n / q - y, p, q, x, y) [/sourcecode] </div> </div> 

            <div id="outline-container-orgheadline8" class="outline-4">
              <h4 id="orgheadline8">
                メモ化再帰
              </h4>

              <div class="outline-text-4" id="text-orgheadline8">
                <p>
                  一度計算した点は覚えておいて、余計な計算をしないのがメモ化再帰.
                </p>

                <p>
                  [sourcecode language=&#8221;python&#8221; title=&#8221;&#8221; ]<br /> class InfiniteSequence2:<br /> def calc(self, n, p, q, x, y):<br /> self.memo = {}<br /> return self.dfs(n, p, q, x, y)
                </p>

                <p>
                  def dfs(self, n, p, q, x, y):<br /> if n <= 0: return 1 if n in self.memo: return self.memo[n] self.memo[n] = self.dfs(n / p - x, p, q, x, y) + self.dfs(n / q - y, p, q, x, y) return self.memo[n] [/sourcecode] </div> </div> </div> </div> 

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

                    <div class="outline-text-2" id="text-orgheadline10">
                      <ul class="org-ul">
                        <li>
                          <a href="http://www.itmedia.co.jp/enterprise/articles/1003/06/news002.html">最強最速アルゴリズマー養成講座:アルゴリズマーの登竜門、「動的計画法・メモ化再帰」はこんなに簡単だった (1/5) &#8211; ITmedia エンタープライズ</a>
                        </li>
                        <li>
                          <a href="http://www.itmedia.co.jp/enterprise/articles/1005/15/news002.html">最強最速アルゴリズマー養成講座:病みつきになる「動的計画法」、その淵に迫る (1/4) &#8211; ITmedia エンタープライズ</a>
                        </li>
                        <li>
                          <a href="http://shindannin.hatenadiary.com/entry/20131208/1386512864">動的計画法が苦手な人が、動的計画法が超苦手な人へアドバイスしてみる &#8211; じじいのプログラミング</a>
                        </li>
                        <li>
                          <a href="http://www.slideshare.net/iwiwi/ss-3578511">プログラミングコンテストでの動的計画法</a>
                        </li>
                      </ul>
                    </div>
                  </div>