2025-09-21

【AtCoder】AtCoder Beginner Contest 424 - 参加記 | 緑コーダーが解くAtCoder

atcoder.jp

コンテスト時間: 2025-09-20(土) 21:00 ~ 2025-09-20(土) 22:40 (100分)

A - Isosceles

Difficulty: ??? / NoviSteps: ???

解答時間: 1:13

面積が正である三角形 ABC があり、三辺の長さはそれぞれ $a,b,c$ である。三角形 ABC が二等辺三角形であるか判定せよ。

$a = b = c$ なら正三角形なので Yes 。
そうではなく、 $a = b$ または $b = c$ または $c = a$ なら Yes 。そうでなければ No 。

B - Perfect

Difficulty: ??? / NoviSteps: ???

解答時間: 3:24

人が問からなるプログラミングコンテストに参加した。このコンテストでは個のイベントが順番に起き、番目のイベントは以下の通り。
- 人 $A_i$ が問題 $B_i$ に正解した。
すべての問題に正解した人の番号を全員出力せよ。そのような人が複数いる場合は、すべての問題に正解したタイミングが早い順に出力せよ。

各参加者がどの問題を解いたかをシミュレーションしていき、イベントが起きるごとにその人が全問正解しているかをチェックすればよい。

C - New Skill Acquired

Difficulty: ??? / NoviSteps: ???

解答時間: 12:13

$1$ から $N$ の番号がついた $N$ 個のスキルがある。 $N$ 個の整数の組 $(A_1,B_1), \dots,(A_N,B_N)$ が与えられ、 $(A_i,B_i)=(0,0)$ のときスキル $i$ を習得済みである。そうでないとき、スキル $A_i,B_i$ の少なくとも一方を習得済みのときに限りスキル $i$ を習得することができる。既に取得済みのスキルも含め、最終的に習得することができるスキルの個数を求めよ。

スキル習得のための依存関係は有向グラフで表すことができる。
すでに習得済みのスキルを始点として、このグラフに対して BFS / DFS を行えばよい。

D - 2x2 Erasing 2

Difficulty: ??? / NoviSteps: ???

解答時間:25:30

$H \times W$ のマス目があり、各マスは白または黒に塗られている。高橋君は $0$ 個以上の黒く塗られたマスを白に塗り替えることで、マス目が黒く塗られたマスのみからなる $2\times 2$ の部分を持たないようにしたい。高橋君が目標を達成するために、白く塗り替える必要のあるマスの個数の最小値を求めよ。 $T$ 個のテストケースが与えられるので、それぞれについて答えを求めよ。

$H, W$ の制約が非常に小さく、頑張れば全探索できそうな気もする。
「各マスを黒に塗るか白にするか順番に決めていく」という愚直な方法では $2^{HW}$ の場合があり、そのままでは TLE してしまう。
しかし、以下のような枝刈りができるので実際の探索量はそれほどでもなさそう。
- 元々白のマスを黒にすることはできない。
- 探索途中に暫定最小コストよりもコストが大きくなったら探索を打ち切る
- 黒に塗ると決め打ったときに、 $2 \times 2$ の領域ができたら探索を打ち切る
これを基に、左上のマスから色を決めていくという再帰全探索(DFS)を行うことができる。

実は答えの最大値が $9$ なので、この枝刈りが間に合いそうだということも考えることができる。

#ABC424 お疲れさまでした～
遅めの4完で微冷え

C: 有向グラフを作って、修得済みのスキルから多始点BFSをする。
D: DP苦手なので、全探索DFSを全力で枝狩りする。↓のような最大ケースでも9マス塗り替えればよい（未証明）ので、塗り替え回数が9になったら打ち切るのが強力。 pic.twitter.com/fkEwqi8uAe
— kurig (@kurig15) 2025年9月20日

結果

Performance: 1275

1167 → 1178 (+11) Highest更新！

atcoder.jp

