AtCoder黄色になりました
raoZです。初めて色変ブログを書きます。
解いた問題数など
写真はAtCoder ProblemsとAtCoder Scoresです。図の通り、ABCは殆ど全埋め、ARCはCまで黄diff以下全埋め、AGCも黄diff以下ほぼ全埋めという感じで精進しました。他のコンテンツとしては、PASTとEDPCを全て埋めてます。AtCoder以外はほとんどやっていません(コドフォはコンテスト参加分だけ消化してます)。
時系列を追って振り返りたいところですが、正直水色前の精進はあんまり覚えていないので青->黄に焦点を絞ります。
1600->1900:
春休み+コロナ禍で無限に精進しました。ABC-FとARC-C埋めで一気に実力が伸びた感覚があり、2~3ヶ月くらいであまり苦労せず達成しました。
1900->2000:
丁度このころ黄溜まりが解消されてレートが上がりにくくなった+院試*研究でキャパが吸われたのでかなりしんどかったです。半年くらい1900付近をフラフラして今に至ります。ここでやったのは、橙diff問をチョット埋める+PAST埋めくらいでしょうか。
精進について
- 高難易度を攻めるか低難易度埋めをするか
僕は低難易度から埋めていく派ですが、これをやると確実にパフォは安定します(易問を早く正確に通せるようになるので)。どうせすぐ終わるなら低難易度も埋めちゃいませんか？
- バチャについて
僕はバチャで解くよりは気ままに問題を1問1問解くほうが性に合っていて、バチャは殆どやってないです。強いバチャ勢の方も多いので、やったほうがいいのかもしれません。
- 解説ACをするか
これは結構意見が分かれるところですが、僕はある程度考えたら解説を見ています。ただし、人の記憶は信用ならないので、ある程度考察過程をノートに文字起こししてからです。解説を読んで思考回路を矯正します。公式解説は発想部分に踏み込んでくれないものも多いため、ググって有志の解説を読むことも多いです。
理想を言うと全問題解説を見たくはないのですが、頭の中に問題を残して生活すると競プロ以外ポンコツになるのでやめました(両立できる人、すごい)。
その他
橙は遠すぎて見えないので、次の目標はレート2200にします。オンサイト行ってみたいなあ
小説家になろうおすすめ作品まとめ(2020/10/30)
自称なろうマスターが、小説家になろうのオススメ作品を紹介していく記事。
(便宜上星の数でオススメ度を表しますが、もちろんどれもオススメ)
⭐️10
俺TUEEEならぬ少女TUEEE。シェラ様万歳！
短編小説。美術鑑賞がしたくなる
元なろう1位。とりあえず読もうな
戦記、英雄モノっていいよね。主人公が格好いい
七つの大罪っていいよね(厨二)。好きです。
人外転生×戦記×神話。素材だけで美味しい。もちろん料理もうまい
VRMMO×SCP。とにかく描くのが上手
叙述トリック × ゲーム転移 タネを予想して読むと楽しい
現なろう1位。人外転生楽しい
ネット小説の枠からはみ出てしまった作品。後にも先にもこんな作品に出会ったことはない(褒め言葉)
家の納屋にダンジョンがある ―God in the abyss of despair―
戦闘描写が熱い。
下品だけど、めちゃんこ熱い。燃える
成り上がりっていいよね
ダークファンタジー。名作
フィル・ガーデン。天才の物語
Tamer's Mythologyと同じ作者さん。好きです
一話一話が重厚。立身出世っていいよね
皆知ってるあの作品。伏線考察で何周もできる
⭐️9
中二病はいつまでも
ここで力つきました。気が向いたら⭐️9以下加筆していきます
キーエンスプログラミングコンテスト2019-E Connecting Cities
お久しぶりです．今回は日本語でのブルーフカ法によるConnecting Citiesの解説が見当たらなかったので筆を取りました．たくさんの解法がある(けんちょんさんblog参照)ので色々検討すると面白いと思います．
[問題]
[前提知識]ブルーフカ法とは
ブルーフカ法 - Wikipedia 参照．簡単に言えば全頂点からのプリム法．計算量はO(E logV)．
[考察]
辺を貪欲に張っていくことを考える．すると重要な考察として，以下の左図のように辺が交差する辺の張り方は，右図のように交差しないように張り替えた方がより効率が良いことがわかる．
この事実から，全ての頂点から最小コストの辺を張ると(すなわちブルーフカ法の1周目を行うと)，連結しているものは全て連続区間であることが導かれる．
更に，連続区間もまた頂点と同様に考えられるので連続区間同士でまた最小コストの辺を結ぶ...という操作を繰り返すと自然と最小全域木(MST)が得られる．これは上で触れたブルーフカ法に他ならない．
ここで重要なのは，連結成分が連続区間なので，左右それぞれについて最小コストの辺はSegment Tree, Sparse TableなどによってO(log N)で求められるということである．
以上の考察により，MSTはO(N(logN)^2)で得られる.
[実装]
連結判定をUnionFind,辺選択をSparseTableで行った．以下実装リンク
Submission #15311792 - KEYENCE Programming Contest 2019
[参考]
キーエンス プログラミング コンテスト 2019 E - Connecting Cities (600 点) - けんちょんの競プロ精進記録
ABC099D Good Grid
問題概要
N行N列のグリッドを色1~Cで塗り分け、(i,j)を最初c_i,jで塗っている。(i+j)%3 = (x + y)%3ならば(i,j)の色は同じ、そうでなければ異なるように塗り替える。X→Yの色に変えた時、そのマスに対して感じる違和感をD_x,yとする。この違和感の和の取りうる最小値を求めよ。
制約
- 1 <= N <= 500
- 3 <= C <= 30
- 1 <= D_i,j(i!=j) <= 1000
方針・所感
設定が小難しくて問題文を読んでから飲み込むのに時間がかかる。
方針としては2つある。
1つ目は、mod3でマス目をグループ分けすることさえ考えれば、各グループ(O(3))の元の色(C)が何個ずつあるか分かってしまえばあとは色の変化パターンを全探索O(C^3)して十分間に合いそうだ。 (公式解説と同じ)
もう一つは、事前にmod3で分けられるマスごとに、事前に色をある色cに変えた時の違和感をO(N^2C)で求めてしまえば、あとは色の塗り方をO(C^3)で求められ、全体として計算量はO(N^2C + C^3)となりこれでも間に合う。以下の実装はこの方針である。
細かいところ・デバッグの記録など
- 制約によって前者・後者の解法が生きたり死んだりするので問題設定に注意したい。
実装
#include <bits/stdc++.h>
#define rep(i, N) for(int i = 0; i < N; i++)
#define FOR(i, a, b) for(int i = a; i < b; i++)
using namespace std;
const int INF = 1e9;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
int main(){
int N, C; cin >> N >> C;
unordered_map<int,int> MP[3]; // (i+j)%3が同じものについて、色kに変えた時の違和感の和
FOR(i,1,C+1) FOR(j, 1, C + 1) cin >> D[i][j];
rep(i, N) rep(j, N) cin >> c[i][j];
rep(i, N) rep(j, N) FOR(k, 1, C+1){
MP[(i + j) % 3][k] += D[c[i][j]][k];
}
int ans = INF;
FOR(c1, 1, C+1) FOR(c2, 1, C+1) FOR(c3, 1, C+1){
if(c1 == c2 || c2 == c3 || c3 == c1) continue;
int tmp = 0;
tmp += MP[0][c1] + MP[1][c2] + MP[2][c3];
chmin(ans, tmp);
}
cout << ans << endl;
}
ABC100D Patisserie ABC
問題概要
N種類のケーキはそれぞれ綺麗さx、美味しさy、人気度zのパラメタを持つ。りんごさんはこのケーキをM個違う種類から選ぶことにした。この時、|xの和|+|yの和|+|zの和|の最大値を求めよ。
制約
- 1 <= N <= 1000
- -1e10 <= x,y,z<= 1e10
方針・所感
一見すると綺麗さ美味しさ人気度が高い順に選んでいけば貪欲に求められるように見えるが、絶対値を取っているのでどっち方向にいいものを選べばいいかわからないのでここに一工夫がいる。絶対値は正数と負数に場合分けを発生させるものなので、ここを場合分けして、x,y,zの和をそれぞれの正負で場合分けして、合計を求めてしまえばあとは2^3 = 8つの場合それぞれについて貪欲にM個ケーキを選んでしまえば最大値が求まってしまう。
細かいところ・デバッグの記録など
- 最初それぞれのパラメタについてソートして場合分けすればいいかと思ったが嘘だった。
実装
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i = 0; i < n; i++)
typedef long long ll;
int main(){
ll N, M; cin >> N >> M;
// P[i][j] := iは-1を綺麗さ・美味しさ・人気度にそれぞれかけるかどうかをbit管理
// jは何個目かを表し綺麗さ・美味しさ・人気度の合計をもつ
//入力+データ整理
rep(i,N){
ll x, y, z;
cin >> x >> y >> z;
rep(j,1 << 3){
ll t[3] = {x, y, z};
rep(k, 3){
if(j & 1 << k){
t[k] *= -1;
}
}
P[j][i] = t[0] + t[1] + t[2];
}
}
rep(i, 8){
sort(P[i].begin(), P[i].end(), greater<ll>());
}
ll SUM[8] = {0};
rep(i, 8){
SUM[i] = 0;
rep(j, M) SUM[i] += P[i][j];
}
cout << *max_element(SUM, SUM + 8) << endl;
}
ABC104D_WeLoveABC
問題概要
文字列TのABC数をT[i]=A, T[j] = B, T[k] = Cとできるi,j,k(i < j < k)の個数と定め,?にはA,B,Cのいずれかの文字で置換出来、そのような文字列全てのABC数の和を求めよ。
制約
- 3 <= |S| <= 1e5
- Sは'A','B','C','?'で構成される
方針・所感
前から順番に決まって行きそうだしdpかな〜と観察していると、前から順番に見ていって、まだ何も選んでない状態、Aを選んだ状態、ABを選んだ状態、ABCを選んだ状態の数が求まりそうなことがわかる。あとはそれらの遷移を漸化式としてdpテーブルを埋めていけば良い。ここで、?があると場合の数が3倍になる(例えば"ABC?"だと、?はABCを作ることに関与しないがABCA,ABCB,ABCCの3つの文字列が作成可能になる)ことに注意して実装すれば良い。
細かいところ・デバッグの記録など
- 上で説明したように場合の数が3倍になることに気付かず、実装が爆散した。
実装
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
template<int MOD> struct ModInt {
static const int Mod = MOD; unsigned x; ModInt() : x(0) { }
ModInt(signed sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; }
ModInt(signed long long sig) { x = sig < 0 ? sig % MOD + MOD : sig % MOD; }
int get() const { return (int)x; }
ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
ModInt &operator/=(ModInt that) { return *this *= that.inverse(); }
ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
ModInt operator/(ModInt that) const { return ModInt(*this) /= that; }
ModInt inverse() const { long long a = x, b = MOD, u = 1, v = 0;
while (b) { long long t = a / b; a -= t * b; std::swap(a, b); u -= t * v; std::swap(u, v); }
return ModInt(u); }
bool operator==(ModInt that) const { return x == that.x; }
bool operator!=(ModInt that) const { return x != that.x; }
ModInt operator-() const { ModInt t; t.x = x == 0 ? 0 : Mod - x; return t; }
};
template<int MOD> ostream& operator<<(ostream& st, const ModInt<MOD> a) { st << a.get(); return st; };
template<int MOD> ModInt<MOD> operator^(ModInt<MOD> a, unsigned long long k) {
ModInt<MOD> r = 1; while (k) { if (k & 1) r *= a; a *= a; k >>= 1; } return r; }
typedef ModInt<1000000007> mint;
const int MAX_N = 1e5;
int main(){
string S; cin >> S;
mint dp[MAX_N+1][4]; // dp[i][j] := i番目の文字まででの、j(A,AB,ABC)が作れる数
int N = S.size();
dp[0][0] = 1;
rep(i, 1, N + 1){
if(S[i-1] == '?') rep(j, 0, 4) dp[i][j] = (mint)3 * dp[i-1][j];
else rep(j, 0, 4) dp[i][j] = dp[i-1][j];
if(S[i-1] == 'A') dp[i][1] += dp[i-1][0];
else if(S[i-1] == 'B') dp[i][2] += dp[i-1][1];
else if(S[i-1] == 'C') dp[i][3] += dp[i-1][2];
else if(S[i-1] == '?'){
dp[i][1] += dp[i-1][0];
dp[i][2] += dp[i-1][1];
dp[i][3] += dp[i-1][2];
}
}
cout << dp[N][3] << endl;
}
ABC105-D Candy Distribution
問題概要
N個の箱が左右一列に並んでいて、左からi番目の箱にはAi個のお菓子が入っている。連続した箱[l,r]からM人の子供に平等に配れるようにMの倍数個取り出したい時、l,rの選び方の総数を求めよ。
制約
- 1 <= N <= 1e5
- 1 <= M , Ai<= 1e9
方針・所感
愚直にやるとN個の累積和をとって全てのl,rの組について条件を満たすか判定する、という解法が思い浮かぶがO(N^2)となり、ギリギリ間に合わない。なので、高速化する方法を考えるわけだが、modMで考えて累積和が等しいものがあるならその区間の和はMの倍数となり、modMが等しいものの個数はO(N)で求められる。あとは、その個数xの中からxC2で(l,r)の組を選べば良いので、全体としてはO(N+N)で求められる。
細かいところ・デバッグの記録など
- 累積和を取る時は1-indexedにすると実装が描きやすい
- 例によってlong longにしなかったせいでxC2がオーバーフローしてしまった、注意
- 累積和にmintを使いたかったが、mod入力で与えられる場合は別のクラスを定義しなければならないようなので断念
実装
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for(int i = a; i < b; i++)
typedef long long ll;
int main(){
ll N, M; cin >> N >> M;
rep(i, 1, N + 1) cin >> A[i];
rep(i, 1, N + 1) SUM[i] = SUM[i-1] + A[i];
map<int, ll> MP;
rep(i, 0, N + 1) MP[SUM[i] % M]++;
ll ans = 0;
for(auto e: MP){
ans += e.second * (e.second-1) / 2;
}
cout << ans << endl;
}
