モグリンの競プロ備忘録

主に競プロの記事を書きます

青色になりました

お久しぶりです、mogurinです。この度ABC188にて入青を果たしました、やったね!!

0. いつもの

いつものやつです、いやいつものとか言いながらこれやるの初めてなんですけど他の人やってるんでとにかくいつものやつです。
f:id:mogurin1000000007:20210112001435p:plain
f:id:mogurin1000000007:20210112002230p:plain
f:id:mogurin1000000007:20210112002249p:plain
f:id:mogurin1000000007:20210112002306p:plain
他の人に比べると少し精進は少なめ?春休み入ったら少し時間できると思うんで頑張りたいですね、でもエロゲの誘惑に負けないかが不安だな

1. 水->青で新しく身に着けたアルゴリズム

  • マージテク


天才かよ

  • ダブリング

algo-logic.info
前々からやらなきゃなーと思ってたダブリングを履修しました、わかってみれば簡単かつ汎用性のある知識だった。

  • 部分集合の全列挙

ark4rk.hatenablog.com
青になってから覚えたのでここに入れていいか微妙だけど感動したから入れた、天才かよ(2回目)


Q. ところで、これらのアルゴリズムをコンテスト中に実際に使う機会はありましたか?
A. いいえ
マージテクなんかはむしろコンテスト終わってから教わった感じですね、しゃーない。どちらかというとAtcoder Libraryとかをたくさん使う機会があったので新規のアルゴリズムよりもデータ構造に慣れたことの方がデ/ア面の成長としては大きい気がします。

2. 水->青になるまでにやったこと

  • 今までの知識の復習

大学でAtcoderの問題を使って初歩のアルゴリズムを教えてくれる授業がありまして、ぶっちゃけ単位と点が欲しくてとったのですが、結果的に知識を復習することになりました、それがために...なった...のかなぁ?あんまり関係ない気もする。

  • 毎回コンテストに出る

ABCもARCもAGCも大体出た、偉い!!


ここだけの話水の時から何か特別にやったこと、ないんですよね...。後述しますけど多分青変できたのはパチンコで当たり台引いたのが大きそう...。

3. 水->青になるまでの過程

急上昇期

f:id:mogurin1000000007:20210112215448p:plain
急上昇期

パチンコ当たり台連発時期、なんか面白いくらい青パフォが出た。

急落期

f:id:mogurin1000000007:20210112221319p:plain
急落期

コンテスト2回で-99になりました、Foxてめぇだけは許さねえからな...。
競プロ辞めたくなるとかそんなことは特になく、まぁうまく行き過ぎてたから補正だろみたいに捉えるようにしてました、決してショックでポテチ爆食いしたりしてない。

停滞期

f:id:mogurin1000000007:20210112230339p:plain
停滞期

下がるわけではないけどなんかぱっとしなかった時期、ただこの辺りからABCが目に見えて易化してた(具体的にはFがなんか典型っぽくなった)のでうまくクリティカル出せば一気にいいパフォが出そうな予感があった、実際ABC185で初の全完したりもした。

入青

f:id:mogurin1000000007:20210112230912p:plain
入青

うまく考察がハマったり既出問に当たったりして、全完黄パフォ2回で無事入青、やったぜ!!

4. 意識していたこと

そろそろ早解きにも意識を向ける

さっっっっすがに全く早解き要素を気にしないわけにはいかなくなってきたのでひとまずA~D問題を問題読みながら入力部分を書くとか、「早く解こう!!」と思って解くようにしてます、するとちょっと早くなる(ほんとか?)。

天才になる

私は天才私は天才私は天才私は...



はい、前にも書いた奴ですね、自分を天才と信じ込むとなんかうまくいく!、かも。その分失敗したときのダメージもでかくなるからほどほどにやろう。

コンテストでその都度新規の知識をつける

個人的に解けてない問題の解説はあまり読みたくない人なんですが、コンテスト終了後のTLを眺めてるとなんとなく自分の知らない知識が必要だったかどうかがわかります。その時は潔く解説を見る、もしくは必要な知識を他の人に聞くようにしてました。SPJのみなさんいつもありがとう。


こーんな感じですかね、書き忘れたことあったらあとで追記しよ

