お布団を温めた初チーム戦（WUPC2020＆HUPC2020 1日目）感想

WUPC2020

https://onlinejudge.u-aizu.ac.jp/beta/room.html#WUPC2020/
早稲田生による有志コン、WUPC2020にれたすさん（@fairly_lettuce）、mo3tthiさん（@mo3tthi）とチーム「melomelody」で参加しました。
チーム戦が初めてなうえに二人とも初めて話す人（mo3tthiさんはFF外）で、しかも私だけメッチャレートが低い（れたすさんは水、mo3tthiさんは青）だったのでビビってましたが、お二人ともすごく気さくな方でした。
結論から言うととにかく足を引っ張りまくってしまったんですが、とても勉強になりました。早稲田の方たち、そして組んでくれたお二人ありがとうございました……。
最初は私がAやる→れたすさんがBやる→その間にmo3tthiさんがC以降を読んで解けそうな問題を探す、という方針を立ててもらいます。Aを出したらCE。なんで？！（using Graph = vector>;を消したら直りました、C++17で提出しなかったことが原因かも）
れたすさんがBを実装している間に後ろから問題文を読み進めていきます。Mはやることは分かりやすい気がする（？）木グラフの問題だったんですが、ぱっとイイ感じの実装方針は全く思い浮かばず、一回どっかからBFSなりしてどうしたらいいんだろう？とか考えてました。次に見たLは自分の手に負える見た目ではなかったのですぐに諦めました。KはLより問題文の意味は理解できたけど、解き方が全く思い浮かばなくてこれも飛ばします。mo3tthiさんがIまで読んでくださってたのでここで合流します。

以下、かなり記憶があやふやなので時系列が間違ってるかも
mo3tthiさん「Fはいけそうです、よければスギノキさんどうですか（菩薩）」
スギノキ「じゃあF見てみます、後ろ三問だとMが難しくなさそうに見えました」←ほんまか？？？
Fを見てみると、2のべき乗をイイ感じにイイ感じすればACできそうなのはそうなんですが、細かいところは全然わかりません。ここでmo3tthiさんが大まかな方針を説明してくれるんですが、私がテンパりまくっていて、死……。結局、Cを解き終わったmo3tthiさんが実装してくれます（ほんとにすみません）。あとから3人で解説見て、「2のべき乗全部見ても全然間に合うんだな～～～」とへこむなどしました。
私がFを見て布団を温めている間に、Mは1回移動するごとに変動する距離はたかだか1だから何とかなるはず、と言ってれたすさんが頑張ってくれます。

mo3tthiさん「GはDPなんですが、スギノキさんはDP得意ですか」
スギノキ「えっとえっと緑コーダー並みって感じです」←ほんまか？？？？？？？
「休憩とか考えないで普通にDPした場合」の結果を利用してあれこれできないかな、と思ったんですが、私が思いついたのは「普通にDPした場合のやつに上書きして、i分目から休憩した場合～」みたいなわけのわからん考え方だったので普通に却下です。次に、mo3tthiさんが「休憩回数を決め打ちしてdpするのはどうですか」と言ってくれて、そこから実装してくれますが通らず……。
スギノキはとくに何の役にも立てないまま5時間が経過しました。
ここで、DPを雰囲気でしかやってきてないなという気づきと反省が生まれます。DPぽいなと思ったときは実装しながら添え字ガチャ！（素振り）てなことをしているので、私には緑並みどころかDPパワーは全くないのでした。DPバチャなどできる範囲で苦手意識を克服する努力はしていたつもりだったんですが、いざやってみると全く身についていないなと感じました。

HUPC2020 Day1

https://onlinejudge.u-aizu.ac.jp/services/room.html#HUPC2020Day1/info
ntkさん（@ntk_ta01）、SEELさん（@Seadogg012）という、レートが近く個人的に気になっている二人とチーム「grin」で参加することができました。3人ともレートが緑中盤くらいという感じです。一応現在のレート順にかんがみて（？）SEELさんがA→スギノキがB→ntkさんがCという方針を立てました。

SEELさんがAを通してくれたあとも、私はBが全然解けていませんでした。
スギノキ「全くわからないです」
ntkさん「この記事どうでしょう」
↓つるさんの「imos 法を線形代数で理解・一般化して，フィボナッチ数列でも足せるようする」記事
https://theory-and-me.hatenablog.com/entry/2020/08/23/182712
スギノキ「全く、分からないです……（勉強不足のため）」
しかしimos法でやれるっぽいことは分かりました。ここで「区間に等差数列を足す　imos法」でググります。
↓アルメリアさんの記事「等差数列の重ね合わせを求める」章
https://betrue12.hateblo.jp/entry/2019/10/19/163736
完全に答えが載っています！やった～～～～～～～！！！！！！！！！！！！！！！ここでなぜか実装をバグらせますが（は？）ntkさんが直してくれてACしました。

