AtCoder 黄色になりました

AtCoderで黄色になりました.

これがレーティンググラフです.ご覧のとおり,青になってから実に2年もの間青〜水の停滞をしていました.しかしここ半年ぐらいで一気にレートが上がるようになり,黄色に上がることができました.

黄色にということにはそれなりに意味があると思うので,特に青になってからどのように取り組んできたのか(どのように取り組むと良いのか)について記述してみたいと思います.

コンテストへの参加

AGC,ARCへの参加をやめました.理由は簡単で,自分にはハードルが高かったからです. 特に最近のAGCは1問目からとても難しく,ARCも自分にはなかなか厳しいセットが多いです.半年ぐらい前から,出場するコンテストをABCに絞り,ABCのパフォーマンスを最大化することに集中するようにしました.結果的にはこれで良かったと思います.

精進

基本的には ABCの過去問 + 「典型90」で練習しました. よく言う問題を「埋める」というのは単に AC をすることを指すと思いますが,単に「埋める」だけではなく問題をマスターするまで繰り返すように意識しました.

特にABCのような典型問題には「解ける」と「早く解ける」のステップがあり,

  • 青diff までは「早く解ける」に行く必要がある.
  • 黄diff は「解ける」に行く

を目標にしました.

その上で,自分は典型90と直近20〜40セットぐらいを何周もしました.

今や ABC は過去問のストックが膨大になってきたので,費やせる時間が同じなら「たくさんの問題を薄く理解する」になってしまいがちですが,「きちんと理解する」の基準をぶらさずにその基準に達した問題を1つ1つ積み上げるようにしたほうが結果的に利得が大きいと思います.(ABCの過去問に対してこの姿勢が取れるのには典型90の貢献が非常に大きいです.典型90のおかげで知識の網羅度がかなり保証されるようになったため,ABCを「手広く」やる必要性がだいぶ低くなったと思う)

意識したこと

以前旧 admin の rng_58 さんに次のようなアドバイスをもらったことがありました:見切り発車で実装しては行けない.頭の中でコードが完全に出来上がるまで書き始めるな

これを練習の時に意識して取り組むようになってからだいぶ実装速度が上がり,結果的に安定するようになったと思います.具体的には,典型90の問題などを題材にして(1度以上通したことがあっても),紙の上で実装手順を全部書き出すなどして完全に理解した状態でコードに起こすことを繰り返しました.

そのほか

難しい問題の解説をどう理解するか?

人によって色々だと思います.自分は印刷したものにペンを持って齧り付いてなんとか理解しようとしました.実は自分は他人のコードをほとんど読むことをしなかったです.と言うのも,読んでも他人のコードをほとんど理解できないからです.強くなればわかるようになるのかな...?

snuke さんの解説は時々見て一緒に実装することで強い人の書き方をトレースしようとしたりはしました.そんなにたくさんやったわけじゃないけどいくつかの書き方はそれで身についた実感もあるので,やって損はないと思います.


そういうわけで,累積の精進にどこまで意味があるか(あんまり昔に背伸びして変に難しい問題を解説読んで通したのに意味があったか?)は微妙なんですが,一応最後に difficulty pie を貼っておきます.

今後

ARC,AGCへの出場も復活します. 橙いけるかなぁ

ABC189参加記

5完 321 位でした。

A

入力をsortしてs[0] == s[2]とするのが(数列が全部一緒かどうかを判定する)常套手段です。

Submission #19606665 - AtCoder Beginner Contest 189

B

実数でやると誤差で死ぬので、適当にスケールを100倍して計算します。ところで、「アルコール度数」がなんであるかを知ってる前提の出題は未成年に厳しい気がします。普通に「B%のアルコールを含んでいます」でいいんじゃないかなぁ

Submission #19606634 - AtCoder Beginner Contest 189

C

何も思いつかなくてSparse Tableで殴った。最大長方形なんですね、確かに

qiita.com

Submission #19606614 - AtCoder Beginner Contest 189

D

全体の真偽値がFalseになる条件を考えます。後ろから見ていって、i 番目が"AND"だったとき、i より右側がFalseの時、i より左側はどうでもいい、ということを足していきます。面白かった

Submission #19610390 - AtCoder Beginner Contest 189

E

アフィン変換のようなことをやると確かにできるんですが、行列を頑張りたくなかったので、(x , y)がそれぞれの操作によってどこに移動するかを計算しました。具体的には(ax+b,cx+d)のような構造体を持って、スワップしたり、x -> 2p - xに変換するみたいなことをしています。