5. ここからやりたいこと

  • 水埋め、青埋め

ちらほら精進不足のぼろが出始めてる気がするので春休み使ってなんとか精進したい...。

  • 環境構築

せっかくインストールしたVSCodeがただのライブラリ置き場になってるのでちゃんと動くようにしたい...。これも春休み中に他の人に聞いたり調べたりしながらだな。


黄色はおそらく一筋縄ではいかなそう...。なんとか今年中に暖色コーダーになることを目指して頑張っていきたいです。

6. 最後に

ひとまず寒色の中では一番上の色になれて自分の中で一区切りついたかな、という感じです。ここからはより一層厳しい戦いになっていきそうですが、まぁ趣味として楽しんでいるのでほどほどに頑張っていきたいです。また今年中に黄変記事を自分が書いてればいいな~、なんて。何はともあれ、ここまで読んでいただきありがとうございました。

7. 余談


よし、ツイートした or いいねしたアカウント覚えた。月夜ばかりと思うなよ...?(ちなみにこの後アイコン画像をマイナーチェンジした)

ABC184E Third Avenue

問題

S,G,.,#,a~zからなる H \times Wのグリッドが与えられます。この時、#は入ることができないマス、a~zはテレポーターのあるマスを表します。この時、次の規則に従って移動するときSからGへは最短何手で移動できるか求めよ。

1手で次のどちらかの移動が可能である。

  • 現在いるマスと上下左右で隣接しているどれかの#以外のマスに移動する。
  • 現在いるマスがa~zのマスであるときにのみ可能である。同じ文字の書かれたマスに移動する。

 

制約

 1 \leq H,W \leq 2000

考え方

テレポートでグラフ上に新しい辺が増えただけなんだから愚直に同じ文字のマス同士に辺を張ってBFSでOK!!

f:id:mogurin1000000007:20201127030232p:plain
どうして...

よく考えると例えばグリッド上の半分が全部aだったりするとa同士に張られる辺の数が O((HW)^2)になって破滅することがわかります。TLE出た瞬間にダメなケース思いつくことってあるよね...

コンテスト中はただのBFSをバグらせてたこともあり(は?)、残り時間もなかったんでここで終わったんですが、うーーんとうなってると、"同じ文字が書かれているマスをすべて一つのノードにまとめてしまう"アイデアを思いつきます。天才だな―
と思ってたんですけどこの方法だとテレポーターを使う時と単純にそのマスを通過するときの区別ができません。ダメかー
またうんうん唸ってると"同じ文字のマスをつなぐ超頂点を作る"ことでその超頂点を通過するときにだけコストがかかるようにすればいいことに気付きます。なるほどなー

ここまで思い浮かべは後は01-BFSなりDijkstraなりで実装できます。結構シンプルな解法だけにコンテスト中に思い浮かびたかったなー

コード

今回は01-BFSで実装してみることにします。

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0;i < (int)(n);i++)
using ll = long long;
const long long INF = 1LL << 60;

template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }

ll dp[4010000];


int main()
{
  ll H,W; cin>>H>>W;
  vector<vector<ll>> graph(H*W+26,vector<ll>(0));
  vector<string> grid(H); rep(i,H) cin>>grid[i];
  
  //テーブル初期化
  rep(i,H) rep(j,W) dp[i*W+j]=INF;
  for(int v=H*W;v<H*W+26;v++) dp[v]=INF;
  
  auto f=[&](ll i,ll j){
    return i*W+j;
  };
  
  //graph作成
  rep(i,H) rep(j,W) {
    if(grid[i][j]=='#') continue;
    if(i<H-1&&grid[i+1][j]!='#') {
      graph[f(i,j)].push_back(f(i+1,j));
      graph[f(i+1,j)].push_back(f(i,j));
    }
    if(j<W-1&&grid[i][j+1]!='#') {
      graph[f(i,j)].push_back(f(i,j+1));
      graph[f(i,j+1)].push_back(f(i,j));
    }
    
    if(grid[i][j]=='.'||grid[i][j]=='S'||grid[i][j]=='G') continue;
    
    graph[H*W+grid[i][j]-'a'].push_back(f(i,j));
    graph[f(i,j)].push_back(H*W+grid[i][j]-'a');
  }
  
  //sとg
  ll s,g;
  rep(i,H) rep(j,W) {
    if(grid[i][j]=='S') s=f(i,j);
    if(grid[i][j]=='G') g=f(i,j);
  }
  
  //01-bfs
  deque<ll> deq;
  deq.push_back(s);
  dp[s]=0;
  while(!deq.empty()) {
    ll v=deq.front(); deq.pop_front();
    for(auto nv:graph[v]) {
      if(nv<H*W&&chmin(dp[nv],dp[v]+1)) deq.push_back(nv);
      if(nv>=H*W&&chmin(dp[nv],dp[v])) deq.push_front(nv);
    }
  }

  cout<<(dp[g]==INF?-1:dp[g])<<'\n';

  return 0;
}