前回の負けを取り返せた。

2025-09-16

【AtCoder】AtCoder Beginner Contest 423 - 参加記 | 緑コーダーが解くAtCoder

AtCoder-ABC-コンテストまとめ AtCoder-ABC AtCoder ABC コンテストまとめ競技プログラミング

atcoder.jp

コンテスト時間: 2025-09-14(日) 21:00 ~ 2025-09-14(日) 22:40 (100分)

A - Scary Fee

Difficulty: ??? / NoviSteps: ???

解答時間: 4:16

ある銀行の通帳からお金を引き出すには、 $1000$ 円単位で引き出し額を指定したうえで、引き出し額 $1000$ 円あたり $C$ 円の手数料を残高から別途支払う必要がある。残高が $0$ 円未満になる引き出しを行うことはできない。通帳の残高が $X$ 円のとき、最大で何円を引き出せるか求めよ。

求める条件は、を整数として以下のように書ける。
- $1000m + Cm \leq X \iff m \leq \frac{X}{1000 + m}$
これを満たす $m$ の最大値は $\left\lfloor \frac{X}{1000 + m} \right\rfloor$ だから、これを $1000$ 倍したものを答えとすればよい。

B - Locked Rooms

Difficulty: ??? / NoviSteps: ???

解答時間: 3:16

$N + 1$ 個の部屋が一列に並んでおり、部屋の間には $N$ 個のドアがあり、ドア $i$ は部屋 $i - 1$ と部屋 $i$ の間にある。各ドアについて鍵の状態を表す値 $L_i$ が与えられ、 $L_i = 0$ のときドア $i$ の鍵は開いており、 $L_i = 1$ のとき閉まっている。2人の人がおり、1人は部屋 $0$ に、もう1人は部屋 $N$ にいる。それぞれの人は、ドア $i$ の鍵が開いているときに限り、部屋 $i - 1$ と部屋 $i$ の間を移動することができる。このとき、2人のいずれも到達できない部屋の個数を求めよ。

両端からの2人の動きをシミュレートし、到達できた部屋のインデックスを求める。
その後、両者の差から答えを求めればよい。

C - Lock All Doors

Difficulty: ??? / NoviSteps: ???

解答時間: 20:52

$N + 1$ 個の部屋が一列に並んでおり、部屋の間には $N$ 個のドアがあり、ドア $i$ は部屋 $i - 1$ と部屋 $i$ の間にある。各ドアについて鍵の状態を表す値 $L_i$ が与えられ、 $L_i = 0$ のときドア $i$ の鍵は開いており、 $L_i = 1$ のとき閉まっている。高橋君ははじめ部屋 $R$ におり、ドア $i$ の鍵が開いているときに限り部屋 $i - 1$ と部屋 $i$ の間を移動でき、部屋 $i - 1$ または部屋 $i$ にいるときに限りドア $i$ の鍵に対して開閉操作を行うことができる。すべてのドアの鍵が閉まった状態にするために行う鍵の開閉操作の回数として考えられる最小値を求めよ。

鍵が閉まっているドアの中で、インデックスが最小のものを $l$ 、最大のものを $r$ とする。
すると、高橋君が訪れるべき部屋の範囲は $[m_l, m_r ] = [ \min(l, r, R), \max(l, r, R) ]$ と求められる。
この範囲において、 $L_i = 1$ となる $i$ の個数を $c$ とすれば、 $m_r - m_l + c$ が答えとなる。

D - Long Waiting

Difficulty: ??? / NoviSteps: ???

解答時間: 32:29

同時に最大人の客を入れられるレストラン店があり、1つの待ち行列を管理している。時刻の時点で店内に客はおらず、待ち行列も空である。今日は個の団体客が来る予定であり、団体客の人数は人で、時刻に待ち行列の末尾に加わる。また、この団体客は入店してから単位時間後に退店する。それぞれの団体客は、以下の2条件が同時に満たされた最も早い時刻に、待ち行列を離れて入店する。
- その団体客は、待ち行列の先頭にいる。
- その団体客と、店内にいるすべての団体客の人数を合算すると、 $K$ 人以下になる。
それぞれの団体客が入店する時刻を求めよ。

