naoya_t@hatenablog

いわゆるチラシノウラであります

Codeforces Round #425 (Div. 2)

久々のリアルタイム参加

いつも通りC(挫けた)→B→A
レーティングは 1676→1679 (+3)
f:id:n4_t:20170725104225p:plain
診断人さんの活躍が光る

C. Strange Radiation (x57)

http://codeforces.com/contest/832/problem/C
(長考)
後ろから閃光を浴びて光子加速、だけじゃなくて、人間が閃光に追いつくケースもある?
とりあえず数式を立てて、爆弾との前後関係や速度比によって  ̄|/ ̄、 ̄| ̄、 ̄\| ̄ のようなグラフになるのは分かる
これimosみたいになるやつ?
(後回し)

後回し

B, Aと通して残り24分弱…これ誰も解いてないじゃん(みんなDに行ってる)
Dを読みに行ったりで
成果は出せず

終了後

いや、欲しいのは合計じゃない。minのmax。

B. Petya and Exam (x1469)

http://codeforces.com/contest/832/problem/B
正規表現に変換して解ける?とか一瞬思ったけど、*が高々1回しか出現しないことが分かっているので愚直にマッチング。
パターンに*が含まれる場合と含まれない場合に分けた。
・含まれない場合は、文字数が同じで、クエリの?の位置はgoodな文字のどれかであること(これはO(1)で調べられる)、それ以外はパターンの当該位置と同じ文字であること。
・含まれる場合は、*の前、*部分、*の後、の3パートに分けて考える(それぞれ長さゼロの可能性あり)。前後については含まれない場合のマッチングと同じで、*部分はgoodでない文字のどれかであること(これもO(1))
というわけでO(Σ|q|)で解ける。
→AC
Submission #28846854 - Codeforces

終了後

python正規表現を使った解法で書いてみた。最悪ケースでTLE出るね…先頭に*があるときつい。

import re

good = raw_input().rstrip()
q = '[' + good + ']'
a = '[^' + good + ']*'

_pat = raw_input().rstrip()
pat = '^' + ''.join([q if ch == '?' else a if ch == '*' else ch for ch in _pat]) + '$'
# print pat
r = re.compile(pat)

n = int(raw_input().rstrip())
for i in xrange(n):
    query = raw_input().rstrip()
    # print i, query, r.match(query)
    print 'YES' if r.match(query) else 'NO'

Submission #28860237 - Codeforces

・長さが固定になるように、[^good]* だったのをクエリの長さに応じて [^good]{|query|-|pattern|} みたいにしてみた →まだTLE
・同じ長さのクエリの時は同じ正規表現を使い回すようにメモ化 →TLE
・TLEのパターンを見たら ?????????????????? みたいなパターンだった。?の並びを[good][good]...じゃなくて[good]{num_of_question_marks}に変換してみた→AC
Submission #28862802 - Codeforces
そこまでするなら正規表現を使わずにマッチングを書いたほうが楽かも…

A. Sasha and Sticks (x5243)

http://codeforces.com/contest/832/problem/A
(long longに入れて)割って、商が奇数か偶数か。O(1)。
→AC
Submission #28847698 - Codeforces

D. Misha, Grisha and Underground (x678)

http://codeforces.com/contest/832/problem/D
結構みんな解いてるみたいだし(DのほうがCより沢山解かれてて、こっちが実質Cだった…)
(他人の様子を伺うのも忘れ長考に入っていて気づかなかった…)
開いてみた

各都市間の相互距離が時間内に用意できれば簡単そうだけど
そんな時間もないよね
(成果なし)

E. Vasya and Shifts (x43)

http://codeforces.com/contest/832/problem/E
開いてない