感想

テレポーター部分をどう処理するかが鍵な問題でしたね、十分に考察時間が取れれば思いつけた自信はあるので、ただのBFSとかをバグらせないようにしたい...、それともライブラリ化したほうがいいかなぁ。
それはそれとして"共通のノードをつなぐ超頂点を作る"のはふつうに典型っぽいのでこの機会に覚えておきます。ここまで読んでいただきありがとうございました。

余談

某discordにて
僕「いやー、こういうのをぱっと思いつけるようになりたい」
???「え、これは典型」
???「まぁ典型」
???「うん」
精進不足です、すいませんでした...
???「まぁPASTで既出だったんだけど」
それはダメだろAtcoder

ABC184D increment of coins

問題

袋の中に金貨が A枚、銀貨が B枚、銅貨が C枚入っています。この時、どれかの硬貨が100枚になるまで次の操作を続けます。

  • 袋の中の硬貨をランダムに1枚取り出し、同じ種類の硬貨を2枚戻す。

この時、操作回数の期待値を求めなさい。

制約

 0 \leq A,B,C \leq 99
 A+B+C \geq 1

考え方

期待値、ほい来た線形性!!...あれ?
はい、この問題貨幣一枚取り出すごとにその確率が前の各々の硬貨の枚数に依存するし終了時点での硬貨の総枚数が状態によって異なるので線形性使おうとすると破滅しますね、困ったな―
コンテスト中にほんとに困ったのでとりあえず「期待値 競プロ」あたりで検索してみます。

f:id:mogurin1000000007:20201126105124p:plain
ひとまず検索は基本

んー、やっぱり線形性が基本ぽいしなんか問題をうまく読み替えればいいのかなー、うん?
f:id:mogurin1000000007:20201126105458p:plain
D...P...?
制約から状態の種類は 100^3=10^6くらい...、そしてD問題...(その当てはめ方はどうなんだ)
はい、見えましたね、DPで解けそうなことがわかったらあとは遷移を考えるだけです。

解法1

私がコンテスト中に考えた解法です。金貨の数が a枚、金貨の数が b枚、金貨の数が c枚となる確率をdp[a][b][c]とすると、遷移が配るDPでうまく書けそうです。すなわち、

dp[a+1][b][c] += dp[a][b][c]*(double)a/(a+b+c);
dp[a][b+1][c] += dp[a][b][c]*(double)b/(a+b+c);
dp[a][b][c+1] += dp[a][b][c]*(double)c/(a+b+c);

と書けますね、後は操作1回ごとに硬貨の総枚数が1枚ずつ増えることを考慮すると、 a,b,cのどれか一つのみ 100である状態の (a+b+c)-(A+B+C)とdp[a][b][c]の積を各々足すことで期待値が求まります。

解法1コード

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0;i < (int)(n);i++)
using ll = long long;


double dp[110][110][110];

