昨日とあるコーディングテストを受けたので記録. 一応問題名みたいなのもあったけど忘れたので仮で. あと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一応は用意されてた問題を全部解けたのでいいでしょ. きっと. 普段のプロコンでは次の２つのズルが出来る.