アラフォー駆け出しエンジニア’s blog

駆け出しエンジニアのメモです

参加記 - AtCoder Beginner Contest 269

AtCoder Beginner Contest 269 に参加しました。E問題まで解くことができました。

A,B

やるだけです。

C

集合の部分集合を列挙するやつを使用しました。

for (ll j = x; j; j = (j - 1) & x)

D

UnionFind でやるだけという印象でした。

E

縦、横を別々に二分探索しました。 片方のコードをコピペしたのですが、愚かなコピペ修正ミスをして2WAしました。

F

解けませんでした。

市松模様の奇数行と偶数行を分けて、以下のように等差数列で解くことを考えました。

区間内の横方向の数 wc, 縦方向の数 hc とし、先頭行の非ゼロの値の和を \Sigma A とします。
縦方向の公差は 2M なので縦方向に等差数列をとることを考え、等差数列の公式から全体の合計は  hc*\Sigma A + wc(hc*(hc-1)*M) で求められる

落ち着けば解ける問題だったように思いますが、上手く実装できませんでした。

AtCoder で水色になるために行った勉強方法

先日 AtCoder で水色になったので、私の勉強方法を紹介します。

主に以下の3つをやっていました。

  • 典型問題対策
  • 早解き練習
  • 実践練習

順に紹介していきます。

過去問で典型問題対策

ABC(AtCoder Beginner Contest) に出題される問題はいわゆる典型問題が多く、過去問に類題があることが多いです。 なので過去問を繰り返し解くことで、典型問題の考察をできるように練習しました。

具体的には、
AtCoder Problems の API を使って、6 問体制になった以降の ABC から difficulty 800 〜 1400 の問題を集め、次のような方針で練習していました。 なお、私が参加するのは ABC だけなので、集める問題は ABC からだけにしました。

  1. 問題を5分くらい考える
  2. 時間がたったら、解けても解けなくても解説を見る

これを繰り返し行います。 解けなかった問題や解くのに時間がかかった問題は2周目以降もやり、解けてもう見なくても良い問題はリストから除きます。

この練習は典型問題の考察をできるようになることが目的なので、実装に不安がある場合だけコードを書いていました。

早解き練習

早解きの練習として、ABC からランダムにAからE問題まで選び、45分以内で解くバチャをしていました。
E問題は時間内に解けないこともありますが、その場合はすぐに解説を見て解説ACをしていました。

実践練習

ABC の本番や codeforces Div.3 に参加します。 バチャの「まよコン」も良いかもしれません。

水色になれるまでは全部実践練習と考え、レーティングが下がっても気にしないことが大事です。

おわりに

練習では1問ごとにかける時間を少なく、その代わりに同じ問題でも繰り返しやる方針で、上記のような勉強方法を採用していました。
「問題を解くこと」を楽しんでる方には向かない練習ですが、てっとり早く水色になりたい方には参考になるかもしれません。

参加記 - Codeforces Round #820 (Div. 3)

Dashboard - Codeforces Round #820 (Div. 3) - Codeforces

Codeforces Round #820 (Div. 3) に参加しました。D問題まで解くことができました。

A, B

やるだけです。

C. Jumping on Tiles

DPかと勘違いして時間をロスしてしまいました。サンプルをちゃんとみるべきでした。

s[0] <= s[-1] として、 s[0] <= c[i] <=s[-1] のindexは全部取れば良いでした。

D. Friends and the Restaurant

z[i]=y[i]-x[i] とします。 z[i]>=0 のものを昇順にし、 z[i]+z[j]>=0 にできる最大のzの j をみつけ、{i, j} でペアを作ります。 その後、ペアを作れなかった z[i]>=0 の要素同士でペアを作ります。 ペア数の合計が答えです。

E

解けませんでした。 4点あれば解が求まりそうと思い試してましたが、WAでした。

test 15 まで行っているのである程度方針は正しいと思うのですが。。。

参加記 - AtCoder Beginner Contest 268

UNIQUE VISION Programming Contest 2022 Summer (AtCoder Beginner Contest 268) - AtCoder

AtCoder Beginner Contest 268 に参加しました。D問題まで解くことができました。

A,B

やるだけです。

C - Chinese Restaurant

理i からみて、あと何回動かせば喜びを得られるかを考えました。

(p[i] - i-1) % n 回からそれ +2 回まで動かすときに喜びが得られます。これにより動かす回数ごとの得られる喜びの合計が求められるので max をとりました。

「逆からみる」という典型パターンですね。

D - Unique Username

N が小さいのでnext_permutation でSをつなげる順を全探索しました。

S' の作成は DFS をしました。このとき念の為、 _ が足りない場合などは枝刈りしましたが、本当に必要だったかわかっていません。

E - Chinese Restaurant (Three-Star Version)

わかりませんでした。

左右に一つ動かすとコストが +1 されるものと -1 されるものがあるので、この合計が最小となる移動を求めたいと考えました。 整数の問題ですが、凸関数のような形を期待し三分探索を考えましたが、よくわかりませんでした。

F - Best Concatenation

コンテスト終了後に解きました。

前方に X が C 個ある場合に、S_i と S_j のどちらを先に置いたほうがスコアが高いかを考えると、

  • S_i の X の個数 * S_j の 数合計

の降順でソートすれば良いことがわかりました。

少し前に X - Tower を解いていたから、その経験が生きたかもしれません。

おわりに

E問題よりF問題が簡単に思えました。 残り30分くらいでE問題は諦めてF問題に取り掛かるべきだったと思います。 また、順位表からEよりFのほうが解かれていることがわかるので、解けない時には順位表を確認することも大事だと思いました。