Submission #19623926 - AtCoder Beginner Contest 189

F

本番で解けませんでした。解説を読んで通しました。有向グラフでゴールに辿り着くまでの期待値ってゴール側から見ていって「 i 番目のマスにいる時あと何手でゴールできるか」を見ていくのが常套なんですね、それで「0番目のマスからあと何手?」を定数でおいて、一次方程式に落とす、というのが面白かった。

Submission #19654965 - AtCoder Beginner Contest 189

ABCは8割ぐらいの打率で2000prfが出るようになったのでなんとかABCでレートをあげていきたいです。

また頑張ります。

ARC111-C Too Heavy

まあ言われりゃ簡単なんだよねこういうのも... あんまコンテスト中考えてなかったけどTwitterとかで大体見ちゃったのでとりあえず通した。

問題概要

https://atcoder.jp/contests/arc111/tasks/arc111_c

N人の人とN人の荷物がある。体重A_iの人 i は、重さB_p[i] の荷物p[i] を持っている。 人 i と人 j の持っている荷物を交換する、という操作を繰り返すことによって、全ての人 i が、荷物 i を持っている、という状態にしたい。ただし、人 i は体重 A_i 以上の重さの荷物を持った時点で、それ以上荷物交換の操作に加わることはできない。最小の操作回数でこれを実現する操作列を構築せよ。また、どのように操作しても実現できない場合は-1を出力せよ。

  • 1 ≤ N ≤ 200000

解法

  • 自明な不可能条件( B[i] >= A[i] && i != p[i] )は先に弾いておく。

  • 置換を巡回置換に分割すると、巡回置換の中で体重が軽い人から順番に荷物を渡していくことが最適。人 i に荷物 i を渡すためのswap操作は下の絵のように、サイクルのサイズを1小さくすることに対応しており、これを繰り返すことが操作回数最小を満足することは明らか。

f:id:andoreiji11:20210110144731j:plain

下の実装では p[i] = x が人 i が荷物 x を持っている、ということに対応し、owner[x] = i が荷物 x は人 i によって所有されている、ということに対応している。swap操作によってこの接続の繋ぎかえのようなことを行なっている。

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

int main(void){
    int n;cin >> n;
    vector<int> a(n),b(n),p(n),owner(n);
    
    for(int i=0;i<n;i++)cin >> a[i];
    for(int i=0;i<n;i++)cin >> b[i];
    for(int i=0;i<n;i++)cin >> p[i] , p[i]-- , owner[p[i]] = i;
    
    for(int i=0;i<n;i++){
        if(b[p[i]]>=a[i] && i != p[i]){
            cout<<-1<<'\n';
            return 0;
        }
    }
    
    vector<int> idx(n,0);iota(idx.begin(),idx.end(),0);
    sort(idx.begin(),idx.end(),[&](int& i,int& j){
        return a[i] < a[j];
    });
    
    vector<pair<int,int>> ans;
    for(int i : idx){
        if(i != p[i]){
            int j = owner[i];
            ans.emplace_back(i+1,j+1);
            owner[p[i]]=j;
            p[j]=p[i];
            owner[i]=i;
        }
    }
    
    cout<<ans.size()<<'\n';
    for(auto[a,b]:ans){
        cout << a << ' ' << b << '\n';
    }
}

ARC111-D Orientation

これも解けるべきだったなと思う 解法はほぼeditorialそのまま

問題概要

https://atcoder.jp/contests/arc111/tasks/arc111_d

無向グラフが与えられる。次の条件を満たすようにグラフの各辺を向きづけよ。

  • 頂点 i から到達可能な頂点数が(自分も含めて)ちょうど C_i 個存在する。

constraints

  • 1 ≤ |V| ≤ 100

解法

  • 各辺について、両端の頂点をa , bとして、C_a != C_bだったら明らかである。C_a > C_bの時、bから到達できる頂点には必ず a から到達できるため、a -> bの方向に向きづける。

  • C_a == C_b の場合。C_aと同じ連結成分内にあって、Cの値が同じ頂点は、「強連結」であることがわかる。ある頂点集合が強連結であるとは、その頂点集合内の任意の2点について、2点を結ぶパスが存在することである。さて、問題は無向頂点集合を向きづけて強連結にすることになったが、これは公式解説にも概要があるが

[Tutorial] The DFS tree and its applications: how I found out I really didn't understand bridges - Codeforces

ここに詳しく説明されている。これ読んだことあってライブラリまで作ってたのにな...

  • 結論としては、DFS木に含まれる辺(span-edge)については「潜る」方向に、そうで無い辺(back-edge)については「遡る」方向に向きづければ良い。
