Codeforces Round #640 (Div. 4) DETAYO~~~~~~~~

Div.4に参加しましたが、結果はさんざんでした（大反省）
コンテストURL：https://codeforces.com/contest/1352

A. Sum of Round Numbers

問題概要

左端（一番大きい桁）以外が0の数（例：4000、1、9、800）を「丸められた数」とします。クエリ数と正の整数が与えられるので、「丸められた数」の和でをあらわすとき、必要な「丸められた数」の最小の個数と「丸められた数」を求めてください。

考え

「を10で割ったあまり」をvectorに格納しつつ、が0になるまで10で割っていきます。そのあと、格納された数が0でない場合は桁数を見て10を掛けて出力します（とは書いたけどとてもバグらせました……）。

実装（折りたたんでいます）

#include <bits/stdc++.h>
using namespace std;
 
int main() {
  int T;
  cin >> T;
  
  for( int t = 0; t < T; t++ ){
    int N;
    cin >> N;
    vector<int> num;
    int now = 10;
    while( N > 0 ){
      num.push_back(N%10);
      N/= 10;
    }
    int ans = 0;
    for( int i = 0; i < num.size(); i++ ){
      if( num.at(i) != 0 ){
        ans++;
        num.at(i) *= pow(10, i);
      }
    }
    cout << ans << endl;
    for( int i = 0; i < num.size(); i++ ){
      if( num.at(i) == 0 ) continue;
      cout << num.at(i) << " ";
    }
    cout << endl;
  }
}

B. Same Parity Summands

問題概要

正の整数が与えられます。数列がすべて奇数、またはすべて偶数である場合に、その和をにすることが可能か判定してください。可能な場合はそのような数列を1つ出力してください。

考え

全部奇数にする場合は最後以外1、全部偶数にする場合は最後以外2にして、一番最後の数で帳尻を合わせればいいです。どちらでも帳尻を合わせられない場合は和をにすることができません。
全部奇数にするときは個の1でを埋めて、に入れるが正の奇数になる必要があります。全部偶数にするときには個の2でを埋めて、に入れるが正の偶数になる必要があります。

実装（折りたたんでいます）

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

signed main() {
  int T;
  cin >> T;
  
  for( int t = 0; t < T; t++ ){
    int N, K;
    cin >> N >> K;
    
    if( (N-(K-1))%2 == 1 && N-(K-1) > 0 ){
      //すべて奇数にする場合
      cout << "YES" << endl;
      for( int i = 0; i < K-1; i++ ) cout << 1 << " ";
      cout << N-(K-1) << endl;
    }else if( (N-2*(K-1))%2 == 0 && N-2*(K-1) > 0 ){
      //すべて偶数にする場合
      cout << "YES" << endl;
      for( int i = 0; i < K-1; i++ ) cout << 2 << " ";
      cout << N-2*(K-1) << endl;
    }else cout << "NO" << endl;
  }
}

C. K-th Not Divisible by n

問題概要

正の整数が与えられるので、で割り切れない正の整数のうち番目のものを出力してください。

考え

「小さいほうから個見た場合、で割り切れない数は個含まれる」
上記はが大きくなるほども大きくなる（＝単調性がある）ので二分探索で求めることができるみたいです。「で割り切れない数の個数」を求めるには、個の数の中からの倍数だけを抜けばいいので、ということになります。

実装（折りたたんでいます）

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

signed main() {
  int T;
  cin >> T;
  
  for( int t = 0; t < T; t++ ){
    int N, K;
    cin >> N >> K;
    int ok = 10e12;
    int ng = 0;
    while( ok-ng > 1 ){
      int mid = (ok+ng)/2;
      if( mid - (mid/N) >= K ) ok = mid;
      else ng = mid;
    }
    cout << ok << endl;
  }
}

算数（数学）orエスパーでもできます（本番中はこっちだった）

実装（折りたたんでいます）

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

signed main() {
  int T;
  cin >> T;
  
  for( int t = 0; t < T; t++ ){
    int N, K;
    cin >> N >> K;
    int A = N*K;
    if( A%(N-1) == 0 ){
      cout << A/(N-1)-1 << endl;
    }else{
      cout << A/(N-1) << endl;
    }
  }
}

