東北大学プログラミングコンテスト TUPC2023 を 2024/03/09 に開催した．公開が遅くなってしまったが，準備の裏話や，問題と当日の感想を書く． 準備について 夏頃に運営の募集をかけた．今年はwriterとして，去年からの僕，仮の人君，とりゐ君，milkcoffee…

9/16〜9/18 に国立オリンピック記念青少年総合センターで開催された JAG 夏合宿 2023 に参加した．jag-icpc.org Day 0 高速バスで仙台から東京に移動．合宿参加費 Day 1 12時半ごろにオリンピックセンターに到着．建物がめちゃくちゃでかくてびっくりした．…

チーム suzukaze_Aobayama (milkcoffee, karinohito, sotanishy) で，ICPC2023 国内予選 に参加した．このチームは，今のメンバーでは2年目である．そして，milk さんの参加資格が今年で最後なので，このメンバーでやれるのは今年が最後になる．コーチはこた…

東北大学プログラミングコンテスト (TUPC) 2022 を 3/4 (土) に AtCoder で開催した．僕は writer，運営としてコンテストに関わった．atcoder.jpこの記事では，TUPC2022 の各問題について，僕視点の感想や裏話を書いたり，当日のオンサイト会場の感想などを…

2023/2/12 の AGC061 で念願の AtCoder 橙になりました．(ABC を除く) コンテスト中 AC の difficulty の自己ベストを大幅更新して色変出来たので，最高です． 各種記録 やったこと 問題を解く 黄を全部埋める いつ達成したか忘れたが，B1 の頃に達成した気…

チーム suzukaze_Aobayama (milkcoffee, karinohito, sotanishy) で，ICPC アジア地区横浜大会 2022 に参加した．今回はオンサイトでできるということで，とても楽しみだった．一方で，コロナ前のICPCルール (ライブラリ写経やPC1台制限) に触れるのが初めて…

チーム 今年も suzukaze_Aobayama です． karinohito: 数学，発想ゲー担当 milkcoffee: 今年加入．最適化，DP，大量の作問ストックで問題を爆破する担当 sotanishy: データ構造，グラフ，幾何，構文解析，重実装，知識ゲー担当 去年のチームメイトだったむげ…

はじめに 行列の \(n\) 乗の計算をする時，対角化すると，固有値を \(n\) 乗するだけになるので計算が楽になります (競プロだと繰り返し二乗法で十分速いのであまり使い所がないですが，手計算でやるときは対角化をすると圧倒的に楽になります)．ところで，…

国内予選の参加記はこちらsotanishy.hatenablog.comチームはsuzukaze_Aobayama．メンバーは相変わらずむげんさん，仮の人君，僕．目標は，とりあえず全体の半分以上の20位，欲を言えば15位．国内予選での順位（6位）を考えるとかなり低めの目標と思われるか…

チーム 昨年のチーム state_of_the_art のメンバーのクマノミさんが，外部の大学院に進学されたので，人員補充をしました．東北大でかなりレートを伸ばしてきていた仮の人君に声をかけて，チームを組みました．むげんさん：典型をたくさん知っている．データ…

最高に面白い 問題 atcoder.jp 解法 重要な観察として，すぬけ君が動ける範囲はBが来るたびに半分以下になるというのがある．最終的にすぬけ君が勝つ，すなわちすぬけ君の動ける範囲が1マス以上あるためには，Bを置く回数は\(O(\log n)\)回程度でなければな…

問題 atcoder.jp 解法 公式解説は行列累乗で解いているが，僕はダブリングで解いた（まあやっていることが実質同じといえば，それはそう）．まず\(d\)桁の項が\(s_l\)から\(s_r\)であるとする．\(l, r\)は二分探索で求められる．この区間での和は \[ 10^{d(r…

形式べき級数楽しい 問題 atcoder.jp 解法 サンプルを見ると明らかに解には対称性があるので，\(i \leq K + 1\)の時のみ考える．解を多項式の係数に帰着する．\(x^n\)の係数が，数字を\(n\)個選んだ時の組み合わせの数という風に．まず，\(a + b = i\)なる\(…

yosupo judge のデータ構造を全部解いた．解法と感想をメモする．judge.yosupo.jp Associative Array Unionfind Static Range Sum Static RMQ Point Add Range Sum Point Set Range Composite Range Affine Range Sum Range Chmin Chmax Add Range Sum Range…

面白い 問題 atcoder.jp 解法 一般性を失わず，\(A \leq B\)とする．\(S_{i + 2} - S_i 次のようなDPを考える\[ \begin{cases} dp[i][0] = \text{\(S_i\)を\(X\)に振り分けるときの，\(S_i, \dots, S_N\)の振り分け方} \\ dp[i][1] = \text{\(S_i\)を\(Y\)に…

何か同じやり方の人が見当たらなかったのでatcoder.jp 問題概要 \(H \times W\)のグリッドが与えられる．各マスには文字が書いてある．行と列を適当に並べ替えて，グリッドを点対称にできるか？制約: \(H, W \leq 12\) 解法 まずグリッドを入れ替えるやつは…

12/7日のyukicoderのアドベントカレンダーコンテストで出題しました．初めての作問です．まず解説を書き，その後作問するときにやったこととこの問題の背景について書きます．yukicoder.me 解説 コンテストサイトの方にも簡単な解説がありますが，もうちょっ…

競プロerのsotanishyです．以前別のタイトルのブログを書いていて，そこに競プロの記事もたまに書いていたのですが，僕は競プロ以外の記事も書く人なので混ざるのは良くないと思い，競プロ用のブログを開設しました． 参加記とか解いた問題とかアルゴリズム/…