int main()
{
  cout << fixed << setprecision(15);

  ll A,B,C; cin>>A>>B>>C;
  dp[A][B][C]=1.0;
  
  for(int a=A;a<=100;a++) for(int b=B;b<=100;b++) for(int c=C;c<=100;c++) {
    //a,b,cのいずれかが100ならその時点で遷移終了
    ll count=0;
    if(a==100) count++;
    if(b==100) count++;
    if(c==100) count++;
    if(count) continue;
    
    dp[a+1][b][c]+=dp[a][b][c]*double(a)/(a+b+c);
    dp[a][b+1][c]+=dp[a][b][c]*double(b)/(a+b+c);
    dp[a][b][c+1]+=dp[a][b][c]*double(c)/(a+b+c);
  }
  
  double ans=0;
  for(int a=A;a<=100;a++) for(int b=B;b<=100;b++) for(int c=C;c<=100;c++) {
    //a,b,cのいずれか1つのみが100の状態の確率だけ考える。
    ll count=0;
    if(a==100) count++;
    if(b==100) count++;
    if(c==100) count++;
    if(count!=1) continue;
    
    ans+=((a+b+c)-(A+B+C))*dp[a][b][c];  
  }
  
  cout<<ans<<'\n';
  return 0;
}

解法2

俗にいう期待値DPというやつですね。dp[a][b][c]を金貨が a枚、銀貨が b枚、銅貨が c枚から始めたときの期待値と置くと、今度は貰うDPできれいに書けますね。すなわち

dp[a][b][c] += dp[a+1][b][c]*(double)a/(a+b+c);
dp[a][b][c] += dp[a][b+1][c](double)b/(a+b+c);
dp[a][b][c] += dp[a][b][c+1](double)c/(a+b+c);
dp[a][b][c] += 1.0;

うーん綺麗、しかもこの解法だと最後に合計する手間がないのでぱっと思いつけるのならこっちのほうが良さそうですね。思いつけるようになりたい...。
どの問題かは言わないでおきますが期待値DPはEducational DP Contestでも扱われていたので、うん、やっぱり典型として使いこなせるようになっておこう。

解法2コード

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0;i < (int)(n);i++)
using ll = long long;

double dp[110][110][110];

int main()
{
  cout << fixed << setprecision(15);

  ll A,B,C; cin>>A>>B>>C;
  for(int a=99;a>=A;a--) for(int b=99;b>=B;b--) for(int c=99;c>=C;c--) {
    ll s=a+b+c;
    dp[a][b][c]+=dp[a+1][b][c]*(double)a/s;
    dp[a][b][c]+=dp[a][b+1][c]*(double)b/s;
    dp[a][b][c]+=dp[a][b][c+1]*(double)c/s;
    dp[a][b][c]+=1.0;
  }
  
  cout<<dp[A][B][C]<<'\n';
  
  return 0;
}

感想

最近期待値/確率DPがABCで出ていなかった(もしかしたら私が参加し始めた3月から考えると初?)ので頭から抜け落ちてて手間取りました。検索したらすぐに出てきたからよかったものの精進しないとですね...。読んでいただきありがとうございました。

ABC184C Super Ryuma

問題

無限に広がるグリッド上の指定された二つの座標
 (r_1,c_1),(r_2,c_2)
の間を次の規則に従って駒を移動させる際に、必要な最小手数を答えなさい。

駒は一手で次の条件のどれかを満たす (a,b)から (c,d)へのが可能である。

  •  a+b = c+d...(移動A)
  •  a-b = c-d...(移動B)
  •  |a-b|+|c-d| \leq 3...(移動C)

制約

  •  1 \leq r_1,c_1,r_2,c_2 \leq 10^9

考え方

この問題が茶diffなのは正直びっくりしました。そんなに簡単な場合分けかなぁ。
とりあえず問題をみてぱっと思いつくことは、

  • AとBの移動を一回ずつ行うことでパリティの等しいマスには最大 2手で移動できる。
  • 上の移動にさらにCの移動を行うことで最大 3手で全てのマスに移動ができる。

ですね。つまりどのマスにも 3手以内で移動できることがわかりました。ならば答えとしてあり得るのは 0,1,2,3の高々 4つしかないんだから場合分けでいけるはず。さらに少し考えれば 0手なのは当然動かない時、 1手なのは上のA,B,Cのどれかの条件を満たす時なので、 2,3手の時を場合分けできれば問題が解けたことになります。

