名もなき未知

エンジニアリングとか、日常とかそういうのをまとめる場所。アクセス解析のためGAを利用、Googleに情報を送信しています。商品紹介のためAmazonアフィリエイトを利用、Amazonに情報を送信しています。記事に関しては私が書いていない引用文を除いて自由にご利用ください。

Codeforces Round #504に参加した(A, B問題のみ)

本番はC問題まで取り組んで、A,Bはプレテスト通った感じ。Aは撃墜パターンがあったので、多分そこでかなりの人が落ちた(B問題の正解者数より少ない時点でお察し) A通せててたらレーティングは維持できてたかもなーくらい。

A問題

https://codeforces.com/contest/1023/problem/A

* が0文字以上の文字列に変更可能であり、* が入っている文字列Sと入っていない文字列Tが一致するかどうかを答える問題。

制約として * が1個までしか入ってこないことを見落としており、え、これ正規表現とか深さ優先とかしないといかんやつか? と勘違いし、正規表現でやったら落とされた。

例えば、正規表現はこういうケースに弱い。

20000 200000 *aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa

で、自分で実装をしてやる必要がある。例えばこんな感じ。

  • * が入っているかどうかで分岐
    • 入っていなければ普通の文字列一致で調べる
  • 以下入っている場合
    • * の位置aiを探す。sのそれまでの文字列はtのそれまでの文字列と一致するはずなので、比較してだめならNO
    • aiが n - 1 の位置なら、問答無用でYES
    • それ以外の場合、sのai以降の文字列でtの以降の文字列を右から探す(rfind)
    • 発見できた位置を見て、文字列一致の結果を見る

うーん、これAにしては分岐が最初から多すぎないですかね。つらい。

https://codeforces.com/contest/1023/submission/41737372

#!/usr/bin/env python
# -*- coding: utf-8 -*-


def solve():
    n, m = map(int, input().split())
    s, t = input(), input()
    if s.find("*") >= 0:
        ai = s.find("*")
        if t.find(s[:ai]) != 0:
            print("NO")
            return
        if ai == n - 1:
            print("YES")
        else:
            t2 = t[ai:]
            ri = t2.rfind(s[ai + 1:])
            print("YES" if t2[max(0, ri):] == s[ai + 1:] else "NO")
    else:
        print("YES" if s == t else "NO")


if __name__ == "__main__":
    solve()

B問題

https://codeforces.com/contest/1023/problem/B

組み合わせはなんとなく n = k + 1 あたりで最大になりそうだなあというのを見て、それっぽく組む。 ちなみに私は (n, k)=(8, 1-17) (n, k)=(9, 1-19) の2パターンで見てOKそうだなと思って出した。正直こっちの問題のほうが落とし穴少なくて簡単だと思う。。

https://codeforces.com/contest/1023/submission/41714613

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import math


def solve():
    n, k = map(int, input().split())
    h = k / 2
    if n < k:
        ans = n - math.floor(h)
    elif k <= n:
        ans = math.ceil(h) - 1
    ans = max(0, ans)
    print(ans)


if __name__ == "__main__":
    solve()

C問題以降

Cはカッコの対応を見る問題だけど、どうも誤訳からの誤解があるようで、よくわからなかった。D以降は見てない。復習するならC, Dまでにしておこうかな。

まとめ

正規表現の弱いパターンを考慮できなかったなという発見があったので、それはプラスだった。あとB問題はすばやくシミュレーションできたので良かったと思う。 問題はA考慮点多いな、B覗こうをさっさとやらなかったのが良くなかったかも。全体的に問題飛ばして行けそうなものから行こうという思考が足りてないかもなあ。

なおこのあとのエデュフォでHACKされて0完扱いになっていて、そっちのほうが痛いのだが。コドフォはあまり力を入れる気がないので、今はゆっくり問題形式とか英文に慣れていければと思う。

追記

C解いた。前から見ていい感じにカッコを補完するだけでよかったらしい。

https://codeforces.com/contest/1023/submission/41907986

この人の解説が役に立った。ありがとう。(まじでそれやるだけなのかー… ってなって本番組めなかった自分が恥ずかしい)

https://cpeditorials.blogspot.com/2018/08/codeforces-round-504-c-bracket.html