ながめも

競技プログラミングについて

2020年を振り返る

月ごとの要約

  • 1月: 就活をしていた。
  • 2月: 就活をしていた。
  • 3月: 落ちる
  • 4月: 内定を得る
  • 5月: 2社受かる
  • 6月: 進路決め(就活終了)
  • 7月: 中間発表
  • 8月:
  • 9月:
  • 10月:
  • 11月: HTTFで健闘する、ハル研プロコンで2週間溶かす。マラソン沼にハマる
  • 12月: 修論がやばくて、やばい

その他

  • 8月〜10月の記憶がほどんどない、何をしていたんだろう
  • 髪の毛を3月くらいから切っていなくて、大変なことに

感想

就活は大変でした。3月くらいから某ロナで面接がオンラインに移行して、戸惑いもありました。最終面接がオンラインだと、家なのにスーツを着て、重圧があり、変な感覚になります。内定が決まったときは泣きました。

競プロ的には、AtCoderでレートを200くらい上げたこと、マラソン形式に楽しく取り組めたことに満足しています。

ラソンは楽しいです。普段アルゴでは絶対に戦えないようなレベルの人たちと同じページの順位表に乗れる可能性があるというだけでワクワクしますし、評価関数を決めたり、計算量を操ったりするのも自由度が高く面白いです。問題が違っても、上位層の使っている手法が意外と共通であることに気づいてからは、自分の知ってる手法に落とし込むために問題の言い換えを考える時間も好きになりました。自明な貪欲を組んだあと、ビームを打ったら劇的に改善される瞬間は最高です。みんなもやろう、マラソンマッチ。人生とのバランスは考えた方がいい気はしますが。

来年度からは業務erになる予定ですが、マラソン、特にハル研プロコンのおかげで開発っぽいことに触れることができて、そういうコードの構造を読み解いたり、構成を考えるのも楽しいと思えたので、この気持ちを忘れずにやっていきたいと思います。

できるならマラソンっぽい案件をやってみたいという気持ちはあるのですが、まずはソフトウェアの開発の基本からという気持ちです。そもそもマラソンっぽい仕事、日本に少ないイメージで、あっても研究者レベルの人がやっていそうです。英語ができたら可能性がありますか?

あと某感染症のせいでリモートワークが増えたわけですが、自己管理能力がないことがよくわかったので入社後もかなり不安です。リモートワークしてる先輩社会人の皆さんはどのようにモチベーションを保って勤務しているのでしょう。

2020年はイレギュラーなこともありましたが、とりあえず生きて終えられそうなのでよかったです。競プロがなかったら就職先も異なっていたことでしょうし、在宅時間を耐えることもできなかったように思います。ありがとう競技プログラミング

最近AtCoderが調子が良いので分析してみた

2020/8/22以降のAtCoderにおけるパフォーマンスが上振れているので分析してみました。

最近緑diffがABC-Eに置かれることが多く、そこまでをある程度早く解いて甘い汁を吸っているか、同レート帯と比べて得意な数え上げを確実に仕留めているだけでした!

いかがでしたか?

Codeforces Round #679 (Div. 2, based on Technocup 2021 Elimination Round 1) C. Perform Easily

C. Perform Easily

問題へのリンク

弾きたい曲の楽譜とギターの弦における音の下限が与えられるので、ギターの抑えるべき幅の最小値を求めよという問題。

ある区間の中に全ての音を包含するようにできるかを考えればいいが、これは尺取りでできる。


int main() {
    vector<int> a(6);
    cin >> a;
    int N;
    cin >> N;
    vector<int> b(N);
    cin >> b;
    vector<pair<int,int>> v;
    rep(i,N)rep(j,6){
        v.emplace_back(b[i]-a[j], i);
    }
    sort(all(v));
    int val = 0;
    vector<int> cnt(N, 0);
    int ans = INF;
    int M = 6 * N;
    for(int l = 0, r = 0; l < M; l++){
        while(r < M && val < N){
            int ridx = v[r].second;
            if(cnt[ridx] == 0)val++;
            cnt[ridx]++;
            r++;
        }
        if(val == N)chmin(ans, v[r-1].first - v[l].first);
        cnt[v[l].second]--;
        if(cnt[v[l].second] == 0)val--;
    }
    cout << ans << endl;
}

AtCoder Regular Contest 106 ARC 106 参加記

A - 106

問題へのリンク

解説

オーバーフローしそうなのでpythonで。

実装

N = int(input())

for a in range(60):
    if a == 0:
        continue
    rem = N - pow(3, a)
    if rem < 0:
        break
    for b in range(60):
        if b == 0:
            continue
        if rem == pow(5, b):
            print(a, b)
            exit()
print(-1)

B - Values

問題へのリンク

解説