ここで解説では 2手で移動するときを丁寧に場合分けすることで求めているのですが、ここでは少し異なる解法で解いてみます。使用する典型は
"ある対象への条件を別の対象の条件に読み替える"
です。最近だとABC181F Silver Woods
atcoder.jp
が、"障害物の点にかぶらないように半径 rの円を動かす"を"点を半径 rの円の障害物と被らないように動かす"、に読み替えることで解く問題でした。「動かす点」に関する条件を「障害物」に関する条件に読み替えてしまうのですね。

さて、今回の問題では
" (r_1,c_1)から (r_2,c_2) 2手で移動できるかどうか"

" (r_1,c_1)から 1手で移動できるマスに (r_2,c_2)から 1手で移動できるマスが存在するかどうか"
に読み替えます。" (r_1,c_1)からの移動"に関する条件を一部" (r_2,c_2)からの移動"に関する条件に読み替えてしまうわけです。

ここで一番単純な方針は
" (r_2,c_2)から 1手で移動できるマスを全列挙してしまい、これらの中で一つでも (r_1,c_1)からの移動に関するA,B,Cの条件のどれかを満たすマスが存在するかどうか求める。"
です。ただこれには問題があって (r_2,c_2)から 1手で移動できるマスって無限にあるんですよね、どうしよっかなー。

ここで図とじーっとにらめっこすると
" (r_2,c_2)からA,Bどちらか 1手で移動できるマスの中に (r_1,c_1)からの移動に関するA,Bの条件のどちらかを満たすマスが存在する"
が、先ほど考えた
" (r_1,c_1) (r_2,c_2)パリティが等しい"
と同値であることがわかります。ならばあと考えるべき 2手の移動は二つ、

  • A→C、B→C、C→A、C→Bの移動
  • C→Cの移動

 5つじゃん!!(すいません)、ともあれどの移動にもCの移動が含まれており、なおかつA→CとC→A、B→CとC→Bの移動で行けるところは各々実質変わらないことに気付けば、これらの移動については
" (r_2,c_2)からCの移動 1手で移動できるマスを列挙してしまい、これらの中で一つでも (r_1,c_1)からの移動に関するA,B,Cの条件のどれかを満たすマスが存在するかどうか求める。"
ことで判定可能であることに気づけます。いやー中々に骨の折れる問題だった。

コード

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

#define rep(i,n) for (int i = 0;i < (int)(n);i++)
using ll = long long;

//移動の条件を全て関数化してしまう
bool can_reach(ll a,ll b,ll c,ll d) {
  if(a+b==c+d) return true;
  if(a-b==c-d) return true;
  if(abs(a-c)+abs(b-d)<=3) return true;
  
  return false;
}

int main()
{
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  // cout << fixed << setprecision(15);

  ll r1,c1,r2,c2; cin>>r1>>c1>>r2>>c2;
  //移動が0手の時
  if(r1==r2&&c1==c2) {
    cout<<0<<'\n';
    return 0;
  }
  //移動が1手の時
  if(can_reach(r1,c1,r2,c2)) {
    cout<<1<<'\n';
    return 0;
  }
  //パリティが等しいとき
  if(~(abs(r2-r1)+abs(c1-c2))&1) {
    cout<<2<<'\n';
    return 0;
  }
  //(r2,c2)からCの移動1手で行けるマスが(r1,c2)から1手の移動で到達可能な時
  for(int i=c2-3;i<=c2+3;i++) for(int j=r2-3;j<=r2+3;j++) {
    if(abs(i-c2)+abs(j-r2)>3) continue;
    if(can_reach(r1,c1,j,i)) {
      cout<<2<<'\n';
      return 0;
    }
  }
  //それ以外は3手
  cout<<3<<'\n';
  
  return 0;
}

感想

やっぱ難しいよこれぇ、場合分け問題は総じて苦手な僕ですがそれでもこれが茶diffはおかしいだろ、インフレは日々加速してるんですね...。精進せねば。ここまで読んでいただきありがとうございました。

ARC108C Keep Graph Connected

問題

 N頂点 M辺の"多重辺を含む"連結なグラフが与えられる。この時辺 iにはラベル c_iが各々貼られているので、すべての頂点に 1以上 N以下の整数を書き込むことで、

"辺の両端の頂点に書き込まれた整数のうち片方のみが辺に張られたラベルと等しい辺のみを残したグラフが連結のままである"