#include<bits/stdc++.h>
using namespace std;

#define LIM 110

int N,M;
pair<int,int> edge[LIM * LIM * 2];
int g[LIM][LIM];
int c[LIM];

int visited[LIM],depth[LIM];
vector<int> graph[LIM];

bool dfstree[LIM][LIM];

void dfs(int x,int pre,int dpt){
    visited[x] = 1;
    depth[x] = dpt;
    for(auto e : graph[x]){
        if(e != pre && !visited[e]){
            dfstree[x][e] = dfstree[e][x] = true;
            dfs(e,x,dpt+1);
        }
    }
}

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    cin >> N >> M;
    for(int i = 0;i < M;i++){
        int a,b;cin >> a >> b;
        a--,b--;
        edge[i] = make_pair(a,b);
        g[a][b] = g[b][a] = 1;
    }
    for(int i = 0;i < N;i++){
        cin >> c[i];
    }
    
    // c[i] == c[j]の辺を無向辺で結ぶ
    for(int i = 0;i < N;i++){
        for(int j = 0;j < N;j++){
            if(g[i][j] && (c[i] == c[j])){
                graph[i].push_back(j);
            }
        }
    }
    
    for(int i = 0;i < N;i++){
        if(!visited[i]){
            dfs(i,-1,0);
        }
    }
    
    for(int i = 0;i < M;i++){
        auto[a,b] = edge[i];
        if(c[a] > c[b]){
            cout << "->" << '\n';
        }else if(c[a] == c[b]){
            if(dfstree[a][b]){
                cout << (depth[a] < depth[b] ? "->" : "<-") << '\n';
            }else{
                cout << (depth[a] > depth[b] ? "->" : "<-") << '\n';
            }
        }else{
            cout << "<-" << '\n';
        }
    }
    
}

ARC111-B Reversible Cards

これは解けないとダメなやつだった

https://atcoder.jp/contests/arc111/tasks/arc111_b

問題概要

N枚のカードがあり、ある面にはA[i] , その裏面にはB[i]が書かれている。N枚のカードの裏表を自由に選択できる時、表を向いている数の種類は最大で何種類?

  • 1 ≤ N ≤ 200,000
  • 1 ≤ A_i ,B_i ≤ 400,000

解法

  • maxflowの計算量的にフローはダメだろうと思っていたが、どうもうまくやるとできたらしい。とりあえず、典型としてグラフを構成する。

  • A_iとB_iの間に辺を張り、無向グラフを構成する(流石に初見じゃない)

  • こうして構成されたグラフにおいて、カード(A[i] , B[i])のうちどちらかを表にすることは、Edge(A[i] , B[i])において、一方の頂点を色塗ることに対応していて、構成された連結成分が木ならばサイズ-1だけ、木ではないならば全部の頂点を色付けることができる。 類題が思い出せないけどABCとか企業ARCで去年あたり2、3回見た記憶がある...

  • ところで、この方法だとサイズが1の時だけ例外になる。これも含めて計算できる方法もあるのかな

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

#define LIM 400010

int N;
vector<int> graph[LIM];
int visited[LIM];

int component_size = 0;
bool istree;
void dfs(int x,int pre){
    component_size++;
    visited[x] = 1;
    for(auto e : graph[x]){
        if(e != pre){
            if(visited[e]){
                istree = false;
            }else{
                dfs(e,x);
            }
        }
    }
}