次にCについて全員で考えてみます。
ntkさんの、Nが小さい場合とそうでない場合で分けてみるのはどうか、というのを聞いて確かに～～～ってなり、とりあえず小さい場合のbit全探索を書きます。小さい場合は通りました。
大きい場合については審議するうちに「N>18くらいから、答えが一意に定まることはなくなるよね」という話になり、そこから「前20桁くらいだけ見ればよくない？？」と、答えに大きく前進します……！
小さい場合と似たような感じのコード（余った桁はアスタリスクで埋める）を書きましたがTLE。ここで実装をSEELさんに代わってもらいましたが、結局TLEは取れずじまいでした。あとから考えると、私の書いていたコードはN=40の場合1000000*60000くらい計算することになるのでぜ～～～～～～～～～～んぜん間に合ってないんですが、その時は分からなくて首をかしげていました……。

結果は2完でしたが、近いレートの人たちとあれこれ話しながら問題について考えることができた（かつ、3時間なので集中力のない私でも最後まで考え切れた）のでとても楽しいコンテストでした。同じ大学に競プロやってる人がいないので、ICPCとかには全然出られないんですが、こういう有志コンで積極的にチーム組んでいきたいな～って思いました。あともっと強くなってさわれる問題を増やしたいな……となりました。完。

Codeforces Round #668 (Div. 2) 出たよ～～～～

約2か月半ぶりのこどふぉ、Div.2に参加しました。結果は2完（A,B）で緑落ちです。超絶自業自得……。Dまでは他の人に教えてもらったのでブログに残そうと思います。
コンテストURL：https://codeforces.com/contest/1405

A. Permutation Forgery

問題概要

～までの整数で、要素の重複なく構成された長さの数列に対応して、以下のの長さの数列を作ります。

が等しく、かつである長さの数列をひとつ出力してください。

考え・反省

が等しくなるためには、ペアになる要素が元の数列と同じである必要があります。たとえばだったら1個目+2個目、2個目+3個目がペアになって長さ2の数列になります。合体後の順番はソートされるので、数列をreverseするだけで通ります。
↑数列を反転させれば通るのに、サンプルを見てものすごく悩んでしまって嘘解法を投げました（懺悔）

B. Array Cancellation

問題概要

となるような、長さの数列が与えられます。この中から一度の操作につき番目と番目の要素を選び、番目の要素にを足し、番目の要素からを引きます。であった場合にはコストがかからず、そうでない場合には1回の操作で1コストかかります。
数列の要素を全てにするために必要な最小のコストを求めてください。

考え・反省

「今まで出てきた正の数の和」を持っておき、もし負の数が出てきたらそこから引いていきます。これを最後まで繰り返すと、数列の和が0になることから、「残った負数の和」と「残った正数の和」は等しいので、その絶対値を出力します。
↑という条件を見逃していて、無限に不可能なパターンについて考えていました。涙。

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

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

signed main(){
  int Q;
  cin >> Q;
  for( int q = 0; q < Q; q++ ){
    int N;
    cin >> N;
    vector<int> A(N);
    int plus = 0;
    for( int i = 0; i < N; i++ ){
      cin >> A[i];
      if( A[i] > 0 ){
        plus += A[i];
        A[i] = 0;
      }
      else{
        if( plus+A[i] >= 0 ){
          plus += A[i];
          A[i] = 0;
        }else{
          A[i] += plus;
          plus = 0;
        }
      }
    }
    cout << plus;
    cout << "\n";
  }
}

C. Balanced Bitstring

問題概要

だけで構成された長さの文字列が与えられます。にはの好きな方を選んで置換します。この文字列の中から連続した個（は偶数）を取り出した際、どの部分でもとの個数が等しくなるようにすることはできますか？

考え・反省

modごとに見るということを全く思いつきませんでした（反省）。
で等しくなる部分の文字がすべて同じで、かつ最初の個が条件を満たしていればYES、そうでなければNOです。
たとえばでのとき、最初の個は「」で、1個右にずらした部分から個取ると「」です。最初の個が条件を満たしていてくれれば、抜き出す部分を1個右にずらした際に新しく部分文字列に入った文字（右端）と、左端にあった捨てる文字が等しいことで、1と0の数の均衡を保てます。
もし最初の個の中にが含まれていた場合は未確定にしておいて、途中でかが出てきたら確定させます（そして確定後の文字列が条件を満たすか確認します）。

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

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