連結成分の和が同じなら達成できます。dfsとかunion findでも実装できます。ac-libraryのdsuはgroupsというのがあるらしいのでそれが一番楽そうです。

実装

vvec<int> G;
vector<ll> a, b;
vector<ll> used;
void dfs(int cur, int pre, vector<int>&v){
    used[cur] = true;
    v.push_back(cur);
    for(auto nxt: G[cur]){
        if(used[nxt])continue;
        dfs(nxt, cur, v);
    }
}
int main() {
    int N, M;
    cin >> N >> M;
    G.resize(N);
    a.resize(N);
    b.resize(N);
    used.resize(N, false);
    cin >> a >> b;
    rep(i,M){
        int c, d;
        cin >> c >> d;
        c--, d--;
        G[c].push_back(d);
        G[d].push_back(c);
    }
    rep(i,N){
        if(used[i])continue;
        vector<int> v;
        dfs(i, -1, v);
        dump(v);
        ll suma = 0;
        ll sumb = 0;
        for(auto x: v)suma += a[x];
        for(auto x: v)sumb += b[x];
        dump(suma, sumb);
        if(suma != sumb){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl;
}

C - Solutions

問題へのリンク

解説

まず、高橋君の方は区間スケジューリング問題の最適解なので、青木君が追い越すことはできません。よって M \lt 0はできません。また、 M = N or  M = N-1の場合もできません。 M = Nは、 (N, 0)の場合ですが、 0はあり得ないです。一個は取れます。また、 M = N-1は、 (N, 1) (N-1, 0)の場合ですが、前者は高橋君が全て取れるときは青木君も全て取れますし、後者は同様に 0はあり得ないことから、無理です。

以上の考察により、 0 \le M \le N-2の場合のみを考えればよいです。この場合、達成可能です。 まず、クソでか区間 (1, 1e9)を置くことで、青木君の結果を 1に固定します。このとき、高橋君の結果が M+1になればいいので、 M+1個の区間を取れるように置きます。ここで残った N - M - 2個の区間は、高橋君にも青木君にも取れないように置きます。具体的には以下のようにです。

f:id:coonevo:20201025162345j:plain

構築が完了しました。

実装

int main() {
    int N, M;
    cin >> N >> M;
    if(N == 1 && M == 0){
        cout << 1 << " " << 2 << endl;
        return 0;
    }
    if(M == N || M == N-1 || M < 0){
        cout << -1 << endl;
        return 0;
    }
    int rem = N - M - 1;
    for(int i = 1; i <= M+1; i++){
        cout << 2 * i+rem << " " << 2 * i+rem + 1 << endl;
    }
    for(int i = 1; i <= N-M-1; i++){
        cout << i << " " << INF - i << endl;
    }
}

AtCoder HHKB プログラミングコンテスト2020 参加記

ABCE青パフォでした。Dが難しかったですね・・・。

A - Keyboard

問題へのリンク

解説

if文。

実装

int main() {
    char s, t;
    cin >> s >> t;
    if(s == 'Y'){
        cout << char(t - 'a' + 'A') << endl;
    }
    else{
        cout << t << endl;
    }
}

B - Futon

問題へのリンク

解説

ある点から右と下を見ます。

実装

int main() {
    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    cin >> S;
    int ans = 0;
    auto IsIn = [&](int i,int j) -> bool{
        return 0 <= i && i < H && 0 <= j && j < W;
    };
    rep(i,H)rep(j,W){
        if(S[i][j] == '#')continue;
        rep(k,2){
            int nx = i + dx[k];
            int ny = j + dy[k];
            if(not IsIn(nx, ny))continue;
            if(S[nx][ny] == '#')continue;
            ans++;
        }
    }
    cout << ans << endl;
}

C - Neq Min

問題へのリンク

解説

pの値がintにおさまるので、ある値が出てきたかどうかのflagを持って全て回していいです。

実装

int main() {
    int N;
    cin >> N;
    vector<ll> p(N);
    vector<bool> used(200010, false);
    rep(i,N){
        cin >> p[i];
    }
    int idx = 0;
    rep(i,N){
        used[p[i]] = true;
        while(used[idx]){
            idx++;
        }
        cout << idx << endl;
    }
}

D - Squares

問題へのリンク

解説

これめちゃくちゃ難しいですね・・・。 公式の解説が丁寧なので追って実装しました。 特に、

  • 正方形の重なりを区間の重なりに言い換える
  • xとyが対称なので独立に考えてよく、また値が同じなので結果も同じ値になる
  • 最初に余事象とった後にもう一回余事象を取る

あたりがすごく難しいと思いました。とにかく、言い換え、対称性などの力が求められる問題だと感じます。

実装

#include <atcoder/modint>
using mint = atcoder::modint1000000007;
void solve(){
    ll N, A, B;
    cin >> N >> A >> B;
    mint X4 = (N-A-B < 0) ? 0: mint(N-A-B+1) * mint(N-A-B+2) / 2;
    mint X3 = 2 * X4;
    mint X2 = (N-A+1)*(N-B+1) - X3;
    mint X1 = X2 * X2;
    mint zen1 = mint(N-A+1)*mint(N-B+1)*mint(N-A+1)*mint(N-B+1);
    mint ans = zen1 - X1;
    cout << ans.val() << endl;
}

E - Lamps

問題へのリンク

解説

いわゆる主客転倒というものです。ある座標に注目して、その座標が照らされる条件を考え、その割り振りを考えます。

ある頂点が照らされる条件は

  • その頂点が'.'である
  • 上下左右につながってる'.'の中に、少なくとも1つランプが点灯してる
  • つながっていないところはなんでも良い

です。 上下左右につながっている点の個数がわかればいいので、尺取りみたいにして実装しました。 多分もっと綺麗な実装があると思いますが。

実装

#include <atcoder/modint>
using mint = atcoder::modint1000000007;

int main() {
    int H, W;
    cin >> H >> W;
    vector<string> S(H);
    cin >> S;
    ll K = 0;
    rep(i,H)rep(j,W){
        K += S[i][j] == '.';
    }
    vvec<int> dh(H,vec<int>(W, 0));
    vvec<int> dw(H,vec<int>(W, 0));
    vvec<int> d(H,vec<int>(W, 0));
    rep(i,H){
        int r = 0;
        for(int l = 0; l < W;){
            while(r < W && S[i][r] == '.'){
                r++;
            }
            for(int k = l; k < r; k++){
                dh[i][k] = r - l;
            }
            if(l == r){
                l++;
                r++;
            }
            else l = r;
        }
    }
    rep(j,W){
        int r = 0;
        for(int l = 0; l < H;){
            while(r < H && S[r][j] == '.'){
                r++;
            }
            for(int k = l; k < r; k++){
                dw[k][j] = r - l;
            }
            if(l == r){
                l++;
                r++;
            }
            else l = r;
        }
    }
    rep(i,H)rep(j,W)d[i][j] = dh[i][j] + dw[i][j] - 1;
    mint ans = 0;
    rep(i,H)rep(j,W){
        if(S[i][j] == '#')continue;
        ans += (mint(2).pow(d[i][j]) - 1) * mint(2).pow(K - d[i][j]);
    }
    cout << ans.val() << endl;
}

F - Random Max

問題へのリンク

まだ見てません。

AtCoder Library Beginner Contest ABL 参加記

ABC3完でした。Dは冷静になりたかった。。。勉強不足です。

A - Repeat ACL

問題へのリンク

解説

for文を使います。

実装

int main() {
    int K;
    cin >> K;
    rep(i,K){
        cout <<"ACL";
    }
    cout << endl;
}

B - Integer Preference

問題へのリンク

解説

区間の位置を固定して、真ん中が交叉してるかを考えればよいです。swapを忘れて1WA。

実装

int main() {
    ll A, B, C, D;
    cin >> A >> B >> C >> D;
    if(A > C){
        swap(A, C);
        swap(B, D);
    }
    if(C <= B){
        cout << "Yes" << endl;
    }else{
        cout << "No" << endl;
    }
}

C - Connect Cities

問題へのリンク

解説

連結成分を一つの頂点だとみなして、連結させるには、連結成分数 - 1回です。

実装

int main() {
    int N, M;
    cin >> N >> M;
    UnionFind T(N);
    rep(i,M){
        int a, b;
        cin >> a >> b;
        a--, b--;
        T.unite(a, b);
    }
    cout << T.group_num() - 1 << endl;
}

D - Flat Subsequence

問題へのリンク

解説

in-place DPというやつらしいです。値を添字に持つこと、もらうDPにすると区間になるので、セグ木で高速化できます。

以下のけんちょんさんの記事に丁寧に解説されています。LISがこれで求められるのは確かにとなりますね。

qiita.com

実装

#include<atcoder/segtree>

ll op(ll a, ll b){
    return max(a, b);
}
ll e(){
    return 0;
}
const int A_MAX = 300010;
int main() {
    int N, K;
    cin >> N >> K;
    atcoder::segtree<int, op, e> S(A_MAX);
    vector<int> A(N);
    rep(i,N)cin >> A[i];
    ll ans = 0;
    for(int i = 0; i < N; i++){
        int l = max(0, A[i] - K);
        int r = min(A_MAX-1, A[i]+K+1);
        ll prod = S.prod(l, r);
        S.set(A[i], prod+1);
        chmax(ans, prod+1);
    }
    cout << ans << endl;
}