int main(void){
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    cin >> N;
    for (int i = 0; i < N; i++) {
        int a,b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    
    int ans = 0;
    for (int i = 0; i < LIM; i++) {
        if(graph[i].size() && !visited[i]){
            component_size = 0;
            istree = true;
            dfs(i , -1);
            if(istree && (component_size != 1)){
                ans += component_size - 1;
            }else{
                ans += component_size;
            }
        }
    }
    
    cout << ans << '\n';
    
}

Codeforces Round #687(Div.1) B - XOR-gun

メモ。

Problem - D - Codeforces

問題概要

単調非減少な数列Aが与えられる。この数列に対して、次の操作を繰り返し行い、単調非減少ではない状態にしたい。

・ 隣接する二つの要素を取り除き、そこに二つの要素の排他的論理和を挿入する。

必要な操作回数は最低何回か?(数列Aを長さ1になるまで操作しても達成できない場合-1)

解法

明らかに、あるi,i+1,i+2について、MSB(a[i]) == MSB(a[i+2])ならば、a[i] > (a[i+1] xor a[i+2])。よって答えは1である。これにコンテスト中気づけなかった。痛い...。

その上で、操作後の数列Cを考えると、全てのCの要素は、Aの連続部分列の排他的論理和であることより、

rng_xor(int l,int r) := (a[l] xor a[l+1] xor ... xor a[r-1])

とした時、rng_xor(l,r) > rng_xor(r,k) ならば、添字組{l,l+1},{l+1,l+2},...,{r-2,r-1},{r,r+1},...,{k-2,k-1}に対して操作を施すことで所望の数列が得られる。この時、答えを(k - l - 2)で更新する。

ACコード:

https://codeforces.com/contest/1415/submission/99959557

Google KickStart 2020H-D "Friends"

サクッと解けた。この回はずいぶん簡単だったと思う(KickStartって結構難しい問題あるんだけど...)

codingcompetitions.withgoogle.com

解法

簡単にいうと、人 i が文字xを経由して人 j に到達する、というルートを、文字xについて26通り試すと、最短ルートは必ず上記26通りのどれかにはヒットするということが言えるので、26通りのDijkstra最短経路を前計算しておくと、各QueryについてO(1)で求められます。ちょっとジャッジに時間がかかってそうで不安になりましたが、下のコードでACしました。

// solution for KickStart2020H-D
// author : lynmisakura
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> struct Edge{
  int from,to,id; T cost;
  Edge(int from,int to,T cost):from(from),to(to),cost(cost){}
  Edge(int from,int to,int id,T cost):from(from),to(to),id(id),cost(cost){}
  Edge(){}
};
template<class T> struct Graph{
  int n;
  vector<vector<Edge<T>>> g;
  Graph(int n):n(n){
    g.resize(n);
  }
  void add_edge(int from,int to){
    g[from].emplace_back(from,to,1);
  }
  void add_edge(int from,int to,T cost){
    g[from].emplace_back(from,to,cost);
  }
  vector<Edge<T>>& operator[](int i){ return g[i]; }
};
template<class T> struct Dijkstra{
  #define INF (numeric_limits<T>::max()/2)
  using P = pair<T,int>;
  Graph<T> G;
  vector<T> d;
  vector<int> prev;
  Dijkstra(Graph<T>& G):G(G){}
  void solve(int s){
    d.assign(G.n,INF);
    prev.assign(G.n,-1);
    d[s] = 0;
    priority_queue<P,vector<P>,greater<P> > que;
    que.push(P(0,s));
    while(que.size()){
      P p = que.top();que.pop();
      int v = p.second;
      if(d[v] < p.first) continue;
      for(int i = 0;i < G[v].size();i++){
        Edge<T>& e = G[v][i];
        if(d[e.to] > d[v] + e.cost){
          d[e.to] = d[v] + e.cost;
          prev[e.to] = v;
          que.push(P(d[e.to] , e.to));
        }
      }
    }
  }
  bool reachable(int t){
    return d[t] != INF;
  }
  vector<int> get_path(int t){
    vector<int> path;
    for(;t != -1;t = prev[t]){ path.push_back(t); }
    reverse(path.begin(),path.end());
    return path;
  }
  T& operator[](int i){return d[i];}
};
void main2(){
  int n,q;cin >> n >> q;
  vector<string> a(n);
  Graph<int> graph(n + 26);
  for (int i = 0; i < n; i++) {
    cin >> a[i];
    vector<int> used_chars(26,0);
    for(char x : a[i]) used_chars[x - 'A']++;
    for (int j = 0; j < 26; j++) {
      if(used_chars[j]){
        graph.add_edge(i,n+j,1);
        graph.add_edge(n+j,i,1);
      }
    }
  }
  vector<Dijkstra<int>> D(26,Dijkstra<int>(graph));
  for (int i = 0; i < 26; i++) {
    D[i].solve(n+i);
  }
  for (int i = 0; i < q; i++) {
    int s,t;cin >> s >> t;
    s--,t--;
    bool reachable = false;
    int mindist = int(1e9);
    for (int j = 0; j < 26; j++) {
      reachable |= (D[j].reachable(s) && D[j].reachable(t));
      mindist = min(mindist , D[j][s] + D[j][t]);
    }
    if(!reachable)cout << -1 << ' ';
    else cout << 1 + mindist / 2 << ' ';
  }
  cout << '\n';
}
int main(){
  cin.tie(0);
  ios::sync_with_stdio(false);
  //cout << fixed << setprecision(20);

  int tt;cin >> tt;
  for(int i=1;i<=tt;i++){
    cout << "Case #" << i << ": ";
    main2();
  }
}