signed main(){
  int Q;
  cin >> Q;
  for( int q = 0; q < Q; q++ ){
    int N, K;
    cin >> N >> K;
    string S;
    cin >> S;
    bool fg = 1;
    vector<char> num(K, '?');
    int sum = 0;
    int hatena = 0;
    for( int i = 0; i < K; i++ ){
      if( S[i] == '0' ) sum--;
      else if( S[i] == '1' ) sum++;
      else hatena++;
      num[i] = S[i];
    }
    if( abs(sum) > hatena ) fg = 0;

    for( int i = K; i < N; i++ ){
      if( num[i%K] == '0' && S[i] == '1' ) fg = 0;
      else if( num[i%K] == '1' && S[i] == '0' ) fg = 0;
      if( num[i%K] == '?' && num[i%K] != S[i] ){
        num[i%K] = S[i];
        hatena--;
        if( S[i] == '1' ) sum++;
        else sum--;
        if( abs(sum) > hatena ) fg = 0;
      }
    }
    if( fg ) cout << "YES\n";
    else cout << "NO\n";
  }
}

D. Tree Tag

問題概要

AliceとBobは頂点の木グラフ🌲の上で鬼ごっこをします。最初はAliceが頂点、Bobが頂点にいて、Alice→Bobの順番で移動します。一回の移動でAliceは最大、Bobは最大の距離を移動できます（ここでの距離とは頂点間の辺の数を指します）。この移動を回する間に、AliceがBobと同じ座標に辿り着けたらAliceの勝ち、そうでなければBobの勝ちです。鬼ごっこの勝者を出力してください。

考え

回移動できる＝いちいち二人の動作を追ってたら絶対に間に合わないので、何かしらの条件があるはず。移動回数が多い分Aliceが有利な気がする（？！）ので、「どうやったらBobが勝てるか」で少し考えてみます。

• 初期配置で、Aliceとの距離が以上離れてないとダメ（最初の1手でAliceに追いつかれてしまうため）
• 木の直径がある程度大きくないとダメ（Aliceがどの頂点にも1手で移動できる状態になると詰むため）

→「ある程度」がどのくらいか？を考えます。ちょうどグラフの真ん中らへんに立てば、木の直径が以下だとAliceはどこにでも行けてしまうので、それより大きい必要があります。

• 

→これ教えてもらうまで理解できませんでした……。
まず、頂点の数よりも移動可能回数のほうがずっと多いので、Bobは逃げ回るときに「Aliceのいる方向」へ逃げないといけない状況が生じます。その際、Bobの移動可能距離がAliceの「1手で移動可能な範囲」よりも大きければ、つかまってしまうゾーンを「飛び越えて」逃げ回ることができます。逆に、それよりBobの移動距離が小さい場合はどこかでAliceが1手で移動できる範囲に入らざるを得ず、捕まってしまいます。

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

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

signed main(){
  int Q;
  cin >> Q;
  for( int q = 0; q < Q; q++ ){
    int N, A, B, DA, DB;
    cin >> N >> A >> B >> DA >> DB;
    A--; B--;
    Graph G(N);
    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);
    }

    //木の直径を求める
    vector<int> dist(N, -1);
    queue<int> que;
    dist.at(A) = 0;
    que.push(A);
    while( !que.empty() ){
      int v = que.front();
      que.pop();
      for( int nv : G.at(v) ){
        if( dist.at(nv) != -1 ) continue; //すでに通っていたらスルー
        dist.at(nv) = dist.at(v)+1;
        que.push(nv);
      }
    }

    int start = 0;
    int k = 0;
    for( int i = 0; i < N; i++ ){
      if( k < dist[i] ){
        k = dist[i];
        start = i;
      }
    }

    vector<int> ponyo(N, -1);
    ponyo.at(start) = 0;
    que.push(start);
    while( !que.empty() ){
      int v = que.front();
      que.pop();
      for( int nv : G.at(v) ){
        if( ponyo.at(nv) != -1 ) continue; //すでに通っていたらスルー
        ponyo.at(nv) = ponyo.at(v)+1;
        que.push(nv);
      }
    }

    int dia = 0;
    for( int i = 0; i < N; i++ ) dia = max(dia, ponyo[i]);
    if( dist[B] <= DA || dia <= 2*DA || DB <= 2*DA ) cout << "Alice\n";
    else cout << "Bob\n";
  }
}

競プロなんもわからん！解散！

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をちょくちょくやってることをほめてもらったので、積極的にやっていきたいです。あと「彼氏と仲直りした？」と数人に聞かれました（大変お騒がせしました）

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