dmk2E

趣味で競技プログラミングやってます（AtCoder A:緑 H:茶）．
たまにハッカソンにも参加してます．
現在はWeb開発をフルスタックに勉強中です．

[dmk2E @dmk2E]

春休みに、サークルの公式サイトをチームで開発しました🚀
その過程で学んだこと、開発体制などを記事にまとめています。

同じようにサークルサイトを内製しようと考えている方の参考になれば嬉しいです！
是非読んでみてください👇
https://t.co/PAzlvw6TN8?

#Web開発
#サークル運営
#Zenn

[dmk2E @dmk2E]

RSS Hackathon 2025 Beyond に参加して，初対面の場での気まずさや役割分担のもやもやを解消するWebアプリを開発しました！
とても楽しかったです！
参加記を書きました👇
https://t.co/PHSUsfBQdj #ハッカソン #Web開発 #zenn

[dmk2E @dmk2E]

A:for文
B:"-1"を適当な値で埋めて，[1,N]の順列を作成
C:先頭位置管理+累積和
D:マス毎に塗った時刻を管理+多始点BFS_黒マスを起点に，4隅の白いマスを塗るかどうかの判定を繰り返す
#AtCoder
#ABC425

[dmk2E @dmk2E]

Cの補足の続き：
これを利用し，主に以下の3パターンに分けて，それぞれで高速化して考える．
<i> A>0 && B>0 && C>0
<ii>B<=0 && A>0 && C>0 && A!= 0
<iii>A == Cが成立した後
※ <iii> においては，「(A,A,C)->(A,C,C)」を1セットにして操作を繰り返すとAとCの数が同数になり，周期性が存在する

[dmk2E @dmk2E]

A：工夫して場合分けを減らす
B：全探索
C：貪欲法 + 高速シミュレーション（周期性なども含む）で解く．最悪計算量は，O(T)
※バチャ参加
#AtCoder
#ABC422

[dmk2E @dmk2E]

Aの補足：ワールド番号wとステージ番号sを 0-indexed で捉え，現在のステージを`e = w*8 + s`という値に変換して考える．すると"{(e+1)/8}-{(e+1)%8}" が答え．
Cの補足：
A,C以外の選び方について，以下の貪欲法が成立する．
・Bの数が残っている時は，B
・A,C のみが残っている時は，数が大きい方

[dmk2E @dmk2E]

A:連想配列 B:優先度付きキュー
C:貪欲法_
max(ceil(x座標の範囲/2),ceil(y座標の範囲/2))
D:imos法_Sの各文字が，M回の操作終了後に，SとTそれぞれどちらにあるかを判定できればよく，それは区間和を高速に計算すればよい．

Cに時間をかけすぎてしまい，撃沈...泣
#AtCoder
#ABC419

[dmk2E @dmk2E]

A:t.substr(n-3,3)=="tea"
B:全探索
C:前処理で高速化_bの値に対する解の配列を予め求めておく．これはbの昇順に，シミュレーションで求められる．イメージは，フレーバー毎にその個数を表現した棒グラフ．最悪計算量は，O(N*log2(N)+max(B)+Q)
#AtCoder
#ABC418

[dmk2E @dmk2E]

A:a.substr(a,n-a-b)
B:シミュレーション
C:iの降順に時系列処理_
(j∈[i+1,a.size())の範囲で，j-a[j]=a[i]+iを満たす添え字の数)を各iについて順に加算した総和が解となる．連想配列を用いて処理するため，最悪計算量はO(N*log2(N))
#AtCoder
#ABC417

[dmk2E @dmk2E]

A:愚直に
B:貪欲法_Sを左から右へ順に走査し，「直前に置いた'o'より後で，最も近い"#."の'.'に'o'を置く」という操作を繰り返す．
C:全探索_制約が小さいので，再帰を用いた全探索．生成した文字列を一旦配列に入れたのち，ソートして解を出力する
#AtCoder
#ABC416

[dmk2E @dmk2E]

3年分のICPC参加記を書きました！今年の大会を中心に，チームの戦略や練習内容をまとめています．長文ですが，これからICPCに挑戦する方の参考になれば嬉しいです！

ACM-ICPC 国内予選 参加記（ICPC2023～ICPC2025） https://t.co/w3BoDAfInr #Qiita #ICPC #競技プログラミング #競プロ #アルゴリズム

[【公式】技育プロジェクト | サポーターズ @geek_pjt]

⛺️#技育CAMP 2025💻
【#ハッカソン Vol.7終了】

みなさん、2日間本当にお疲れさまでした！！

約6割の方がハッカソン初参加の中、
なんと全チーム無事完走💨 すごいです👏

今年度は2月のVol.22まで続きます！
またのご参加お待ちしてます🔥
(集合写真の掲載許可いただいてます)

[dmk2E @dmk2E]

A:そのまま B:setで愚直
C:両端キュー+ランレングス圧縮 _(x,c)の形で整数列Aを保持すると，Aの要素数は最大Q個で，それぞれ出し入れするだけになる．
D:整数列Aを値の絶対値の昇順に整列&公比である分数を適切に保持して判定．
ただし，Aが全て同じ要素である時は例外処理を行う．
#AtCoder
#ABC413

[dmk2E @dmk2E]

E:訪問済み頂点を始点とする多始点BFSを繰り返す貪欲法 O(n^2)
_訪問済み頂点を始点とする多始点BFSを行うことで，"ei+(その頂点までの到達時間)"が最小となる頂点iを求め，そこへの移動を最優先で行うことを繰り返すシミュレーションを行えばよい．

[dmk2E @dmk2E]

ICPC2025国内予選参加してました．
チームとしては4完(A+B+C+E)で，自分はAとE問題の実装を担当しました．
悔しい気持ちは残りましたが，楽しかったです!
（以下，各問題の方針が続きます．）

[dmk2E @dmk2E]

C:平日の日数から，元々平日だが休日となった日数を数え上げ O(n*log2(n))
_期間[1,m]ではなく，期間[0,m-1]で平日の日数を数え上げる．この期間での平日日数は，"5*floor(m/7)+min(5,m%7)"となる．その後追加休日の一覧を順次見て，7で割った余りから平日か判定，数え上げ．重複の対処ではsetを使用．

[dmk2E @dmk2E]

A:そのまま B:累積和
C:各マスの色状態を持ち，色反転させたマスの両隣のマスを見て数え上げ
D:Trie木+DFS_各文字列はTrie木上の頂点番号で管理．解は，サーバーの頂点番号をTrie木上のDFSで探索し出力する．O(N+Q+Σ|S|)<10^7 となり高速．
#ABC411
#AtCoder

[dmk2E @dmk2E]

A:シミュレーション
B:値毎の個数持つと楽 C:imos法
D:ランレングス圧縮+DP_圧縮後の配列rとし，
dp[i][j]:i番目の要素を0と1のどちらかに決めた時，状態jの時の最小操作回数(∵操作を行う順番は関係無)
├状態0:r[0,i)="00~0"
├状態1:r[0,i)="0~01~1"
└状態2:r[0,i)="0~01~10~0"
#AtCoder #ABC408