D. Alice, Bob and Candies

問題概要

飴が個並んでいて、左から番目の飴の大きさはです。アリスは左から、ボブは右から、交互に飴を食べるゲームをします。自分の番の時、（一番最初のアリスの時以外は）「直前に相手が食べた飴の大きさの合計」より大きくなるように、1つ以上の飴を食べる必要があります。飴がなくなったら終了です。ゲームの総ターン数と、アリスとボブそれぞれが食べる飴の個数を出力してください。

考え

dequeを使って、アリスのターンの時は前から、ボブのターンの時は後ろから飴を取っていけばいいです。

実装（折りたたんでいます）

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

signed main() {
  int T;
  cin >> T;
  
  for( int t = 0; t < T; t++ ){
    int N;
    cin >> N;
    deque<int> dq;
    for( int i = 0; i < N; i++ ){
      int A;
      cin >> A;
      dq.push_back(A);
    }
    
    bool fg = 1; //0のときalice
    int alice = 0;
    int bob = 0;
    int K = 0;
    int now = 0;
    int ans = 0;
    while( !dq.empty() ){
      if( fg ){ //aliceのとき
        now += dq.front();
        alice += dq.front();
        dq.pop_front();
        if( now > K ){
          K = now;
          fg = 0;
          now = 0;
          ans++;
        }else if( dq.empty() ) ans++;
      }else{
        now += dq.back();
        bob += dq.back();
        dq.pop_back();
        if( now > K ){
          K = now;
          fg = 1;
          now = 0;
          ans++;
        }else if( dq.empty() ) ans++;
      }
    }
    cout << ans << " " << alice << " " << bob << endl;
  }
}

E. Special Elements

問題概要

数列が与えられます。であるようなの個数を求めてください。

考え

連続する部分数列の和と等しいはいくつありますか？ということなので、まずは累積和をします。lとrの位置をそれぞれ全探索して一通り部分数列の和を求めた後、と等しい数があるか見ます。8000*8000なので、TLEはしなくてもメモリが不安な気持ちになるようなならないような（？）が最大でもであることから、vectorのサイズはで十分です。じゅぴろさんありがとうございました……。

実装（折りたたんでいます）

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

signed main() {
  
  cin.tie(0);
  ios::sync_with_stdio(false);
    
  int T;
  cin >> T;
  
  for( int t = 0; t < T; t++ ){
    int N;
    cin >> N;
    vector<int> A(N);
    for( int i = 0; i < N; i++ ) cin >> A.at(i);
    vector<bool> num(N*N+10);
    vector<int> R(N+1);
    for( int i = 0; i < N; i++ ) R.at(i+1) = R.at(i) + A.at(i);
    
    for( int i = 0; i <= N; i++ ){
      for( int j = i+2; j <= N; j++ ){
        num.at(R[j]-R[i]) = 1;
      }
    }
    
    int ans = 0;
    for( int i = 0; i < N; i++ ){
      if( num[A[i]] ) ans++;
    }
    cout << ans << endl;
  }
}

F, G なんもわからん（就寝……）

競プロお役立ちサイト・ツール

AtCoder Problems以外にも競技プログラミングで役に立つサイトやツールがあるよ～！という紹介記事です。競プロを始めたばかりで、これからたくさん精進したい！という方向けです（全部知ってるわ～という方は、「これ追加したほうがいいよ！」というものがあれば、ぜひ教えてください……）。

AtCoder Scores

atcoder-scores.herokuapp.com

サイト上部「精進グラフ」のリンクを押して、IDを入力することで「レーティングと解いた問題の点数の合計（割る100）」を見ることができます（下画像参照）。

細い線が精進グラフ、太い線が実レートです。IDを複数入力することで、他の人の精進グラフと見比べることもできます。

AtCoder Rivals

atcoder-rivals.herokuapp.com

ライバルのIDを登録することで、コンテストごとにライバルと成績を比較出来たり（下画像参照）、ライバルの提出一覧をまとめてみることができます。

