ABC244

コンテスト参加

atcoder.jp

初めてA、B、Cの3完できた。 C問題はインタラクティブ問題で焦った。

D問題

D問題は意味わからんと思って諦めたが解説見たら単純だった。

atcoder.jp

感想

AtCoder Problemsを最近やっていて問題傾向として、

• C問題は全探索で解決できる
• D問題は計算量を考慮してひねりが必要

みたいな問題パターンが見えてきた。

ABC243

コンテスト参加

atcoder.jp

とりあえずA問題、B問題の2完できた。C問題、D問題は壁が厚く終わったあとに解説見ながら取り組んだ。

C問題

1. Y座標が同じ
2. 人 p は右を、人 q は左を向いている
3. 人 p の x 座標が 人 q より小さい ときのみ衝突が起こる

さらに右を向いている人のうち最も左のx座標にいる人、左を向いている人のうち最も右のx座標にいる人のみ見ればよい。

1.、2.の条件は気づけたが、3.の条件で

R (2, 1)、L (1, 1)
のようなY座標が同じかつRLだが衝突しないケースを考慮できていなかった・・・。

D問題

解説を見て二分木の性質を思い出して実装したがTLEになり解けない。

list[-1] でリストの最後から数えた要素を取得できることを知った

これだとTLEになる

    for i in range(N):
        if S[i] == "U" and len(T) > 0 and (S[i - 1] == "L" or S[i - 1] == "R"):
            T.pop()
        else:
            T.append(S[i])

こっちだとOK

    for i in range(N):
        if S[i] == "U" and len(T) > 0 and (T[-1] == "L" or T[-1] == "R"):
            T.pop()
        else:
            T.append(S[i])

今の心境

ABC241

atcoder.jp

コンテスト未参加
A問題、B問題はなんとか解けた

C問題は右斜めの判定方法がわからなくて詰んだ

dxとdyを使えば、縦、横、斜めを簡単に走査できることを学んだ

    Dx = [1, 0, 1, 1]
    Dy = [0, 1, 1, -1]
    for x in range(N):
        for y in range(N):
            for dx, dy in zip(Dx, Dy):

D問題は他の人の回答を見たが未だによくわからない

Multisetというものを使えば簡単に解けるらしいがPythonにはない github.com