AtomからVSCodeに乗り換え実験中

emacs、vim、sublime text、atom等々色々使ってきたが、最近はatomに落ち着いていた。

しかしながら、githubがmicrosoftの一員になって久しく、今後はatomの開発リソースがvscodeに集約されていくのかなといった感じもあり、vscodeを使ってみる。

vscodeに追加できるAtom Keymapという拡張機能を使うと、かなりスムーズに移行できる。

あと、shift + ctrl + e等での行選択ができなかったので、これらも追加。

色々拡張機能とかおもしろそうなのあったら試していこうかな。

お好みキーバインディング

[
    {
        "key": "shift+ctrl+e",
        "command": "cursorEndSelect",
        "when": "textInputFocus"
    },
    {
        "key": "shift+ctrl+n",
        "command": "cursorDownSelect",
        "when": "textInputFocus"
    },
    {
        "key": "shift+ctrl+p",
        "command": "cursorUpSelect",
        "when": "textInputFocus"
    },
    {
        "key": "shift+ctrl+a",
        "command": "cursorHomeSelect",
        "when": "textInputFocus"
    },
    {
        "key": "shift+ctrl+b",
        "command": "cursorLeftSelect",
        "when": "textInputFocus"
    },
    {
        "key": "shift+ctrl+f",
        "command": "cursorRightSelect",
        "when": "textInputFocus"
    }
]

AtCoder ABC 138の「E - Strings of Impurity」

はじめに

AtCoder Beginner Contest 138 の「E - Strings of Impurity」問題です。 解説では、ある文字→ある文字への距離を事前計算する方法と、二分探索で解く方法の両方が紹介されてましたが、自分は二分探索で解きました。

解き方

1. 結合後の文字は巨大なので、sとtの文字種が一致している限り、解がある
2. 文字ごとに出現位置を保持しておいて、都度二分探索で調べる

コード

typedef long long ll;

int main(int argc, char *argv[]) {
  string s,t;
  map<char, vector<int> > mp;
  cin>>s>>t;

  for(int i=0;i<s.size();i++){
    char c = s[i];
    mp[c].push_back(i);
  }

  for(int i=0;i<t.size();i++){
    char c = t[i];
    if(mp.count(c)==0){
      cout<<-1<<endl;
      return 0;
    }
  }

  ll res=0;
  int s_p=0;

  for(int i=0;i<t.size();i++){
    char c = t[i];
    auto it = lower_bound(mp[c].begin(), mp[c].end(), s_p);
    if(it == mp[c].end()){
      res += s.size() - s_p;
      s_p = 0;
      res += mp[c][0] - s_p + 1;
      s_p = mp[c][0] + 1;
    } else {
      res += *it - s_p + 1;
      s_p = *it + 1;
    }
  }

  cout<<res<<endl;

  return 0;
}

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

AtCoder Beginner Contest 138の振り返り

はじめに

AtCoder Beginner Contest 138に参加したのでその振り返り。 A,B,C,D解けて、Eは初級レベルの失敗でTLEに、、悔やまれる。

A - Red or Not と B - Resistors in Parallel

Aはそのまま、Bはdoubleとか気をつけて実装する。

C - Alchemist

1回合成するたびに2で割ることになるので、小さいものから貪欲に合成していく。

D - Ki

入力段階では、単に頂点に値を足していって、最後にDFSで根からスタートして回答を一気につくる。

typedef long long ll;

vector<int> g[200005];
ll val[200005];

void dfs(int p, int c, ll sum){
  val[c] += sum;
  for(auto v : g[c]){
    if(v!=p){
      dfs(c, v, val[c]);
    }
  }
}

int main(int argc, char *argv[]) {
  int n,q;
  cin>>n>>q;
  for(int i=0;i<n-1;i++){
    int a,b;
    cin>>a>>b;
    a--,b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }
  for(int i=0;i<q;i++){
    int p,x;cin>>p>>x;
    p--;
    val[p] += x;
  }
  dfs(-1, 0, 0);

  for(int i=0;i<n;i++){
    if(i)cout<<' ';
    cout<<val[i];
  }
  cout<<endl;

  return 0;
}

E - Strings of Impurity

コードは、こちらのエントリーで。

ループ中に配列のコピーが発生するコードを書いてしまい、TLEに。。

F - Coincidence

E解けなかったので開かず。

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

ABC116の「D - Various Sushi」

問題概要

AtCoder Beginner Contest 116 の、D - Various Sushi。 解説や提出されたコード見ても？？？だったけど、自分で書いてみて理解できた。

解き方

1. 種類ポイントのことは一旦忘れる

2. 単にK個分、得点順にでかいものだけを食べていく
   答えがこの種類数を下回ることはないのでここから上の種類数を調べる。

3. 選ばれてない種類の中で一番得点が高い寿司と、2個以上選ばれた種類の中で一番得点が低い寿司を交換する
   これを繰り返すことで種類数別の最大得点が得られるのであとは比較するだけ

コード

typedef long long ll;

typedef pair<int, int> P;

bool used[100005];
ll scores[100005];