レートの近い人を登録しておけば、どの過去問を解くか悩んだ時の参考にもなるし、モチベーションも上がります！

ac-predictor

ac-predictor.azurewebsites.net

コンテスト中、現時点でどの程度パフォーマンスがあるのか確認できるユーザースクリプトです。サイト上部にある「インストール」を見ての通り、ユーザースクリプトを実行できる環境を用意する必要があります。

インストールして、ac-predictorを有効にすると、AtCoder上でのみ下画像のように「有効」となります。

コンテスト中、順位表からパフォーマンスとレート変動（多少の誤差あり）をリアルタイムで確認できるようになります。

AtCoder Submission User Colorizer

greasyfork.org

AtCoderの提出一覧で、ユーザーの色が一目で分かるようになるスクリプトです（下画像参照）。上のac-predictorと同じく、ユーザースクリプトを実行できる環境が必要です。

「もっと分かりやすい書き方はないかな？」と強い人のコードを読みたい場合や、解けない問題で同レート帯の人のコードを見たい場合に役立ちます。

CF-Predictor

cf-predictor-frontend.herokuapp.com

ac-predictorのこどふぉ版で、Codeforcesのコンテスト中にレート変動をリアルタイムで確認できます。Chromeの場合、Chromeウェブストアからインストールできるため、ユーザースクリプトの実行環境は不要です。

Rating History

rating-history.herokuapp.com

一番上のリンク「Rating History」から、TopCoder・Codeforces・AtCoder・AOJ・yukicoderでのACを足し合わせた総AC数を確認できます。ツイートリンクもあるため、キリのいい数字で適当にツイートして、AC数を記録することもできます。

 AC Logger

aclogger.herokuapp.com

AtCoder Problems等にあるHeatmapをAtCoder・CodeForces・AOJ・yukicoderの合計ACで見ることができます。

また、「今日ACした問題」や「過去にACした問題」を時系列順に、サイト関係なく並べて見ることができます。

以上です。ちょっとずつ増やしていけたらなと思います。何か誤った記述等あればできる限り迅速に直しますので、ご指摘お願いいたします。

Codeforces Round #627 (Div. 3) 出たで

コンテストの感想を書いたことないなーと思ったので書きます！

普段より早い時間で参加しやすかったので、Codeforces Round #627 (Div. 3)に出ました。まだHack時間中だけど多分3完です。

Problem A Yet Another Tetris Problem

URL：https://codeforces.com/contest/1324/problem/A
問題文が読みづらくてちょっとビビりました。上から高さ2、幅1のブロックが降ってきます。テトリスとあるように、横一列にブロックが揃うと消えます。幅（要素数）と高さが初期値として入力で与えられるので、ブロックを降らせていって全部消すことができますか？みたいなことが書いてあります（多分）。
読解できたら問題は簡単で、要素同士の高さの差が奇数の場合は2*1のブロックで埋めることができないのでNOを出力します。

Problem B Yet Another Palindrome Problem

URL：https://codeforces.com/contest/1324/problem/B
「Palindrome」って単語めっちゃかっこいいですね。翻訳されなくてググったら回文って出てきました。数列が与えられるので、部分数列（連続していなくてもよいが順番を並び変えてはいけない）に回文数列（1 2 1みたいな）が含まれていますか？という問題。hackフェーズで落ちてしまいました。泣いてええか？
mapでそれまで出てきた数字を管理して、今見ている数字が2回以上出てきてたらYES（1 1 1 みたいな回文数列が作れる）、1回出てきている場合は直前の数字が今見ている数字と違えばYES（1 2 1みたいな）を出力します。

Problem C Frog Jumps

URL：https://codeforces.com/contest/1324/problem/C
「L」と「R」からなる文字列が与えられ、Lにいるときは左に、Rにいるときは右に移動できます。一番右（文字列の長さNに対してN+1番目）を目指すとき、カエルが一度に移動できる最短距離はいくつですか？みたいな問題です。何でかは分からないんですが（は？）Lを踏んでも無駄っぽいのでRまでの最長の距離+1が答えになります。コンテスト中はこっちのほうがHackされるかもと思っていました……（理屈がわかってないため）