ことが可能であるか判定し、また可能ならそのような整数の書き込み方を1つ上げなさい。

 

制約

 2 \leq N \leq 10^5

 M \leq 2 \times 10^5

与えられるグラフに自己ループはない

 

考え方

「連結グラフの辺削除、ってことは全域木!」、とここまではコンテスト中に考えが及んだんですが最初に思いついた方針が

"根を決め打ちして、各頂点について、根なら自分とつながっているすべての辺のラベルと異なる整数、それ以外の頂点は親とつなぐ辺のラベルの整数を書き込む"

というのが解法かなと思ったんですがこれは例えば

 3~~2 \\ 1~~2~~1 \\ 2~~3~~1

というテストケースで落ちます。つまり同じ頂点をはさんで同じ整数のラベルが張られた辺があるとダメなわけですね。

ここでコンテスト中はいい案も浮かばずdpっぽくて面白そうな問題Dに逃げてしまったのですが、実はこれ

"根のみ適当な整数をいれて、他の頂点については親の頂点に書かれた整数が、自分と親とを結ぶ辺に貼られたラベルの整数と等しかったら自分の頂点にはそれ以外の適当な数を書き、等しくない場合は自分の頂点に辺に貼られたラベルの整数を書く"

という方針でいいんですね、うーん思いつかなかった。根から貪欲に決めるという部分は一緒なので、後は実験とかして気づきたかったですね。

 

コード

https://atcoder.jp/contests/arc108/submissions/18293471

 

感想

コンテスト中の問題の取捨選択は難しいのでそれ自体をミスったのはやむなしですが、最初の嘘解法時点でも'No'になるケースはないのわかりそうなものなのに気づけてなかったのがダメですね、ここに気付いてればもう少しCに時間割こうと思えていたかもしれない。反省です。後コンテスト中に直感的にそんな気がしてただけで

"連結な無向グラフを考える時は全域木を疑う"

も別に典型として知ってたわけじゃなかったのでこれも改めて覚えなおします。読んでくれてありがとうございました。

 

 

ARC108B Abbreviate Fox

問題

長さ Nの英小文字からなる文字列 Sが与えらえれる。ここから連続部分文字列'fox'を削除する操作を繰り返した時に最後に残る Sの最小の長さをこたえよ。

 

制約

 1 \leq N \leq 2 \times 10^5

 

考え方

これ茶diffかぁ、沼にハマっちゃってたねぇ。コンテスト中は'fox'を()列に置き換えてみたり、左から貪欲に'f''fo'がそれまでに出てきたかどうかでフラグ管理してみたり、色々試してみたけど大事なのは

"愚直な操作を通るようにできないか考えてみる"

ことでしたね。文字列に対する挿入、削除は"末尾を除き"一回当たり O(N)かかりますが末尾に限り O(1)で済むのでなんとか文字列に対する末尾の操作のみでシミュレーションできないか考える。この考え方はABC158 String Formation

atcoder.jp

とかでもありましたね。今回の場合は

"空文字列 sに対して文字列 Sの文字を左から順番に加えていき、文字列'fox'が出てきたら逐次削除する"

という方法で計算量 O(N)で十分高速にシミュレーション可能なんですね、うーん思いつきたかった。

 

コード

https://atcoder.jp/contests/arc108/submissions/18291630

 

感想

うーん、悔しい。ともあれ

"文字列に対する挿入/追加を何らかの文字列の末尾への処理のみの操作に置き換えることで高速化する"

という自分のなかでの新しい典型を作れたのでよしとしよう、次似たような問題出たらぜって―解く。読んでくれてありがとうございました。

 

余談

はてなブログって見たまま編集だとソースコード貼り付けられないんすね...。別にこのままでもいい気はするけどせっかくだからどこか機会見つけたらはてな記法の勉強しようかな...。

入水しました

はじめまして、mogurinです。ブログを始めるにあたって最初に何の記事を書こうかなーと思ったので色んな人が書いてて書きやすそうな色変記事から書くことにしました。ですので、基本的にここに書いてあることは入水した約一か月前のことになりますがご了承ください。ついでに初めての記事だから色々荒いのも許して