参加記 - Educational Codeforces Round 135 (Rated for Div. 2)

Dashboard - Educational Codeforces Round 135 (Rated for Div. 2) - Codeforces

Educational Codeforces Round 135 (Rated for Div. 2) に参加しました。 コンテスト中にC問題まで解けました。D問題は解けましたが実装が間に合いませんでした。

A. Colored Balls: Revisited

英文が理解できず、何を求めたら良いのかよくわかりませんでしたが、「最後に残すことのできる最大の色番号」と考えて実装しました。

{個数の大きい, 色番号の小さい} 順に使っていくようにし、残った最後の色番号を答えとしました

B. Best Permutation

最終的な値を (n-1) + n となるようにします。

n が偶数の場合は、{2, 1, 4, 3, ..., n-1, n+1} とし、奇数の場合は {3, 2, 5, 3,..., n-1, n-3, 1, n-2, n} とし、最後の2、3要素の値が加算されるようにしました。

C. Digital Logarithm

priority_queue を使って大きい順に揃えていきます。
1つの要素に対するfの操作は高々2回なので O(NlogN) 程度になると考えました。

D. Letter Picking

時間内に解くことができませんでした。

区間DPをしました。
dp[i][j] := [i, j) の区間が取られたとき、{aliceの勝ち, 引き分け, bob の勝ち} のいずれになるか?をもたせました。 引き分けの時は取った端の値も保持するようにしました。

勘ですが、DPの遷移を考えると、残り偶数個から取る方が選択肢を多く持つため、そちらが勝つか引き分けることがほとんどに思います。
Bob が勝てる場合はありますか?

参加記 - AtCoder Beginner Contest 267

atcoder.jp

AtCoder Beginner Contest 267 に参加しました。 E問題まで解くことができました。

A. Saturday

やるだけです。

B. Split?

面倒ですがやるだけです。

倒れてないピンのある最小 index, 最大 index を求めて、

  • 最小 index <= index <= 最大 index

を満たすすべて倒れている列が存在するか。で判定しました。

C. Index × A(Continuous ver.)

難しかったです。最初全く解法が思いつきませんでした。

B_1 から B_M までの和と B_2 から B_{M+1} までの和を比較すると、累積和で解けることががわかります。

D. Index × A(Not Continuous ver.)

典型的なDPです。以下でDPしました。

DP[i][j]:= i番目の要素までで j 個選んだときの最大合計

簡単なDP問題に慣れてきたのか、C問題よりもこちらのほうが簡単に感じました。

E. Erasing Vertices 2

頂点を削除しても、その他の頂点のコストは広義単調減少するだけなので、小さいコストのものから削除して良さそうに思いました。 最初は貪欲で考えましたが、「操作全体のコスト」の最小値の求め方がわからないので、「すべての操作のコストを mid 以下で行えるか」という二分探索しました。 証明力が無く、これで解法あってるのか疑心暗鬼でした。

1度目のsubmitでは二分探索の中身をsetを使った遅いコードを書いてしまい TLE。WAがでてなかったことから方針は合ってると思い、queue を使ったコードに書き換えてACしました。

VL costs(n, 0);
rep(i, n) {
    for (auto v: g[i]) {
        costs[i] += a[v];
    }
}

auto fnc = [&](ll mid) {
    queue<int> que;
    VI used(n, 0);
    VL diff(n, 0);

    rep(i, n) {
        if (costs[i] <= mid) {
            que.push(i);
            used[i] = 1;
        }
    }
    while (!que.empty()) {
        int u = que.front();
        que.pop();
        for (auto v: g[u]) {
            if (used[v])continue;
            diff[v] += a[u];
            if (costs[v] - diff[v] <= mid) {
                que.push(v);
                used[v] = 1;
            }
        }
    }

    rep(i,n)if(!used[i])return false;
    return true;
};
ll l = -1, r = INF;
while (l + 1 < r) {
    ll mid = (l + r) / 2;
    if (fnc(mid)) r = mid; else l = mid;
}
print(r);

F問題

解けませんでした。クエリ先読みすることを考えましたが、親方向に行ったときの頂点の見つけ方がわかりませんでした。 終了5分前に、ダメ元で全方位木DP を貼りましたがTLEでした。

「木の直径」は全く頭に浮かばなかったので練習不足だと感じました。

参加記 - Codeforces Round #818 (Div. 2)

Dashboard - Codeforces Round #818 (Div. 2) - Codeforces

Codeforces Round #818 (Div. 2) に参加しました。 B問題まで解くことができました。

初めて Div. 2 に参加しましたが、とても難しく、ABCよりARC寄りといった印象でした。

A. Madoka and Strange Thoughts

 g=gcd(a,b) とすると  lcm(a,b)/gcd(a,b)=ab/g^2 より、g を固定した場合に  lcm(a,b)/gcd(a,b) \leq 3 となる (a,b) のペアを考えます。

  • 1 になるケース: (g, g) の1通り
  • 2 になるケース: (2g, g), (g, 2g) の2通り
  • 2 になるケース: (3g, g), (g, 3g) の2通り

あとは各 a, b <= n となるような g の個数から解が求まります。

ans+=n;
ans+=n/2*2;
ans+=n/3*2;

B. Madoka and Strange Thoughts

まず r, c が指定されていない場合を考えると、

x..x..
.x..x.
..x..x

のように1行ずつ1つシフトすれば良いことがわかるので、(r, c) に X がくるようにずらして出力すれば良いです。