int main(int argc, char *argv[]) {
  ll n,k;
  cin>>n>>k;
  // 全部の寿司を得点の高い順に
  priority_queue<P> all_pq;
  // タイプが重複した寿司のうち、得点の低いもの集合
  priority_queue<P, vector<P>, greater<P> > less_pq;
  for(ll i=0;i<n;i++){
    int t,d;cin>>t>>d;
    all_pq.push({d,t});
  }

  // 種類ポイントのことは一旦忘れる
  // 単にK個分、得点順にでかいものだけを食べていく
  ll sum = 0;
  int cnt=0;
  for(ll i=0;i<k;i++){
    auto v = all_pq.top();all_pq.pop();
    if(!used[v.second]){
      used[v.second] = 1;
      cnt++;
    }else{
      less_pq.push(v);
    }
    sum += v.first;
  }
  scores[cnt]=sum;

  // 選ばれてない種類の中で一番得点が高い寿司と、2個以上選ばれた種類の中で一番得点が低い寿司を交換する
  while(!all_pq.empty()&&!less_pq.empty()){
    auto v = all_pq.top();all_pq.pop();
    if(used[v.second])continue;
    auto v2 = less_pq.top();less_pq.pop();
    used[v.second]=true;
    sum -= v2.first;
    sum += v.first;
    cnt++;
    scores[cnt] = sum;
  }
  ll res=0;
  for(ll i=0;i<=n;i++){
    if(!scores[i])continue;
    res=max(res, scores[i] + i*i);
  }
  cout<<res<<endl;

  return 0;
}

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

ABC130の「D - Enough Array」

AtCoder Beginner Contest 130のD - Enough Array。

ポイント

ナイーブに実装するとTLEになるので尺取法で計算していく。

コード

typedef long long ll;

int main(int argc, char *argv[]) {
  ll res =0;
  ll n,k;cin>>n>>k;
  std::vector<ll> v(n);
  for(int i=0;i<n;i++){
    cin>>v[i];
  }
  int rp=0;
  ll sum=0;
  for(int lp=0;lp<n;lp++){
    while(sum<k&&rp<n){
      sum += v[rp++];
    }
    if(sum>=k){
      res += n-rp+1;
    }
    sum -= v[lp];
  }
  cout<<res<<endl;

  return 0;
}

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

ABC137のE - Coins Respawn

感想

AtCoder Beginner Contest 137のCoins Respawn。

自分のようなビギナーには、グラフ問題のエッセンスが詰まったような問題でいろいろ勉強になった。

ポイント

1. Pは辺のコストとしてまとめて考えることができる
2. 辺のコストに-1かけることで、最短経路問題にできる
3. 負の閉路がある可能性があるのでベルマンフォード法を使う
4. 逆辺でつくったグラフをBFSやらDFSで探索することでゴールにたどり着ける頂点を事前に調べる

コード

typedef long long ll;

struct edge {int from;int to;ll cost;};
vector<edge> es;

ll dist[2505];
ll inf=1ll<<50;
vector<int> rev_g[2505];
int ok[2505];
ll n,m,p;

void bfs(int v) {
  ok[v]=1;
  for(auto u : rev_g[v]) {
    if(ok[u])continue;
    bfs(u);
  }
}

void solve_bf(){
  dist[0]=0;
  for(int i=0;i<n;i++){
    bool update = 0;
    for(auto e : es) {
      if(ok[e.to] && dist[e.from] != inf && dist[e.to]>dist[e.from]+e.cost){
        dist[e.to]=dist[e.from]+e.cost;
        update=1;
      }
    }
    if(!update)break;
    if(i==n-1){
      cout<<-1<<endl;
      exit(0);
    }
  }
}

int main(int argc, char *argv[]) {
  for(int i=0;i<2505;i++)dist[i]=inf;

  cin>>n>>m>>p;
  for(int i=0;i<m;i++){
    int a,b;ll c;cin>>a>>b>>c;a--;b--;
    es.push_back({a,b,-c+p});
    rev_g[b].push_back(a);
  }

  bfs(n-1);
  solve_bf();

  cout<<max(dist[n-1]*-1, 0ll)<<endl;

  return 0;
}

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?

AtCoder Beginner Contest 137 の振り返り

AtCoder Beginner Contest 137に参加したので備忘録。

急いでA〜Dまで解いた結果、パフォーマンス的には1600を超えていたので、安定して速く解けるようになると青になれるのかな。

A - +-x

実装のみのスピード勝負。

B - One Clue

これまたスピード勝負。

C - Green Bin

文字列のソートして、配列全体もソートして、あとは数え上げる。

D - Summer Vacation

公式の解説にも書いてあるけどM日後から逆に見ていくパターン。

日数を前にさかのぼっていって、選べる報酬額を全部プライオリティキューにいれていく。

typedef long long ll;

// 報酬でかい順に出てくるキュー
priority_queue<int> pq;

// 日数と報酬のマップ
map<int, vector<int> > mp;

int main(int argc, char *argv[]) {
  int n,m;
  cin>>n>>m;
  for(int i=0;i<n;i++){
    int a,b;
    cin>>a>>b;
    mp[a].push_back(b);
  }
  ll res=0;
  for(int i=1;i<=m;i++){
    for(auto t : mp[i]) {
      pq.push(t);
    }
    if(pq.empty())continue;
    res+=pq.top();
    pq.pop();
  }
  cout<<res<<endl;

  return 0;
}

E - Coins Respawn

挑戦したけど本番中は解けず。復習した。

F - Polynomial Construction

そっ閉じした。

プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?