f:id:mogurin1000000007:20201121040945p:plain

これわざわざ入水時点のグラフ引っ張り出してくるのに時間かけたのウケる

1.自己紹介

所属:東京大学理科一類

競プロ歴:およそ9か月、(入水時点で7か月強)

Twitter:mogurin (@mogurin_kyopro)

Atcoder ID: mogurin

2月にAPG4bをやる前はプログラミングどころか人差し指タイピングだったAtcoderの完全純粋培養(?)競プロerです。趣味は当然競プロ、後最近はノベルゲーにハマってます。ICPCに一緒に出てくれるUT生募集中です!!

 

2.水になるまでにやったこと

 

はじめは水になるまでにやったことを、各色になるまでごとに分けて書こうかなぁ、と思ったんですけど、元々の原稿が6000字を超えたあたりで心が折れたのでこの記事はゆるっと書いてもし何か特筆して書きたくなったら別の記事に書きます。

あーこれも結構あるな面倒くさいなー........ん?

そうだ、他の入水記事書いてる人で僕の知ってるアルゴリズム全部書いてくれてる人の記事引用すればいいんだ!!(最低)

というわけでこちら

 

AtCoder 水色わーい!soohprogramming.wordpress.com

 

W_Acmanさんの入水記事です、いろんな記事見たけどこの記事に載ってて僕が履修してないアルゴリズムはあっても入水時点での僕が履修しててこの記事に載ってないアルゴリズム多分ない、気がする。(こんな引用の仕方でごめんなさいW_Acmanさん...、ちなみにかなり良いこと書いてるんでみんな読んでみてね、特に後半)

 

流石にこれでアルゴリズム部分終わりだと神様から赤べことか頭の上に落とされそうなんで個人的に印象深いとこだけでも色々書くか

 

  • 累積和、BFS/DFS、bit全探索、コンビネーション(組み合わせ)

驚くべきことにこれらの単語を (単語) けんちょん の順にならべて検索するだけであなたに最適な記事が出てきます、けんちょんさん、いつも良質な記事をありがとう。

なぜかコンビネーションだけ出てこなかったからリンク貼っときます。しっかりしてGoogle

qiita.com

 

通称DP、これ一つの呼び名でまとめるのどうかと思うよね、いや私も便利だから使うが。簡単なのは本当に簡単ですが、時に赤diffになってABC参加者を苦しめたりします恐ろしい子。対策としては Educational DP Contest

atcoder.jp

がおすすめです、解けば解くほど典型DPがわかる(気がする)。例のごとくけんちょんさんの解説記事があるのでこちらもおすすめです。

qiita.com

 

後はフレンズさんの記事もユーザー解説についてるので好きな方(あるいは両方)を読むといいと思います、どちらも非常にためになります。一度学べば想定解がDPじゃない問題も少し遠回りすれば楽な発想でDPで解けたりすることもあるので学んで損はないはず。

 

  • ModInteger、セグ木、BIT、UnionFind(、遅延セグ木)

データ構造ってめんどいよね、わかる、僕も実装できない。

けどAtcoder優しいから公式データ構造を作ってくれました、公式マイバチみたいなもんだね(伝われ)。使い方もドキュメントに書いてある至れり尽くせり仕様なので、もしセグ木とかの実装に困っている人がいたらガンガン使いましょう!!

ところで遅延セグ木だけは結構ドキュメントが難しい気がします(主観)、なんかわかりやすく書いてるところないかなー

 

 

opt-cp.com

 

 

ありましたね、というわけでoptさんの記事です、非常に細かくわかりやすく遅延セグ木の使い方が書かれています。これで遅延セグ木を使う問題も怖くない!!optさんありがとう!!

 

  • 二分探索

二分探索ってあれだよね、単調増加(減少)数列から少ない計算量で必要な値引っ張ってこれる奴。

 

atcoder.jp

?????????ナニコレ????????

 

 

というわけで人によっては典型、人によっては大苦戦を強いられた問題ですが(私は後者、コンテスト中には解けなかった)、この問題を解いたことがない人はこれを解説ACでも良いので解いてから続きを読んでほしいです。

 

 

 

 

 

 

 