団体客の「列に並ぶ」と「退店」をイベントとして扱い、priority_queueを用いながらイベントソートの要領でシミュレーションしていけばよい。
自作構造体をpriority_queueに突っ込む際は、比較関数を自分で定義する必要があるので注意(1敗)。

結果

Performance: 1072

1177 → 1167 (-10)

atcoder.jp

D問題の実装を手間取り過ぎた。

2025-09-07

【AtCoder】AtCoder Beginner Contest 422 - 参加記 | 緑コーダーが解くAtCoder

AtCoder-ABC-コンテストまとめ AtCoder-ABC AtCoder ABC コンテストまとめ競技プログラミング

atcoder.jp

コンテスト時間: 2025-09-07(日) 13:10 ~ 2025-09-07(日) 14:50 (100分)

A - Stage Clear

Difficulty: ??? / NoviSteps: ???

解答時間: 2:51

あるゲームにはワールドがつあり、それぞれのワールドにはステージがつずつある。最初のステージは個目のワールドにある個目のステージであり、個目のワールドにある個目のステージの次のステージは、以下のように定まる。
- $j\lt8$ のとき、次のステージは $i$ 個目のワールドにある $j+1$ 個目のステージである。
- $i\lt8,j=8$ のとき、次のステージは $i+1$ 個目のワールドにある $1$ 個目のステージである。
- $i=8,j=8$ のとき、次のステージはない。
- $i$ 個目のワールドにある $j$ 個目のステージの名前は $i$ - $j$ である。高橋くんが現在遊んでいるステージのステージ名 $S$ が与えられるので、次のステージのステージ名を出力せよ。

ステージ名の規則はマリオと同じ。
$i = S_1, \, j = S_3$ として、あとは規則通りに計算していくだけ。

B - Looped Rope

Difficulty: ??? / NoviSteps: ???

解答時間: 3:16

のマス目があり、それぞれのマスは白もしくは黒のどちらかで塗られている。マス目が以下の条件を満たすか判定せよ。
- どの黒で塗られたマスについても、上下左右で隣り合うマスのうち黒く塗られているものは $2$ つもしくは $4$ つである。

制約が小さいので、素直に全探索すれば十分。

ライフゲームの実装で無限にこれをやっているから、もはや呼吸するように書けてしまう()

C - AtCoder AAC Contest

Difficulty: ??? / NoviSteps: ???

解答時間: 7:30

高橋くんは、はじめAを $n_A$ 個、Bを [tex; n_B] 個、Cを $n_C$ 個持っている。高橋くんは、Aを1つ、Cを1つ、さらに任意の1つの文字を使うことで、コンテストを1つ開催することができる。高橋くんは、現在持っている文字を使ってコンテストをなるべく多く開催したい。開催できるコンテストの最大値を求めよ。 $T$ 個のテストケースが与えられるので、それぞれについて答えよ。

開催できるコンテスト回数を $t$ 回とする。
まず、コンテストを開催するごとにA, Cを1個ずつ消費しなければならないので、 $t \leq \min(A, C)$ が必要。
さらに、コンテストを1つ開催するには文字が3つ必要なので、 $t \leq \left\lfloor \frac{n_A + n_B + n_C}{3} \right\rfloor$ も必要。
これらをまとめると、 $t \leq \min(\min(A, C), \left\lfloor \frac{n_A + n_B + n_C}{3} \right\rfloor)$ となる。この $t$ の最大値が答え。

D - Least Unbalanced

Difficulty: ??? / NoviSteps: ???

