本棚を購入しました。家が広くなりました。全人類本棚を買ってください。
本棚のリンクです。
作りはかなりしっかりしていて、組み立てるのも2人必要かもしれませんが楽しくできました。
就活は大変でした。3月くらいから某ロナで面接がオンラインに移行して、戸惑いもありました。最終面接がオンラインだと、家なのにスーツを着て、重圧があり、変な感覚になります。内定が決まったときは泣きました。
競プロ的には、AtCoderでレートを200くらい上げたこと、マラソン形式に楽しく取り組めたことに満足しています。
マラソンは楽しいです。普段アルゴでは絶対に戦えないようなレベルの人たちと同じページの順位表に乗れる可能性があるというだけでワクワクしますし、評価関数を決めたり、計算量を操ったりするのも自由度が高く面白いです。問題が違っても、上位層の使っている手法が意外と共通であることに気づいてからは、自分の知ってる手法に落とし込むために問題の言い換えを考える時間も好きになりました。自明な貪欲を組んだあと、ビームを打ったら劇的に改善される瞬間は最高です。みんなもやろう、マラソンマッチ。人生とのバランスは考えた方がいい気はしますが。
来年度からは業務erになる予定ですが、マラソン、特にハル研プロコンのおかげで開発っぽいことに触れることができて、そういうコードの構造を読み解いたり、構成を考えるのも楽しいと思えたので、この気持ちを忘れずにやっていきたいと思います。
できるならマラソンっぽい案件をやってみたいという気持ちはあるのですが、まずはソフトウェアの開発の基本からという気持ちです。そもそもマラソンっぽい仕事、日本に少ないイメージで、あっても研究者レベルの人がやっていそうです。英語ができたら可能性がありますか?
あと某感染症のせいでリモートワークが増えたわけですが、自己管理能力がないことがよくわかったので入社後もかなり不安です。リモートワークしてる先輩社会人の皆さんはどのようにモチベーションを保って勤務しているのでしょう。
2020年はイレギュラーなこともありましたが、とりあえず生きて終えられそうなのでよかったです。競プロがなかったら就職先も異なっていたことでしょうし、在宅時間を耐えることもできなかったように思います。ありがとう競技プログラミング。
2020/8/22以降のAtCoderにおけるパフォーマンスが上振れているので分析してみました。
コンテスト | 順位 | パフォ | 新Rating | 差分 | 解答 | 理由 |
---|---|---|---|---|---|---|
ABC176 | 519 | 1789 | 1371 | +58 | 緑diff 53:28 | 類題既知 |
ABC177 | 605 | 1732 | 1412 | +41 | 緑diff 23:01 | spf(高速素因数分解) |
ABC178 | 864 | 1597 | 1432 | +20 | 緑diff 34:38 | マンハッタン距離は45°回転 |
ABC179 | 1120 | 1454 | 1434 | +2 | 緑diff遅 87:21 | 周期苦手 |
ACLC1 | 332 | 1835 | 1481 | +47 | 水青diff 108:00 | 貪欲, extGCD |
ACLBC | 1285 | 1110 | 1449 | -32 | 水diff解けず | 基本的なDPができません |
ARC104 | 1270 | 1387 | 1443 | -6 | 茶diff遅 | 誤読したのと次黄diffで崖 |
HHKB2020 | 571 | 1728 | 1475 | +32 | 水diff 43:01 | 数え上げ |
ARC105 | 295 | 2038 | 1545 | +70 | 黄diff | コドフォに類題のあるゲーム |
AGC048 | 964 | 661 | 1482 | -63 | ☀️ | 😭 |
ARC106 | 891 | 1518 | 1486 | +4 | 緑diff 64:06 | 構築(区間スケ問題) |
ARC107 | 658 | 1698 | 1509 | +23 | 緑diff 36:57 | 得意めな数え上げ |
ABC181 | 366 | 1776 | 1538 | +29 | 緑diff 46:02 | 添字ガチャが得意 |
最近緑diffがABC-Eに置かれることが多く、そこまでをある程度早く解いて甘い汁を吸っているか、同レート帯と比べて得意な数え上げを確実に仕留めているだけでした!
いかがでしたか?
弾きたい曲の楽譜とギターの弦における音の下限が与えられるので、ギターの抑えるべき幅の最小値を求めよという問題。
ある区間の中に全ての音を包含するようにできるかを考えればいいが、これは尺取りでできる。
int main() { vector<int> a(6); cin >> a; int N; cin >> N; vector<int> b(N); cin >> b; vector<pair<int,int>> v; rep(i,N)rep(j,6){ v.emplace_back(b[i]-a[j], i); } sort(all(v)); int val = 0; vector<int> cnt(N, 0); int ans = INF; int M = 6 * N; for(int l = 0, r = 0; l < M; l++){ while(r < M && val < N){ int ridx = v[r].second; if(cnt[ridx] == 0)val++; cnt[ridx]++; r++; } if(val == N)chmin(ans, v[r-1].first - v[l].first); cnt[v[l].second]--; if(cnt[v[l].second] == 0)val--; } cout << ans << endl; }
オーバーフローしそうなのでpythonで。
N = int(input()) for a in range(60): if a == 0: continue rem = N - pow(3, a) if rem < 0: break for b in range(60): if b == 0: continue if rem == pow(5, b): print(a, b) exit() print(-1)
連結成分の和が同じなら達成できます。dfsとかunion findでも実装できます。ac-libraryのdsuはgroupsというのがあるらしいのでそれが一番楽そうです。
vvec<int> G; vector<ll> a, b; vector<ll> used; void dfs(int cur, int pre, vector<int>&v){ used[cur] = true; v.push_back(cur); for(auto nxt: G[cur]){ if(used[nxt])continue; dfs(nxt, cur, v); } } int main() { int N, M; cin >> N >> M; G.resize(N); a.resize(N); b.resize(N); used.resize(N, false); cin >> a >> b; rep(i,M){ int c, d; cin >> c >> d; c--, d--; G[c].push_back(d); G[d].push_back(c); } rep(i,N){ if(used[i])continue; vector<int> v; dfs(i, -1, v); dump(v); ll suma = 0; ll sumb = 0; for(auto x: v)suma += a[x]; for(auto x: v)sumb += b[x]; dump(suma, sumb); if(suma != sumb){ cout << "No" << endl; return 0; } } cout << "Yes" << endl; }
まず、高橋君の方は区間スケジューリング問題の最適解なので、青木君が追い越すことはできません。よってはできません。また、 or の場合もできません。は、の場合ですが、はあり得ないです。一個は取れます。また、は、かの場合ですが、前者は高橋君が全て取れるときは青木君も全て取れますし、後者は同様にはあり得ないことから、無理です。
以上の考察により、の場合のみを考えればよいです。この場合、達成可能です。 まず、クソでか区間を置くことで、青木君の結果をに固定します。このとき、高橋君の結果がになればいいので、個の区間を取れるように置きます。ここで残った個の区間は、高橋君にも青木君にも取れないように置きます。具体的には以下のようにです。
構築が完了しました。
int main() { int N, M; cin >> N >> M; if(N == 1 && M == 0){ cout << 1 << " " << 2 << endl; return 0; } if(M == N || M == N-1 || M < 0){ cout << -1 << endl; return 0; } int rem = N - M - 1; for(int i = 1; i <= M+1; i++){ cout << 2 * i+rem << " " << 2 * i+rem + 1 << endl; } for(int i = 1; i <= N-M-1; i++){ cout << i << " " << INF - i << endl; } }
ABCE青パフォでした。Dが難しかったですね・・・。
jjjjjjjtgpptmjjさんのHHKB プログラミングコンテスト 2020での成績:571位
— naga@精進 (@longeqe) 2020年10月10日
パフォーマンス:1728相当
レーティング:1443→1475 (+32) :)#AtCoder #HHKBプログラミングコンテスト2020 https://t.co/hTuwuCdLLo
if文。
int main() { char s, t; cin >> s >> t; if(s == 'Y'){ cout << char(t - 'a' + 'A') << endl; } else{ cout << t << endl; } }
ある点から右と下を見ます。
int main() { int H, W; cin >> H >> W; vector<string> S(H); cin >> S; int ans = 0; auto IsIn = [&](int i,int j) -> bool{ return 0 <= i && i < H && 0 <= j && j < W; }; rep(i,H)rep(j,W){ if(S[i][j] == '#')continue; rep(k,2){ int nx = i + dx[k]; int ny = j + dy[k]; if(not IsIn(nx, ny))continue; if(S[nx][ny] == '#')continue; ans++; } } cout << ans << endl; }
pの値がintにおさまるので、ある値が出てきたかどうかのflagを持って全て回していいです。
int main() { int N; cin >> N; vector<ll> p(N); vector<bool> used(200010, false); rep(i,N){ cin >> p[i]; } int idx = 0; rep(i,N){ used[p[i]] = true; while(used[idx]){ idx++; } cout << idx << endl; } }
これめちゃくちゃ難しいですね・・・。 公式の解説が丁寧なので追って実装しました。 特に、
あたりがすごく難しいと思いました。とにかく、言い換え、対称性などの力が求められる問題だと感じます。
#include <atcoder/modint> using mint = atcoder::modint1000000007; void solve(){ ll N, A, B; cin >> N >> A >> B; mint X4 = (N-A-B < 0) ? 0: mint(N-A-B+1) * mint(N-A-B+2) / 2; mint X3 = 2 * X4; mint X2 = (N-A+1)*(N-B+1) - X3; mint X1 = X2 * X2; mint zen1 = mint(N-A+1)*mint(N-B+1)*mint(N-A+1)*mint(N-B+1); mint ans = zen1 - X1; cout << ans.val() << endl; }
いわゆる主客転倒というものです。ある座標に注目して、その座標が照らされる条件を考え、その割り振りを考えます。
ある頂点が照らされる条件は
です。 上下左右につながっている点の個数がわかればいいので、尺取りみたいにして実装しました。 多分もっと綺麗な実装があると思いますが。
#include <atcoder/modint> using mint = atcoder::modint1000000007; int main() { int H, W; cin >> H >> W; vector<string> S(H); cin >> S; ll K = 0; rep(i,H)rep(j,W){ K += S[i][j] == '.'; } vvec<int> dh(H,vec<int>(W, 0)); vvec<int> dw(H,vec<int>(W, 0)); vvec<int> d(H,vec<int>(W, 0)); rep(i,H){ int r = 0; for(int l = 0; l < W;){ while(r < W && S[i][r] == '.'){ r++; } for(int k = l; k < r; k++){ dh[i][k] = r - l; } if(l == r){ l++; r++; } else l = r; } } rep(j,W){ int r = 0; for(int l = 0; l < H;){ while(r < H && S[r][j] == '.'){ r++; } for(int k = l; k < r; k++){ dw[k][j] = r - l; } if(l == r){ l++; r++; } else l = r; } } rep(i,H)rep(j,W)d[i][j] = dh[i][j] + dw[i][j] - 1; mint ans = 0; rep(i,H)rep(j,W){ if(S[i][j] == '#')continue; ans += (mint(2).pow(d[i][j]) - 1) * mint(2).pow(K - d[i][j]); } cout << ans.val() << endl; }
まだ見てません。
ABC3完でした。Dは冷静になりたかった。。。勉強不足です。
for文を使います。
int main() { int K; cin >> K; rep(i,K){ cout <<"ACL"; } cout << endl; }
区間の位置を固定して、真ん中が交叉してるかを考えればよいです。swapを忘れて1WA。
int main() { ll A, B, C, D; cin >> A >> B >> C >> D; if(A > C){ swap(A, C); swap(B, D); } if(C <= B){ cout << "Yes" << endl; }else{ cout << "No" << endl; } }
連結成分を一つの頂点だとみなして、連結させるには、連結成分数 - 1回です。
int main() { int N, M; cin >> N >> M; UnionFind T(N); rep(i,M){ int a, b; cin >> a >> b; a--, b--; T.unite(a, b); } cout << T.group_num() - 1 << endl; }
in-place DPというやつらしいです。値を添字に持つこと、もらうDPにすると区間になるので、セグ木で高速化できます。
以下のけんちょんさんの記事に丁寧に解説されています。LISがこれで求められるのは確かにとなりますね。
#include<atcoder/segtree> ll op(ll a, ll b){ return max(a, b); } ll e(){ return 0; } const int A_MAX = 300010; int main() { int N, K; cin >> N >> K; atcoder::segtree<int, op, e> S(A_MAX); vector<int> A(N); rep(i,N)cin >> A[i]; ll ans = 0; for(int i = 0; i < N; i++){ int l = max(0, A[i] - K); int r = min(A_MAX-1, A[i]+K+1); ll prod = S.prod(l, r); S.set(A[i], prod+1); chmax(ans, prod+1); } cout << ans << endl; }