大体5月から最近くらいまで
Haskell にあるリスト (linked-list, cons-list) は実質そのままスタックとして用いることができる. そして深さ優先探索 (DFS) はスタックに次訪れる状態を入れることで書けるのでとても相性がよく、Haskell で DFS は簡単である. この双対となるのが幅優先探索 (BFS) であり、これはキューに次訪れる状態を入れて持てば簡単に書ける. Haskell で BFS する方法として以前には余再帰を書いた taglibro/2014/06/16 のが、もう余再帰がなんだかわからんし、このコードも読めないので二度と書ける自信がない.
そういえばキューというのはスタック２つで表現できる. その実現方法は簡単で適当にググれば出てくる (例: スタック２つでキューを作る ).
これ使えば難しい概念を使わなくても BFS も簡単に書けることに気づいた.
data Tree = Leaf | Node Int Tree Tree deriving Show
-- ダミーデータとして完全2分木を使う
nibun :: Int -> Tree
nibun n = nibun_sub n 0
where
nibun_sub 0 i = Leaf
nibun_sub n i = Node i (nibun_sub (n - 1) (2 * i + 1)) (nibun_sub (n - 1) (2 * i + 2))
-- まずはスタック一つで深さ優先探索
-- 訪れたノードを返すことにする
dfs :: Tree -> [Int]
dfs tr = dfs_sub tr [] []
where
dfs_sub Leaf [] order = reverse order
dfs_sub Leaf (x:xs) order = dfs_sub x xs order
dfs_sub (Node val left right) stack order = dfs_sub left (right:stack) (val:order)
-- 次はスタック2つをもたせる
-- 1つ目が push 用で二つ目が pop 用 （一番最後のリストは訪れた順を保存して最後に返す用）
bfs :: Tree -> [Int]
bfs tr = bfs_sub tr [] [] []
where
bfs_sub tr q@(x:xs) [] order = bfs_sub tr [] (reverse q) order -- queue
bfs_sub Leaf [] [] order = reverse order
bfs_sub Leaf queue_left (x:xs) order = bfs_sub x queue_left xs order
bfs_sub (Node val left right) [] [] order = bfs_sub left [] [right] (val:order)
bfs_sub (Node val left right) queue_left (x:xs) order = bfs_sub x (left:right:queue_left) xs (val:order)
main :: IO ()
main = do
print $ tr
print $ dfs tr
print $ bfs tr
where
tr = nibun 3
友人が言っていたのを無断で借りているフレーズ
平日は休日が来るのを待ち、休日は平日が来るのを待っている。
それと、梅雨が明けるのを待っている。
昨日とあるコーディングテストを受けたので記録. 一応問題名みたいなのもあったけど忘れたので仮で. あとPythonで書いたけど途中で言語を変えたければ変えても良いと言われた. 実際にプログラムは動かさないし存在しないメソッドも時々用いたのでハナから動かないただの擬似コード. なので Python で良かったと思う.
オブジェクトが \(N\) 個あり, これを一列に並べたい. ただしいくつかの制約が予め与えられるのでこれに合致するように並べる必要がある. 制約は「 \(i\) 番目のオブジェクトは \(j\) 番目より左 (または右) にある」というもの.
まず, そもそもオブジェクトの表現方法から自分で決める必要があったが, 普通に自然数 (int) にすると言った. 制約についてだが, 左右対称なので, 右という制約は左に書き換えられ, すべて「 \(i\) は \(j\) の左にある」という形式をしてると思ってればいい. で, 解法として \(i\) から \(j\) にエッジを張ってトポロジカルソートをすれば出来るだろうと言うと, いいんじゃない？ と合意が取れたのでコーディングを始めた. トポロジカルソートの実装は詰まった. 覚えてたのはDFSして帰りがけ順にノード番号をメモすればなんか答えっぽいものが得られるということだけ. それだと明らかに逆順が得られるので最後にリバースすれば答えかなと思った. 口頭でそんな感じのことだけ言ったらこの問題は何故かACした（システムの都合上, 個別のジャッジ結果はわからないので雰囲気で察しただけだけど, たぶんACということだと思う）.
トポロジカルソートは実際には, 前処理としてエッジの向きを逆にしたグラフを作ってから, それの上で DFS する必要があったが, 今の場合は左右対称なので, 口頭で言った方法であってた.
忘れた. 簡単ななにか.
文字列が与えられる. 隣り合う二文字であって大文字と小文字のペアになってるものを消す操作を繰り返し適用する. 例えば axXb は ab になるし, 操作は可能な限り繰り返すので axXA という文字列は空文字列 になる. この処理を書けという問題.
実際に繰り返しの処理をシミュレーションすればもちろん出来るが, それは簡単すぎるからワンパス (要は \(O(n)\) ) で書けという指示が最初にあった.
そこまでに読んだ文字列をスタックで管理して, 次の読む文字がスタックの頭の文字とペアになってたら消すということをすれば, 頭から一巡で舐めるだけなので, 時間は \(O(n)\) . 空間も元の文字列を除いても \(O(n)\) 必要になるが.
def solve(s):
stack = []
for c in s:
if match(stack.top(), c):
stack.pop()
else:
stack.push(c)
return ''.join(stack)
次に, stack という変数を消してみろと言われた. 要は空間量を削った方法を要求してる？ スタックに入ってる文字は大抵は連続のスパンになってるので, 添字だけ持ってればいい？ みたいなことを言った. 正解がわからん.
忘れた. 簡単ななにか.
文字列とパターンが与えられるのでそのマッチ関数 (完全マッチ) を書けという問題. パターンは普通の英字に加えて * という文字がたかだか一度だけ出現する. これは正規表現でいう .* として機能する.
初め私は * がたかだか一度だという制約を見落としていて, 編集距離みたいなDPをしようとしていた. すなわち,
def solve(s, pattern):
Run DP:
dp[i][j] = (s[0..i], pattern[0..j]) でマッチする最大文字数
return dp[len(s)-1][len(pattern)-1] == len(s)
という方針でやってた. とっさに DP の中身の処理が書けなくて詰まってたら * が一度だけという制約をそこで教えられ書き直した.
def solve(s, pattern):
if '*' in pattern:
p1, p2 = pattern.split('*')
return s.beginwith(p1) and s.endwith(p2) and len(s) <= len(pattern)
else:
return s == pattern
一応は用意されてた問題を全部解けたのでいいでしょ. きっと. 普段のプロコンでは次の２つのズルが出来る.