を正整数として、長さの非負整数列のアンバランスさを次の操作によって得られる非負整数値として定義する :
- はじめ、 $X=0$ とする。
- 次の一連の操作を回行う。
  - $X \leftarrow \max(X, \max(A) - \min(A))$ とする。
  - $A \gets (A_1 + A_2, A_3 + A_4, \dots, A_{\vert A \vert - 1} + A_{\vert A \vert})$ とする。
- 最終的な $X$ をアンバランスさとする。
非負整数 $K$ が与えられるので、長さ $2^N$ の非負整数列であって総和が $K$ であるものの中で、アンバランスさが最小値を取る数列を構成せよ。

操作を行うごとに、数列は長さ $2^{N-1}$ の2つの数列に分割される。
前後の総和をなるべく均等にしたいので、総和を前の数列は $\left\lfloor \frac{K}{2} \right\rfloor$ 、後ろの数列はその残りで考える。
これを再帰的に長さ $1$ になるまで繰り返せば、あとは順次当てはめていくだけ。
...ここまで考察できたは良いものの、時間が足りなくてACできず。悔しい。

ぱっと見で再帰解法を思いつかなくてE, F問題へ行ってしまい、そこで時間を食った形に。

E - Colinear

Difficulty: ??? / NoviSteps: ???

解答時間: 35:00 + WA x2

2次元平面上に $N$ 個(奇数)の点があり、 $i$ 番目の点は $(x_i, y_i)$ にあって、全ての点の座標は相異なる。 $N$ 個の点のうち過半数を通る直線が存在するかを判定して、存在すればそれを出力せよ。

求めるべき直線 $l$ が存在すると仮定するならば、 $N$ 個の点からランダムに選択した点がこの $L$ 上に存在する確率は $\frac{\frac{N+1}{2}}{N}$ 以上であり、これは $\frac{1}{2}$ を超える。
ある2点を通る直線は一意に定まるので、 $N$ 個の点からランダムに選択した2点を通る直線が題意を満たす確率は $\frac{1}{4}$ である。
ランダム選択を $100$ 回程度繰り返せば、誤答を返す確率は $\left( \frac{3}{4} \right)^{100} \approx 3.20 \times 10^{-13}$ となり、ほぼ確実にACできる。

while文を用いて実装してたら、イテレーションを回すのを忘れて無限ループに陥っており2ペナ。

結果

Performance: 1368

1154 → 1177 (+23) Highest更新！

atcoder.jp

異例の日曜日のお昼開催となったABC。参加者が少ないと Performance が上に引っ張られて良いね。

D問題解ければ入水だったのになー

2025-09-06

【AtCoder】ABC 420 C - Sum of Min Query | 緑コーダーが解くAtCoder

AtCoder-ABC-ABC_C問題 AtCoder-ABC-ABC_300点問題 AtCoder-NoviSteps-NoviSteps_4Q AtCoder-ABC AtCoder-AtCoder_灰Diff AtCoder-NoviSteps AtCoder-クエリ処理問題 AtCoder ABC ABC_C問題 ABC_300点問題 AtCoder_灰Diff NoviSteps_4Q クエリ処理問題競技プログラミング C++

atcoder.jp

配点: 300 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 169 / NoviSteps: 4Q

問題概要
制約
考察
実装例
コメント

問題概要

長さ $N$ の整数列 $A, B$ が与えられる。 $Q$ 個のクエリが与えられるので順に処理せよ。 $i$ 番目のクエリは以下のようになる。

文字 $c_i$ と整数 $X_i,V_i$ が与えられる。 $c_i=$ Aならば $A_{X_i}$ を、 $c_i=$ Bならば $B_{X_i}$ を $V_i$ に変更する。その後、 $\displaystyle \sum_{k=1}^N \min(A_k,B_k)$ を出力する。

制約

$1\le N,Q \le 2 \times 10^5$
$1\le A_i,B_i \le 10^9$
$1\le V_i \le 10^9$
入力される数値は全て整数

