ARC 101 の感想

1完だった。2問目D問題の700点は手も足も出ずだったけど、なんか典型的なアルゴリズムが組み合わさった問題らしいので後で解く。

C - Candles

N本のろうそくを連続するK個ずつ見て、どの区間が最短かを見る。

K個見る際は、符号の反転に要注意。マイナスからプラスに変わる場合と、プラスからマイナスに変わる場合があるが、プラス、マイナスの一番絶対値の大きい値から折り返してもう1つの符号を見るような形になる。

実装自体は割と早く思いつくものの、無限にバグらせてしまい、90分位かかってしまったので、流石に自分で組んでいて呆れた。(最初のSubmit時点で上がらないことがわかりきっていたので、コンテスト座ったままのほうがレート的には優しかったが、まあ、そんな事を言っていると一生コンテストから逃げるので最後までやることにした)

ちなみに条件式をもう少し簡潔に書けるとのことなので、下記の方法は微妙（あと似たようなループをもう一つ書いていてその名残で i < 0 などという変な条件が入っていたりするので、通るけど真似はしないほうがいいという話。その時書いていたコードをそのまま残したいので、そのまま貼る）。ちなみに私は0が入ったときはカウントを減らすような処理にし、リストから削除している。

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

import bisect


def solve():
    n, k = map(int, input().split())
    al = [int(i) for i in input().split()]

    ans = sum(abs(i) for i in al)
    flag0 = 0 in al
    if flag0:
        k -= 1
        n -= 1
        if k == 0:
            print(0)
            return
        al.remove(0)
    nc = bisect.bisect_left(al, 0)
    for i in range(n):
        if i < 0 or i + k - 1 >= n:
            break
        if al[i] < 0 and al[i + k - 1] < 0:
            t1 = abs(al[i])
        else:
            t1 = min(abs(al[i]) * 2 + abs(al[i + k - 1]),
                        abs(al[i]) + abs(al[i + k - 1]) * 2)
        if al[i] > 0 and al[i + k - 1] > 0:
            t2 = abs(al[i + k - 1])
        else:
            t2 = min(abs(al[i]) * 2 + abs(al[i + k - 1]),
                        abs(al[i]) + abs(al[i + k - 1]) * 2)
        t = min(t1, t2)
        ans = min(ans, t)
    print(ans)


if __name__ == "__main__":
    solve()

併設 ABC 107の問題とか

A - Train

単純に (n - i + 1) を出すだけ。

B - Grid Compression

いろいろやり方はあると思うけど、消せるラインかどうか見て、消せるラインなら入力テーブルと同じ大きさのフラグだけ持つテーブルのフラグをいじる。フラグがTrueのものだけ出力するようにする感じ。

結局見ていくと、縦横の . のカウントを見て、縦横の長さと一致していたら出力しないという形にできるので、それで良いんじゃなかろうか。

珍しくC++を書いた。（そろそろC++を書けみたいな圧が多くて辛い）

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout.precision(16);

    int h, w;
    cin >> h >> w;

    string table[h];
    vector<int> wv(w);
    vector<int> hv(h);
    for (int i = 0; i < h; i++) {
    cin >> table[i];
    for (int j = 0; j < w; j++) {
        wv[j] += table[i][j] == '.' ? 1 : 0;
        hv[i] += table[i][j] == '.' ? 1 : 0;
    }
    }

    for (int i = 0; i < h; i++) {
    string s = "";
    for (int j = 0; j < w; j++) {
        if (hv[i] != w && wv[j] != h) {
        s += table[i][j];
        }
    }
    if (!s.empty()) {
        cout << s << endl;
    }
    }

    return 0;
}

感想

今の自分の実力だと、300点問題は20分以内には解けていないと多分だめなレベルで、考察、コーディング速度の両面を鍛えないといけないなという気持ちになった。

あとB問題もC問題も最初考えて通したロジックをよく見ると、かなり余計なコードやロジック、処理が入っていてそれを簡潔な形で書けた、となったのは見返していてよかったなと思える点だが、やっぱりそれもコンテスト中に出来ないと険しいな、という気持ちになった。

D問題はある程度C++書けるようになってから戻ってきて解いたほうが良さそう。今は放置。(自分の直感とC++の実装は結構ずれているような感じがして、コンパイル代わりと通らなくて辛い見たいな気持ちになりがちで、業務で使うわけでもないC++を書くモチベーションがなかなか上がらない。Rustを学びながら書くのはありだけど、まだRustで競技プログラミングするほど知識がないので、多分、無理)