Problem D Pair of Topics

URL：https://codeforces.com/contest/1324/problem/D
要素数Nの数列Aと数列Bが与えられるので、i番目とj番目を選んだ時、A[i]+A[j]>B[i]+B[j]となる組み合わせはいくつありますか？という問題です。AとBの差が大切ぽいのは分かるので、A-Bを配列Cに入れていきます。Cを小さい順に並べたとき、たとえばC[0]が-5だったら、5より大きい数字と組み合わせることで条件が達成できます。「配列C内にホニャララより大きい要素が何個あるか」は二分探索で求められるので、C.end() - upper_bound([今見てるやつより一個後ろのイテレータ], C.end(), 今見てる数字)を答えにどんどん足していけばおっけーです。今見てるやつより一個後ろのやつから探し始めることで、重複して数え上げてしまうのを防げます。

ProblemE & Problem F なんもわからん
こどふぉ　なんもわからん
全人類オヤスミ太郎

ゆるふわ競プロオンサイト #3 に行きました(Div2)

KUPC(昨年10月)ぶりのオンサイトイベントでした。前日の夜に闇討ちに成功し（？）、補欠から繰り上がったので、大阪から日帰りで弾丸東京に乗り込みました！

会場がビルの13階にあったんですが、途中のエスカレーターで右に乗ってしまい、ながたかなさんに特定されます。そしてながたかなさんの隣にいた人をidsigmaさんと勘違いしてしまいました。ふっぴーさんでした……。

会ったことのある方がかっつさん、すぎやんさんくらいしかいなくて一人でビビり倒しました。席を探してるんだと勘違いして、知らない方に「隣座りませんか！？」とナンパしてしまったんですが、相互フォローの方だったのでget kotonaki（sutaさんありがとうございました……）！

以下コンテストの問題についてです（私は緑なのでDiv2に出ました）

www.hackerrank.com

1問目「Yurufuwa Division」はABCのAと同じくらいの難易度でした。2問目「Coupons」もB問題っぽい感じです。3問目「New Comers」は1回目の参加者と2回目の参加者をsetに入れて3回目の参加者が初参加かどうか確認します。簡単目のC問題くらいだと思います。

4問目「Book Rotation」は最初に難しく考えすぎてしまって実装に難航しました。解説はO(H^2*W)って書いてたんですが自分のコードを見返すと制約がH,W<=100なのに4重ループを書いていました（？）通ったのでヨシ！（？）

全然よくなかったです（今見たらint iのところのループが完全に無駄）
5問目「Median Permutation」は全く歯が立ちませんでした……。後ろから見る発想がなくてずっと前から考えてわからんわからんと唸ってました。いったんN<8くらいで愚直実装して法則を探そう……と思ったら無限にバグらせて泣きました。
6問目「Bananas Multiplier」はeasyだけ解けました！見てすぐに、AtCoderから過去に書いたBFSをコピペしてきて、バグらせずに通すことができました。「通った辺の重みがいくらか」を調べる方法に少し悩んだ結果map<pair<int, int>, int>を使ったんですけど良かったのか良くなかったのかわかりません（？）
hardと600点の「Sweet Distribution」は私の理解できそうな範囲内の問題ではなかったので何も言えません（完）

私は緑下位なので参加者の中でもレートは低いほうですが、それでも2時間ずっと楽しんで考えられるコンテストでした……！ぷちさんがかなり早く全完していてびっくり。

懇親会ではながたかなさん、idsigmaさん、じょえさん、けんちょんさん、ぷちさん、まゆさん、のいみさん等々色んな方とお話しできてすごく楽しかったです！本当に関西の人が少なくてちょっとアウェー感がありました（それはそう）。「関西人ってこんな感じなのか……」みたいなことを言われましたが静かな関西人も中にはいます（たぶん）。Div.3をちょくちょくやってることをほめてもらったので、積極的にやっていきたいです。あと「彼氏と仲直りした？」と数人に聞かれました（大変お騒がせしました）

フォルシア社の皆様、すごく楽しいイベントをありがとうございました！次回も行きたいです！