AtCoderで青になりました！！！
AtCoder 青です！！！！！！！！！！！！ pic.twitter.com/2BHOi2Lwtj
— ysystem (@ysystem_prog) 2021年5月1日
AtCoderで青になりました。ここまでこれるとは思っていなかったのでとても嬉しいです！！今回も色変記事を書こうと思います。
水→青での変化
DPの克服
水色になった時点ではDPに対する苦手意識が非常に強く、コンテストで出たとしてもほとんど解けないような壊滅的な状態でした。ですが、練習を積み重ねていくうちに徐々に解けるようになりました。練習方法については次章の「青になるまでにやったこと」を参照してください。ABCやABC相当のコンテストでは、DPの問題が1問解けるとパフォーマンスが大きく変わってくると思います。
青になるまでにやったこと
精進についてです。
JOI埋め（DP練習）
AOJ/AtCoder-JOI
JOIの問題にはDPの問題が多いということをTwitterで何度か見かけたので、JOIの問題を解くことにしました。主に難易度6、7の問題を解いていました。
AtCoder Problems Virtual Contest の DP100問
https://kenkoooo.com/atcoder/#/contest/show/f1fd5759-0b54-4365-974e-6681a3837443
これはDPの練習になると思い、活用しました。
Codeforcesの問題を解く
春休み以降、Codeforces Problemsを利用して紫diff（1900~2000）の問題を解いていました。
新たな知識
水色になってから学習した内容です。
- 行列累乗
- 強連結成分分解
- 2-SAT
- ダブリング
- 平方分割
- セグ木上の二分探索
- 二辺連結成分分解
など
精進記録
水色になってから+864問解きました。
竸プロを続けること
竸プロを続けてきて本当によかったと思っています。
去年水色になってから
— ysystem (@ysystem_prog) 2021年5月1日
春学期(5月~7月)：課題地獄で竸プロどころじゃなかった
夏休み(8月~9月)：頑張って精進してた 一回黄パフォを出すもその後停滞
秋学期(10月~2021 1月)：モチベがなくなり進んで精進しなくなった
春休み以降(2月~)：精進再開
って感じ
まともに精進してた期間が短いですが、コンテストに参加することは継続していました。
今年の2月、PASTの過去問が残っていたのでやってみたら上級相当の点数が取れて嬉しかったので、モチベが回復しました。
こういう時期もありました。正直とても辛かったです...
それでも諦めませんでした！
その後5回連続でレートが上がり、無事青に。
〜 今後は 〜
黄色を目指します。大学在学中になれればいいかなと思っています。今後も精進頑張ります。
その他
竸プロとは関係ないんですが、最近SIGNATEやKaggleを始めました。現在勉強中です。
AtCoderで水色になりました
ysystemです。AtCoderでついに水色になりました！！！嬉しいです！！！
色変記事書きます！
精進に関して
緑から水色になるまでの僕の精進の仕方についてです。参考にしていただければ幸いです。
その１ 解説を読むようにした
緑になりたての頃までは「解説を読む、見る」ということをほとんどしていませんでした。自力で解けるまで考え、できない場合は放置してまた後でやろうというスタンスでした（当時は解説ACをあまり好ましく思っていませんでした）。しかし、これが良くなかったのです。当時は精進していても高難易度の問題は自力で解けず、なかなかAC数も増えませんでした。さすがにこの状況をどうにかしなければならないと思い、どうしてもわからない問題については解説を読むようにしました。解説を読んで新たな知識・考え方を増やそうということです。この実践はかなり効果的でした。新たな知識・考え方が徐々に増えていき、コンテスト中に緑・水diffの問題が解けるようになったり、水Perfが出せるようになりました。
その２ Codeforces div3バチャについて
緑後半になってからCodeforcesのdiv3バチャを多くやるようにしました。それ以前もdiv3バチャを何回かやったことはありましたが、当時は解ける問題があまり多くなく、積極的にバチャをやることはあまりありませんでした。緑後半になって実力もある程度ついてきただろうと感じたので、取り入れることにしました。目的は主に二つです。
コンテスト本番に近い状況で問題を解く
僕はそれ以前バチャ自体をやることがほとんどなく、時間制限を設けて問題を解くということはあまりしていませんでした（竸プロerにとってバチャは必要なことだと思いますが...）。冷えたときに、時間制約内での練習が足りない、と感じたため、バチャをやるようにしました。
数学的思考力の増強
Codeforcesの問題は数学的思考力を要するものが多いと自分では認識しています。数学問題に強くなりたいという考えがありました。
Codeforcesで青になった
コドフォでも色変しました。div3バチャをたくさんやったのが良かったと思います。
その他学習記録
使えるようになったアルゴリズムやデータ構造を紹介します。水色になってから学ぶのでもよさそうなものに関しては*マークをつけておきます。
AtCoder Beginner Contest 157 参加記
D - Friend Suggestions 解説
問題文が長いですね。結論から言うとこの問題はグラフ問題に帰着できます。今回はUnionFind（以下UF）というデータ構造を使います。グラフやUFについての基本的な内容は他の記事を参照してください。
考察
まず友達関係に関するグラフを作ります。人を、番号
のついた頂点とみなします。求めたいものは、各
について、頂点
と同じ連結成分に属する頂点のうち、頂点
に隣接せず、かつ頂点
とブロック関係にないものの個数です。図解すると以下のようになります。✔️のついた頂点のうち、ブロック関係にないものの個数を求めます。
実装
まずUFと、頂点の次数を管理するvectorを宣言します。また、vector
set[i]:=頂点に隣接する頂点の集合
UnionFind tree(n);
vector<int> deg(n);//頂点の次数
vector<set<int>> st(n);
for(int i=0;i<m;i++){
a[i]--;b[i]--;
deg[a[i]]++;
deg[b[i]]++;
st[a[i]].insert(b[i]);
st[b[i]].insert(a[i]);
tree.unite(a[i],b[i]);
}次に、頂点と同じ連結成分に属する頂点のうち、頂点
と友達関係になく（に隣接せず）、かつブロック関係にあるものの個数を求めます。そのためのvectorを宣言し、
で初期化します。UFのsame機能を使うことにより、二つの頂点が同じ連結成分に属するかどうかを判定できます。
u[i]:=頂点と同じ連結成分に属する頂点のうち、頂点
に隣接せず、かつブロック関係にあるものの個数
vector<int> u(n,0);
for(int i=0;i<k;i++){
c[i]--;d[i]--;
if(tree.same(c[i],d[i])){
if(!st[c[i]].count(d[i])) u[c[i]]++;
if(!st[d[i]].count(c[i])) u[d[i]]++;
}
}最後に、各について、頂点
と同じ連結成分に属する頂点の個数から、頂点
に隣接する頂点の個数と、上記のu[i]と、
（
自身）を除けばよいです。
for(int i=0;i<n;i++){
cout << tree.size(i)-deg[i]-u[i]-1 << ' ';
}
その他、精進記録など
3/1時点で以下のような感じです。
TopCoder 0
CodeForces 60
AtCoder 396
AOJ 17
yukicoder 0
Sum 473
もう少しでレート4桁です。遅くとも5月には水色になりたいです。
ABC 153-E
問題見てしばらくしてdpというのは分かった。しかしコードを書き上げてもなかなかバグが取れない。
for(int i=h;i>=0;i--){
for(int j=0;j<n;j++){
}
}
という二重ループを回し、
dp[i][j]:現在モンスターの体力がiで、魔法jを使おうとしてるときに、今までに消費した魔力の合計の最小値
と考えたが、遷移の際にdpテーブルに魔力の情報は必要ない(むしろバグる)と分かったので、以下のように書き換えた。
dp[i]:現在のモンスターの体力がiのときに今まで消費した魔力の合計の最小値
ただしモンスターの体力がその値を取りうるかどうかを確認しなければならないので注意が必要。
今までは、もう少しで解けそうだったり凡ミスでAC逃したりパフォは出たけど早解きだったりショートカット知らなかったりと、思わしくない内容ばっかりだったけど今回は自分の中で総合的に見て1番よかったんじゃないかな
— ysystem (@ysystem7) 2020年1月26日
緑になりました
AtCoderで緑になりました。色変記事ですが書くことがあまり見当たりません（笑）。ですが今回は今までに学んだアルゴリズム等を列挙していこうと思います。
少しでもいいから使えるようになったもの
・BFS
・DFS
・二分探索
・累積和
・Unionfind
・尺取り法
・bit全探索
・セグ木 等
一度学んだけどまだ理解できてないもの
・ベルマンフォード
・ワーシャルフロイド 等
今後強化していきたい分野
・グラフ、木の問題
・DP
まだ学んでない分野もたくさんあるのでそれらも学習していきます。あとは純粋に数学力を身に付けたいですね（切実）。
現時点で288AC（CF、AOJ含む）なのでもっと精進しなきゃと思います。
水色に向かって頑張るぞ！
2019年を振り返って～競プロ編～
昨日のAGC041で2完して水パフォを出し、highestを更新しました 緑が見えてきましたが、本日のABCには参加できないので年明けにでもなりたいです ARC級が2つあるのでそのあたりで
アルゴリズム実技検定受験記
有効期限が2年ということもあり、受験するか迷いましたが、力試しにと思い受けてみることにしました
認定級は初級 茶コーダーにしては頑張った方かと 解けた問題はA-B-C-D-F-Gで、合計点は45点でした 解けて嬉しかったのはGですね その週に勉強した成果が出たので
G 組み分け/Division
ABC147-Cでbit全探索の問題が出ました 当時はそんなことを知らなかったのでもちろん解けず... その後勉強して無事AC 類題も解いてみて書き方は徐々に分かっていきました
このGはbit全探索を応用して解きました グループが3つ以下なので、組み分けを三進法表記したとき各ビットの数字が同じ人同士で同じグループに入ればよい、と考えました あとは各ペアを見ていってで解けると思います グループを区別していますが今回は特に問題ないです
また2年以上後に受験しようと思います その時にはもっとレベルアップして臨みたいですね
AGC041
＜以前の記録＞
AGC038:nosub撤退
AGC039:1完緑パフォ +113
AGC040:0完 -9
参加前は本当に不安でしかありませんでした ですが
＜今回＞
AGC041:2完水パフォ +153
見事大勝利 ですが...
Ctrl CするはずがCtrl VしてしかもCtrl Sしてたから書き直すはめに... 20分くらいロスしました
— ysystem (@ysystem7) 2019年12月28日
もっとパソコン強くなろうと思いました
B Voting Judges
僕の解法です（長いです（笑））
数列をソートします（以下0-indexedとする） 上のような図を考えます 投票の際は各
に対してブロックを積み上げていくイメージです 各
に積み上げられるブロック数の最大値は
です
から
の
個の問題は確実に採用されます あとは
から
をすべて見ていきます
とします
について
(a) のとき
から
にそれぞれ
個のブロックを積み重ね、
となれば
は採用されます
(b) そうでないとき
から
にそれぞれ
個のブロックを積み重ねます 残った
個のブロックの山（山の高さ
）をどこに積み重ねるかを考えます
(b-1) のとき
と
の大小関係が分かれば十分なので、
から
のいずれか
個にブロックの山を積み重ね、
となれば
は採用されます
(b-2) そうでないとき（のとき）
まず、から
までそれぞれブロックの山を積み重ねます そうすると
個のブロックの山が残ります 次に、
から
までそれぞれブロックの山を積み重ねます そうすると上図のように
より大きくなる部分（緑斜線部）ができます これを赤斜線部に移動させることを考えます（このときブロックの山の形は変えてOK） 赤斜線部に収まれば
は採用されます
2019年を振り返って
競プロ活動はまだ三か月ほどですが、今年を振り返っていこうと思います
灰色の時期
正直言ってつらかったです AGCで1回うまくいったことはありましたが、ほかの回ではレート微増程度 なかなか伸びないなあと 早く色が付いてほしいという気持ちでいっぱいでした 特につらかったのはオーバーフローでACできなかったこと これが2回連続で続いたときはメンタル相当やられました それでもコンテストには毎回参加していました
茶色になってから
色変してからの伸びは灰色の時とは比べ物にならないと思います コンテスト中に茶diff後半の問題が解けるようになり、茶パフォ以上は安定してきました 考え方も以前に比べればだいぶ身についてきたのではないかと思います コドフォに参加してたのもよかったかもしれません 基本は深夜開催ですが、出られるときにはなるべく出ていました
まだ緑にはなっていませんが、緑になってからは今まで以上に精進が必要になってくると思います まずはB1のうちに緑になり、そこからさらに精進していこうと思います
それではよいお年を
