週末報告 2025.10.19-2025.10.26
毎週末にその週継続的に取り組んでいたことの報告と次週の目標を掲示していきたいと思います。今はまだバンバン成長するよりも継続することが目的なので目標はキツ過ぎずに設定するつもりなので「楽勝だろ」とか思っても温かく見守ってください👀
振り返り
大学の仲間内での競プロモチベが9月中より上がって、10月始まってからほぼ毎回複数人でデイリーコンテストに臨めています。大学の課題とかをそこそこにこなしながら楽しくプログラミングを進めることができました！
来週の目標
構成的に来週の目標は一番下に書こうと思ったのですが、思ったより内容が膨れてしまって読みにいくのが大変になってしまいそうなので上に書いておきます。
- AtCoder Daily Training全参加
- 200代のD埋めを5問(下からやりたいけど気分で)
- EDPC計5問(E, F, G, H, I)
- NeetCode150を1日1問
- 1本は記事投稿(振り返り以外にもう1つ)
- 個人開発進める
頑張ります💪
こういう系以外で言うとジムに行くのと授業にちゃんと出るっていうのも頑張っていきます、、、
ちなみに可読性の低い私のコードの可読性を下げている部分であるマクロ達を載せておきます.
マクロ
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ld long double
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i,a,b) for(int i = (int)a; i < (int)b; i++)
#define vi vector<int >
#define vvi vector<vi >
#define vvvi vector<vvi >
#define vd vector<ld >
#define vvd vector<vd >
#define vin(A, n) vi A(n); rep(i, n) cin >> A[i];
#define vb vector <bool>
#define vvb vector <vb>
#define vc vector <char>
#define vvc vector <vc >
#define vs vector <string>
#define vvs vector <vs>
#define pii pair <int, int>
#define pq(T) priority_queue <T>
#define gpq(T) priority_queue <T, vector<T>, greater<T> >
#define so(v) sort(v.begin(), v.end());
#define rso(v) sort(v.rbegin(), v.rend());
#define rev(v) reverse(v.begin(), v.end());
#define Ans(i) cout << i << endl;
#define dev(a,b) (((a)*(b) > 0) ? ((a)+(b)-1)/(b) : ((a)+(b)+1)/(b)) // 切り上げ. 0.5で切り捨てと同値. 負の数も使える.
#define Floor(x, m) (x - MOD(x,m)) / m // 切り捨て. 負の数も使える.
#define getl(S) string S; getline(cin, S);
#define yre(chk) if(chk){Ans("Yes"); return 0;}
#define nre(chk) if(chk){Ans("No"); return 0;}
#define all(a) a.begin(),a.end()
#define MOD(a, b) (((a) % (b)) + (b)) % (b)
#define rti(i) Ans(i); return 0;
#define YN(Boolean) cout << ((Boolean) ? "Yes" : "No") << endl;
#define INF LLONG_MAX
#define MINF LLONG_MIN
#define PRINT(d) printf("%.10f\n",(double) d);
Atcoder Beginner Contest 429
参加回数ももう31回になりました。
臨場感の共有で解いた順番に書いていきたいと思います。
C - Odd One Subsequence
各数字に対して出た回数が2以上ならその中から二つ選んで他の数字の個数と掛け合わせれば良さそう.
コンビネーションとれば各数字に対して出た回数が2以上ならの議論をしなくても0かけるから良さそう.
と思い1:53で解答提出...見事
本当に悔しい.
A - Too Many Requests
まあやるだけ.
B - N - 1
まあやるだけ.
この時点で6分. Dまで解いてレート上げちゃおう！！
と思ってから何も解けませんでした、、、、
とか思って取り組み続けましたが何も為せず、こうなってくるとCのペナルティが痛いですね実質時間倍になってしまいましたし。。
来週こそ4完します！
LeetCode Weekly Contest473
初めてLeetCode Weekly Contestに参加しました！ 開始時間を勘違いしていてお風呂に入っていたので30分遅れで参加しました。
Q1. Remove Zeros in Decimal Representation©leetcode
10進数の0の桁を詰めて返す問題. ←この通りにやるだけ.
class Solution {
public:
long long removeZeros(long long n) {
vector<long long>digit;
while(n){
if(n%10!=0){
digit.push_back(n%10);
}
n/=10;
}
long long ans=0,pw=1;
for(int i=0;i<digit.size();i++){
ans+=digit[i]*pw;
pw*=10;
}
return ans;
}
};
Q2. Maximum Alternating Sum of Squares
配列を並び替えてscore = arr[0]^2 - arr[1]^2 + arr[2]^2 - arr[3]^2 + ...を最大化する問題. 二乗が大きい項を+に, 小さい項を-に割り当てると解ける. -1倍したけど二乗して格納しちゃえば楽だったかな. どこかで似た問題を解いた記憶がある.
class Solution {
public:
long long maxAlternatingSum(vector<int>& nums) {
int n=nums.size();
for(int i=0;i<n;i++){
if(nums[i]<0){
nums[i]*=-1;
}
}
sort(nums.begin(),nums.end());
long long ans=0;
int l=0,r=n-1;
while(l<=r){
if(l!=r){
ans-=nums[l]*nums[l];
}
ans+=nums[r]*nums[r];
l++;r--;
}
return ans;
}
};
AtCoder Daily Training
これからはなるべく毎回デイリーコンテストに参加していきたいと思います。
2025/10/21(Tue)
E - Standing On The Shoulders
これは一番上の巨人以外は足から肩までの高さが加算され, 一番上の巨人だけ頭の高さまで加算されるので最後の巨人のみしか方から頭までの高さが参照されないことを考慮して, それが一番大きいやつを一番上に選ぶ.
(一番肩から頭までが高いやつ)+(全員の足から肩の高さの総和)が答え. ソートすれば解ける.
F - Dice Sum
dp[i][j]:
と定義することで
全ての
for(int l = 1; l <= M; l++){
if(j + l <= k){
dp[i + 1][j + l] += dp[i][j];
dp[i + 1][j + l] %= 998244353;
}
}
で配っていく.
G - LR insertion
dequeでやろうと考えたけど上手い実装が思いつかなかったので(数が大きい順に挿入していけば一回前に入れた要素は先頭か末尾に入るのでdequeの性質が使える), Linked List的な考え方を使った.
弱すぎてデータ構造があることを知りませんでした。勉強します。
map<int,pair<int,int>>Link;
で, keyの値に対して{前の数字, 後ろの数字}を持たせて頑張って実装した.
とか言ってGは実装が間に合いませんでした。
2025/10/22(Wed)
E - Shapes
#が出てきた一番大きい/小さい行/列をそれぞれ覚えておいて#を全て覆う最小の長方形を構成し直してそれらを回転させて一致するかを確認する.
F - Sowing Stones
-
X_1 - それ以降は
X_i X_{i+1}(=L)
a.A_i
b. それ以外はL
\sum_{i=1}^L-1{i}=\frac {1}{2}L(L-1)
で, 残りのA_i-L
L(A_i-L)
となり, その分をA_{i+1}
わけではなくて
入力が昇順とは限らないので最初に
0. 入力を昇順に並び替える
↑↑これが必要です. 一緒にデイリーやった友達と2人とも気付けずに沼って解ききれませんでした泣泣
2025/10/23(Thu)
E - Max MEX
長さKの数列のMEXの値はmaxでKだからK以上の要素は考えなくていい. 取り出す順番にも依存していないからK未満の要素をsetに入れていってあとは下から一つずつあるかどうか確かめる.
F - Yamanote Line Game
同じくsetに使ってない数字を格納しておいて, 使う/使われたら減らしていってその時点での最小を出力し続ければOK.
G - "redocta".swap(i,i+1)
バブルソートの比較回数だから転倒数を数える問題.
"atcoder"の語順を正しいものとして0,1,2,...6と順番を振って転倒数を数える. 転倒数については気が向いたら記事を書きます.
H - Addition and Multiplication 2
どれだけ99999と並べても100000みたいな桁の強さには勝てないのでまずは桁を最大化する.
77777777
97777777
99777777
99877777
...
みたいなイメージ
I - Two Spanning Trees
しれっと最終問題まで来れて嬉しい！
この問題は解ききれてないし、解答も見ていないので今から書くことはただの考察なのですが、、、
T1: 1を含む閉路があれば1を含む辺を削除する. (閉路あたり一つ残して)
T2: 1を含む閉路があれば1を含まない辺を1つ削除する.
という方針で解けそう.
幅でやったけど深さでやった方が簡単そう.
1にたどり着く時に
- T1はその最後にたどった辺を,
- T2はその時にいた場所の一個前とを結ぶ辺を,
削除すれば良さそう.
一個前にいた辺も保持したままDFSをしたらいけそうだから時間がある時に実装して試してみます。
200代のD埋め
気分で進めていたABC200代のC埋めが先週ついに終わったので今週からD埋めを開始しました. 今回は気分で埋めていくのではなくて下からちゃんと埋めていこうと思います.
ABC200 D - Happy Birthday! 2
dpで作れる和を保存していってそうなるvectorを入れてく
っていうのが最初の方針.
ミス 4次元dp
vvvvi(i,vvvi(j)): iまで見て, 和がmod200でjになるような,
添え字の配列の配列.
示すの二つ分だけでいいからこんなに次元いらないね. vvviで行ける.
保有するベクトルは1つ分で十分 (2つ目は今からできるし3つは要らない)
dp[i][j]: iまで見て和がjになるような添字を集めたvectorの一例
// なんなら一個前しか参照しないからもう一次元減らせる.
- もし, a[i]を入れようとするところにすでにその和になるものがあればそれとa[i]を出力する.
- そうでなければすでにあるdp[i-1][j]の末尾にiをくっつけたベクトルをdp[i-1][(j+a[i])%200]に格納できる.
- あとは1. のようにすでにあったら出力なければそのまま突っ込むを繰り返す.
模範解答(とそれへの感想)
-
鳩の巣全探索
適当にa[i]を8個選んでbit全探索したら255通りできて, 余り200個に配分したら必ず被りが発生する. だから7個以下の時に気を付けてbit全探索でやればO(1)
https://atcoder.jp/contests/abc200/editorial/1246 -
DP(個数のみを保持)
頂点倍化で1個前の添字を保持する. (max2つ)
個数が2になったら2通りで戻る.
https://blog.hamayanhamayan.com/entry/2021/05/08/233613 -
なんか賢そう(わからん)
https://kanpurin.hatenablog.com/entry/2021/05/09/042413
void solve(vi a,vi b){
Ans("Yes");
cout<<a.size()<<" ";
rep(i,a.size()){
cout<<a[i]<<" ";
}
Ans("");
cout<<b.size()<<" ";
rep(i,b.size()){
cout<<b[i]<<" ";
}
Ans("")
return;
}
signed main(){
// dpで作れる和を保存していってそうなるvectorを入れてく?
// vvvvi(i,vvvi(j)): iまで見て和がmod200でjになるような添え字のvector.
// 示すの1組でいいから, こんなに次元いらないわ. vvviで行ける.
// なんなら一個前しか参照しないからもう一次元減らせる.
int n;cin>>n;
vi a(n);
rep(i,n){
cin>>a[i];
a[i]%=200;
}
vvvi dp(n,vvi(200));
dp[0][a[0]].push_back({1});
repi(i,1,n){
dp[i]=dp[i-1];
if(dp[i-1][a[i]].size()){
solve(dp[i-1][a[i]],{i+1});
return 0;
}
dp[i][a[i]].push_back({i+1});
rep(j,200){
if(dp[i-1][j].size()){
if(dp[i][MOD(j+a[i],200)].size()){
vi tmp=dp[i-1][j];
tmp.push_back(i+1);
solve(dp[i][MOD(j+a[i],200)],tmp);
return 0;
}else{
dp[i][MOD(j+a[i],200)]=dp[i-1][j];
dp[i][MOD(j+a[i],200)].push_back(i+1);
}
}
}
}
nre(1);
}
ABC201 D - Game in Momotetsu World
- ある場所への最短経路は→, ↓の並び替えだから経路に依らずに移動回数が固定されているため, 高橋が来るか青木が来るか確定できる. (敬称略)
a. 縦横の移動回数に依存するからi+jのmod2だから判定できる - ある場所からの移動は右か下なので, ある場所へ行けるのはその左か上のみ.
- つまり最終地点での点差(高橋-青木)を0に固定したときに逆に上に左に戻っていく. 青木の点を0に固定している→dp[0][0]が高橋の点数
- ある場所に来る時、(高橋か青木)-(+か-)で4通りあるが、青木基準だから青木+と高橋-が青木利、相対値が+1される.
- これを頑張って実装する
まだちゃんと学習してないけどゲームdp好き. 後ろから作ってく.
signed main(){
// 右下から周を一層ずつ増やしていくdpで最適を判定.
// どっちのターンかを判定するのと,
int h,w;cin>>h>>w;
vs s(h);
rep(i,h){
cin>>s[i];
}
vvi dp(h,vi(w,0));
dp[h-1][w-1]=0;
for(int i=h-2;i>=0;i--){
dp[i][w-1]=dp[i+1][w-1]+pow(-1,(i+w+1+(s[i+1][w-1]=='-'))%2);
// 高橋のターンかつ+の時に高橋の得点を+1.
}
for(int i=w-2;i>=0;i--){
dp[h-1][i]=dp[h-1][i+1]+pow(-1,(i+h+1+(s[h-1][i+1]=='-'))%2);
}
for(int i=h-2;i>=0;i--){
for(int j=w-2;j>=0;j--){
if((i+j)%2){
dp[i][j]=min(dp[i+1][j]+pow(-1,(i+j+(s[i+1][j]=='-'))%2),dp[i][j+1]+pow(-1,i+j+(s[i][j+1]=='-')));
// Ans("1: "<<i<<" "<<j<<" "<<dp[i][j])
}else{
dp[i][j]=max(dp[i+1][j]+pow(-1,(i+j+(s[i+1][j]=='-'))%2),dp[i][j+1]+pow(-1,i+j+(s[i][j+1]=='-')));
// Ans("2: "<<i<<" "<<j<<" "<<dp[i][j])
}
}
}
// Ans("")
// rep(i,h){
// rep(j,w){
// cout<<dp[i][j]<<" ";
// }
// Ans("")
// }
if(dp[0][0]<dp[h-1][w-1]){
Ans("Aoki");
}else if(dp[0][0]>dp[h-1][w-1]){
Ans("Takahashi");
}else{
Ans("Draw");
}
}
ABC221 D - Online games
202Dの解き方が思いつかずに200代の問題をふらふら探してたどり着きました.
こっちもわからずに方針だけと答えを覗いてみて解きました.
- 累積和の取る部分を入り日を+1, 出る日を-1と振り当てて実装する.
- 間の全部追ってたら時間かかるどうでも良い部分は人数変動がないので一気に足し合わせる.
まじで賢い. もっと強くなりたい.
signed main(){
int n;cin>>n;
vector<pii>delta;
rep(i,n){
int a,b;cin>>a>>b;
delta.push_back({a,1});
delta.push_back({a+b,-1});
}
so(delta);
int cnt=0;
vi ans(n+1);
rep(i,2*n-1){
cnt+=delta[i].second;
ans[cnt]+=delta[i+1].first-delta[i].first;
}
rep(i,n){
cout<<ans[i+1]<<" ";
}
Ans("")
}
ABC274 D - LRUD Instructions
壁に当たるか進める距離がなくなるまである方向に進み続ける問題.
1-indexで各r,cについてそこにある壁をsetで管理する.(0,r/cの外周も壁判定)
であとはlower_boundで移動方向の一番近い壁を探して移動距離と比較する. 場合分けしたあとで共通化できない処理が多くて面倒だった.
signed main(){
int h,w,rs,cs,n;cin>>h>>w>>rs>>cs>>n;
map<int,set<int>>wallr,wallc;
rep(i,n){
int r,c;cin>>r>>c;
wallr[r].insert(c);
wallc[c].insert(r);
wallr[r].insert(0);
wallr[r].insert(w+1);
wallc[c].insert(0);
wallc[c].insert(h+1);
}
int q;cin>>q;
map<char,pii>dir;
while(q--){
char d;int l;cin>>d>>l;
if(d=='D'){
int wall=h+1;
if(wallc[cs].size()){
wall=*wallc[cs].lower_bound(rs)-1;
}
rs=min({wall,rs+l,h});
}else if(d=='U'){
int wall=-1;
if(wallc[cs].size()){
auto itr=(wallc[cs].lower_bound(rs));
itr--;
wall=*itr+1;
}
rs=max({wall,rs-l,(int)1});
}else if(d=='R'){
int wall=w+1;
if(wallr[rs].size()){
wall=*wallr[rs].lower_bound(cs)-1;
}
cs=min({wall,cs+l,w});
}else if(d=='L'){
int wall=-1;
if(wallr[rs].size()){
auto itr=(wallr[rs].lower_bound(cs));
itr--;
wall=*itr+1;
}
cs=max({wall,cs-l,(int)1});
}
Ans(rs<<" "<<cs);
}
}
ABC215 D - Coprime 2
全ての配列の要素と互いに素な(M以下の)数を列挙する問題.
出てきた数の素因数を列挙する→そいつらの倍数を全て列挙する.
そうすると答えの補集合ができる.
線形篩っていう解法があるらしい. 来週区間篩とかの素数系を少し学んでみようと思う.
signed main(){
int n,m;cin>>n>>m;
set<int>primes,lib,ans;
rep(i,n){
int t;cin>>t;
for(int j=2;j*j<=t;j++){
while(t%j==0){
primes.insert(j);
t/=j;
}
if(t!=1){
primes.insert(t);
}
}
}
for(auto p:primes){
for(int i=p;i<=m;i+=p){
lib.insert(i);
}
}
Ans(m-lib.size());
rep(i,m){
if(!lib.count(i+1)){
Ans(i+1);
}
}
}
ABC295 D - Three Days Ago
あるindexについて ”そこまでの累積の登場回数が奇数の数字の集合” が等しい組同士はそこを両端に嬉しい列の条件を満たす. 最初を忘れずに入れればclear!
signed main(){
string s;cin>>s;
vi cnt(10);
map<vi,int>M;
M[cnt]++;
for(auto c:s){
cnt[c-'0']^=1;
M[cnt]++;
}
int ans=0;
for(auto m:M){
ans+=m.second*(m.second-1)/2;
}
Ans(ans);
}
ABC270 D - Stones
それぞれのnに対して, dp[a[i]個とった後の残りの個数]の値が相手が取る個数だから, 残った数-dp[それ]をしていく.
signed main(void){
int n,k;cin>>n>>k;
vin(A,k);
vvi dp(n+1,vi(k+1));
vi ans(n+1);
rep(i,n+1){
dp[i][0]=0;
}
repi(i,1,n+1){
rep(j,k){
int p=i-A[j];
if(0<=p&&p<n){
dp[i][j]=max(dp[i][j],i-ans[p]);
}
}
rep(j,k){
ans[i]=max(ans[i],dp[i][j]);
}
}
Ans(ans[n]);
}
EDPC
EDPCを前から埋めていくのを始めました。
A
B
C
D
最後に
こんなに長い記事を最後まで見ていただいてありがとうございます！
解説部分は常体で、感想とかは敬体で書いていたら文章がごちゃごちゃしてしまってどうしたものか、、、と思いました笑
わかりにくかったり、間違っている部分があったらぜひ教えてください！
また、書いて欲しい記事があればぜひリクエストしてください！
Discussion