考察

クエリを処理するごとに sum を計算していては TLE になってしまう。

しかし、クエリごとに $A, B$ いずれか一か所の要素しか変更されないことに注目すると、 sum の差分を計算してその都度更新していくことができる。

実装例

#include <bits/stdc++.h>
using namespace std;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

using ll = long long;

// ======================================== //

int main()
{
    int N, Q;
    cin >> N >> Q;
    vector<int> A(N), B(N);
    rep(i, 0, N) cin >> A[i];
    rep(i, 0, N) cin >> B[i];

    ll sum = 0;
    rep(i, 0, N) sum += min(A[i], B[i]);

    while (Q--)
    {
        char c;
        int X, V;
        cin >> c >> X >> V;
        X--;

        sum -= min(A[X], B[X]);

        if (c == 'A')
            A[X] = V;
        else
            B[X] = V;

        sum += min(A[X], B[X]);

        cout << sum << endl;
    }

    return 0;
}

atcoder.jp

実装時間: 5分

C問題久しぶりの4Q難易度。良心的だ。

2025-09-05

【AtCoder】ABC 420 A - What month is it? | 緑コーダーが解くAtCoder

AtCoder-ABC-ABC_A問題 AtCoder-ABC-ABC_100点問題 AtCoder-NoviSteps-NoviSteps_8Q AtCoder-計算問題-簡単な計算問題 AtCoder-ABC AtCoder-AtCoder_灰Diff AtCoder-NoviSteps AtCoder-計算問題 AtCoder ABC ABC_A問題 ABC_100点問題 AtCoder_灰Diff NoviSteps_8Q 計算問題簡単な計算問題競技プログラミング C++

atcoder.jp

配点: 100 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 10 / NoviSteps: 8Q

問題概要
制約
考察
実装例
コメント

問題概要

$1$ 以上 $12$ 以下の整数 $X,Y$ が与えられるので、 $X$ 月の $Y$ ヶ月後が何月か求めよ。

制約

問題文の通り

考察

$X$ に $Y$ を加えて、それを $12$ で割った余りを求めればよい。

...のだが、これだとサンプルケース3の $X = Y = 12$ のような場合に答えが $0$ となってしまうので、うまいこと $1$ から $12$ の範囲で出力できるように調整しなければならない。

今回は $(X - 1 + Y) \mod 12 + 1$ とすればよい。

実装例

#include <bits/stdc++.h>
using namespace std;

// ======================================== //

int main()
{
    int X, Y;
    cin >> X >> Y;

    cout << (X - 1 + Y) % 12 + 1 << endl;

    return 0;
}

atcoder.jp

実装時間: 5分以内

一般に、 $N \mod M$ を区間 $[1, M]$ に clamp するためには、 $(N-1) \mod M + 1$ とすればよい。これは地味に便利なので覚えておいてもいいかも。

Yuulis.log

トンネルを抜けるとそこは参照エラーであった。

【AtCoder】AtCoder Beginner Contest 424 - 参加記 | 緑コーダーが解くAtCoder

A - Isosceles

B - Perfect

C - New Skill Acquired

D - 2x2 Erasing 2

結果

【AtCoder】AtCoder Beginner Contest 423 - 参加記 | 緑コーダーが解くAtCoder

A - Scary Fee

B - Locked Rooms

C - Lock All Doors

D - Long Waiting

結果

【AtCoder】AtCoder Beginner Contest 422 - 参加記 | 緑コーダーが解くAtCoder

A - Stage Clear

B - Looped Rope

C - AtCoder AAC Contest

D - Least Unbalanced

E - Colinear

結果

【AtCoder】ABC 420 C - Sum of Min Query | 緑コーダーが解くAtCoder

問題概要

制約

考察

実装例

コメント

【AtCoder】ABC 420 A - What month is it? | 緑コーダーが解くAtCoder

問題概要

制約

考察

実装例

コメント