はい、おかえりなさい(?)、値を決め打ちすることで二分探索の問題に持ち込む、 自力でこれ思いつくのはさすがに無理だろ。このように二分探索にはある値以上/以下で性質の変わる値の求値問題を、Yes/No判定問題に持ち込めるという強力な側面があります。使いどころを見極めればこれは非常に強力なツールです、時に黄diff以上の問題でもこの方法で簡略化して解けることがあります。流石にこのレベルの問題だと二分探索が本質であることはまずなさそうですが、問題を簡略化できることで視野が開けることはよくあります。(経験談)

 

アルゴリズムで書きたいこと他にあったかなー、特に思いつかないんで思いついたら追記しますね。(適当)

 

  • やったこと

  • 茶diff埋め、緑diff埋め

茶diffと緑diffを埋めました、ちなみに今はdiff変更により埋まってないグラフに逆戻りしました、悲しい...。特に効果があるかといわれると...、ほら、埋まるとなんか達成感あるじゃないですか、そんな感じです、多分。実際一色下の色埋めればその色のレートになれるって黄コーダー(当時青コーダー)が言ってた。また埋めなおさなきゃ...

f:id:mogurin1000000007:20201121102356p:plain

悲しい...
  • バチャ

くじかつに出てみました。楽しいけど長続きはしなかった...やっぱり時間縛られるのきついよね。

 

 

あれ俺やってること意外となくね?大丈夫か?

緑diff全部埋めるのは言葉以上に大変なはず、多分、そういうことにしておきます。

 

3.意識していたこと

  • 諦めない

負けないで、もーおー少しー(古い)

コンテスト中、明らかに自分の知らない典型を含んでいる、あるいは自分の解いてきた問題より高難易度、または添え字ガチャで外れしか出ない(それはただのバグでは?)、など様々なこちらの心を折りに来る事態に遭遇します、した。こんな時、ほんっっっとーーーに心が折れそうになるのですが、最後時間いっぱいまで折れないことを私は意識していました。もちろん何もできずに終わることのほうが多いのですが、ごく稀にミラクルは起こります。自分が散々悩まされた問題の解法がひらめいたとき、そしてその解法が通った時の達成感はひとしおです。ダメでもともと、最後まで粘り続けるのは、きっと大切なことだと思います。

 

  • 自分を天才だと信じる

理由なんてなんでもいいです、とにかく私は天才なんです。僕は天才僕は天才僕は天才僕は...

 

 

 

 

 

と、コンテスト前(あるいは最中)に自分に暗示をかけると「この問題も天才の私に解けないはずがない」と考えられるようになります。これほんと。実際舐めてかかったほうが超速で典型に落とし込む道筋が見つかって解けたりする。やっぱ俺天才だわ。よし、この調子でABC183全か...

f:id:mogurin1000000007:20201121135822p:plain

え?

f:id:mogurin1000000007:20201121135844p:plain

は?

f:id:mogurin1000000007:20201121140009p:plain

引退です...

こんな感じで解くべき(解かないと冷える)問題が解けないと著しくメンタルを傷つける諸刃の刃です、用法用量を適切に守って服用しましょう。

4.最後に

なっがながと毒にも薬にもならない駄文書いた感ありますけどまぁ当初の目標である入水できたことは素直に嬉しいのでこっからも頑張ってくつもりです。結構入青近づいてきた気がするし!(単に最近あたりくじ引いてただけ説は、ある)

結局考えること精進の仕方は人それぞれなんですが、私の記事が少しでも役に立つ人がいてくれるならこんなにうれしいことはありません。

最後に、twitterその他での私の質問に嫌がる素振りも見せず丁寧に答えてくださった皆さんや、いつもわかりやすい解説記事を書いてくれる皆さん、ここまで様々なアドバイスを下さった TeamSPJ のお三方、そして何よりもここまでこの記事を読んでくださったあなたへの感謝をもって、この記事の締めとさせていただきたいと思います、本当にありがとうございました!!

 

余談

 この記事書いてる最中に昔のやったこと見返してたんですけどAPG4b普通に難しくありません?詰まりやすいポイントと対処法とかまとめた記事を次は書いてみようかな