2023-08-26

院試体験記 (東北大学理学部数学専攻)

はじめに

R6年度東北大学理学部数学専攻の入学試験を受けました.

出願時の状況は以下の通りです.

東北大学理学部数学科からの進学
併願はせず
博進は未定

院試対策

4年に上がる春休みの段階で過去問を集めました. web上で公開されている東北の直近数年分に加え, そこからさかのぼること20年分くらいは先輩づてで手に入れました. このほか, 大阪, 名古屋, 東工, 神戸, 京都はweb上に多めに掲載されていたのでこれらも追加.

その後友人ら数人と不定期的に院試対策会を行い始めます.
はじめのうちは, 他大学院の問題を中心に, 各自問題を解いてきて答えの確認を, 院試が近くなってきたら東北大の最近の過去問を本番通りのスケジュールで解くということをしていました.

それ以外にもdiscordがかなり活発に動いていて, 解けなかったところのヒントを出し合ったり, 賢そうな解答の共有をしたりしていました.

なんやかんやで用意していた東北大の過去問で当日自分が解く予定の問題は全て解きました.

出願

受験料を払ったのち, 各種書類をインターネット出願システムで登録します.
また, 数学系独自の調査書もあり, 四年セミナーの内容や, 卒業後の希望, 講義外でのセミナー活動, 好きな定理について等を記入しました.
いざ書こうとすると書く内容に迷い, 記入には結構時間がかかりました.

前日

起床の練習として試験日程に合わせて大学へ向かいました. 流石に前日ともなると新たな知識を入れる感じでもないので友人と駄弁って英気を養っていました.
午後には流石に何かやるかとなってちゃんとした解答の作れていなかったR4-専門-1(4)を数人で考えました.
中々進展がありませんでしたが, 要素を1つ以外潰すような準同型を作り, それのカーネル(これは一般に正規部分群になる)をとり, というのを数回適切な順番で行えば, 可解群たらしめる部分群の列が作れます. 適当な部分群を考えてしまうと正規部分群であることの確認や商群が可換であることの確認が超面倒ですが, この解法ではそのどちらもが簡単に確認できてとても気持ちが良いです.
これが解けるまでは可解群の問題当日出ないでくれ～と言っていましたが, これを解いた直後から可解群の問題出てくれ～というようになりました.

当日(day1)

朝

6:30に起床して競プロを1問解きました.
その後朝食をとり, 8:30位に大学に着きました. まだ開場していなかったので, C棟で友人と駄弁りながら開場を待ちました.
ほどなくして開場したので受験票の確認をした後, 入室しました.

午前・共通

1問目

線形代数の問題です. 変数の入った3次正方行列をあれこれする問題です.
ジョルダン標準形を求めることが主題な問題は東北大の過去問に一度も出ていなかったのでややビックリしました.
(1)行列に元からある変数やら固有値を求めるための変数やらが入り混じって大変なことになりそうだったので, 一つ自明に出てくる固有値を探した後, 固有値の積が行列式であることと固有値の和がトレースであることを使って楽をしようとしましたが, 結局計算ミスをしてかなりの時間と計算用紙を費やしました. 計算用紙は2枚裏表が使えるのですが, 1枚半には行列計算の痕跡が残ることになりました. 後から聞いた話では対称性のようなもののおかげで, 愚直に計算してもそこまでは大変にならないらしいです.
(2)固有値を(1)で既に求めていたのでほぼ何もすることがありませんでした.
(1)を展開した形で求めて(2)では微分を利用することが想定なのかと思いましたが, その方針を取った人曰く大変なことになったらしいのでどのような想定でこの問題があったのかはあまりよく分かりませんでした.
(3)3次なので固有空間の次元を求めればジョルダン標準形が決定できます. 確認の意を込めて, 結論を書いた後で実際にジョルダン化できる相似変換を求めました.

2問目

位相の問題です.
(1)端点が有理数であれば $\mathbb{R}$ の開区間も閉区間も相対位相では同じものになることから議論を進められます.
(2)もし2点あったらその間の有理数で2つの開区間に分けられてしまい連結性に反します.
(3)(2)より定値でなければ像が非連結と分かります.
(4) $0\notin X$ であるので, $(-\infty,\frac{1}{n})\cup (\frac{1}{n},\infty)$ (の相対位相をとったもの) がコンパクトでない論拠となります.

3問目

実解析の問題です. 関数列が与えられるので一様収束性を議論します.
(1)各点毎に極限を考えるだけですが, なぜか $1-x^{2}$ で $x=0$ を代入した値を $0$ と勘違いしました. 結論は変わらないですが.
(2)必ず $x$ と $(1-x^{2})^n$ のどちらかが十分小さくなるような $n$ を探せばよいです.
(3)(1)と同じミスをしました. 今回は結論にも影響が出てしまいます.
(4) $n$ を止めた後に $x$ を上手く取れば $g(x)$ と $f_n'(x)$ が十分離れるようにできます. ここで取るべき $x$ が $0$ 以外にもあったので, (3)で間違えていても間違えていなくても(ほぼ)同じ議論が回せるのは不幸中の幸いでした. なお, (3)を正しく計算すると不連続になるため, 連続関数の収束に関する一般論からそもそもこの議論が要らないものとなります.

4問目

実解析の問題です. (1) 符号が交互に現れることと, 各項の絶対値の値は単調減少することから, 2項ずつペアにすると正となります.
(2) 初項と末項を2つずつペアにすれば, $S_{*}$ が $a_{1}$ で上から抑えられるので(1)と合わせて収束性が言えます.
(3) 積分の区間を分割したものを数列とすれば, (1),(2)の議論が使えます. (2)の評価だと, 一か所不等式が真となる事までは言えないので, もう2項先まで見る必要がありました.

3完半といった感じだと思います. 3問目のミスがとてもつまらないものだったので悔しいですが, 試験直後は全完のつもりでいたので, 精神的には大分余裕が生まれました.
周りの反応は2.5~3.5完位が多く, 大問1で苦労したのを後半にも引きずってしまったという人もちらほらいました.

昼食

学食が普通に空いていたので冷やしラーメンを食べました. 冷やしラーメンというより冷麺ぽかったが夏らしくて美味しかったです.

午後・専門

専門は例年8題(代数2問, 幾何2問, 解析3問, 基礎論1問)の中から3題を選んで解答する形式です.
代数は2問しかないため, 代数分野を志望する場合他分野からもう一問解く必要があります. 過去問では, 大体の回で基礎論を, それが解けなさそうな時は複素解析を解いていました.

1つ目・大問1(群論)

正規部分群に対する問題で, 全体の主題としては部分群の列でどこに正規部分群の関係があれば別のどこかでも正規部分群の関係にあることが言えないかといった感じです.
(1)~(3)に関しては特別な発想も必要なく状況を整理して基本をできていれば解けると思います.
(4)では, $S_4\triangleright N, N\triangleright K, S_4\ntriangleright K$ となる例を一つ探せばよいです. ( $S_4$ は4次対称群)
まず $N$ は交代群かクラインの四元群である必要があります. 感覚的には指数が大きいほど正規部分群になりにくいので, より位数の小さいクラインの四元群の方を $N$ として選びます. すると $N\triangleright K$ なる非自明な $K$ も同型を除いて一意に定まります.
後は $S_4\triangleright N, N\triangleright K, S_4\ntriangleright K$ を実際に示せば良く, これはそれぞれ, 型をみる, 全て計算する, 適当に具体例を一個計算する, という事をすれば示せます.

2つ目・大問2(体論)

ガロア拡大に関する問題で, 過去に類を見ないほど素直な問題でした.
(1)はアイゼンシュタインの既約判定法( $p=2$ ) をしても良いし, 3次式なので $\mathbb{Q}$ 上に根を持たないことを言うだけでも良さそうです.
(2)は両側の包含を, 生成元が含まれるかの確認によって示せばよいです.
(3)は拡大を2段階に分ければ簡単な議論で拡大次数が求まります. ガロア群が3次対称群と同型なことは, 後の問題の関係で $(12),(123)\in S_{3}$ に対応するようなガロア群の元を持ってくることで示しました.
(4)ガロア群が特定できているのでガロアの基本対応で良いです. 答え自体は簡単に予想がつく/知っているので, それらを列挙して, ガロア群の部分群の個数からそれらで尽くされることを言っても論理上は問題なさそうです.

3つ目・大問6(関数解析)

基礎論も複素解析もちゃんと詰め切れる自信が無さそうな問題をしていたので, どちらにするか悩みながら他の問題もパラパラみていたら関数解析が解けそうだったので急遽これに手を付けることにしました.
バナッハ空間の問題で, 関数空間上で積分を用いて定まる作用素を考える問題です.
(1)H22の共通で似た問題をみました. 帰納法をして, 直前の結果を用いて評価を少しずつ厳しくしていけばよいです. (2)無限和を直接扱うのではなく, 有限個で止めた状態でコーシー性を示すことによって完備性からその極限として無限和の正当性が担保できます.
(3)こちらも有限で止めたもので議論し, ノルムの連続性から極限をとったものへの議論へと移行できます. 一意性も該当する元を2個とればその差のノルムが0であることを示せます.

3完できたと思っていていて, 議論不足や気づかぬうっかりで多少点が引かれていたとしても十分な出来だと思います.
代数2問がかなりあっさりした問題で, ここ数年の中では圧倒的に解きやすかったです. 話を聞いた中にも2問とも完答or1-4以外解けたと言っていた人がそれなりの人数いました.
関数解析は本番解く予定はありませんでしたが友人たちが解いているのを聞いたり一応講義を振りかったりしておいたのが功を奏しました.

午後・英語

(1) 長文読解です. 和訳や要約をします. 数学を題材にした文章ですが, どちらかと言えば受験英語のような感じです.
(2) 英訳です. 定理とその証明が与えられるのでそれをまるまる英訳します. 普段何となくで英語を読んでいるのでなんとなくな文章を書きました. 多分伝わるけども......みたいな文章が完成したと思います.

その後

翌日の面接で解けなかった問題について聞かれるという噂があったため, 何人かで集まって解答のすり合わせをしました.
その後はサイゼリヤで夕食と間違い探しをしました.

当日(day2)

面接

集合の15分ほど前に控室に行きました. 到着はほぼ一番乗りでしたが, 続々と受験生が集まり, その後滞りなく面接が開始されました.
服装に関しては, 解析は全員スーツを着ていて, 代数はスーツ/私服が半々くらいでした. 私は普段着よりはちゃんとしているつもりの私服で行きました. 面接は分野ごとに部屋が分かれているのですが, 開始5,6分で幾何と代数の部屋から最初の一人が戻ってきてあまりの早さに控室が少しざわつきました.
ほどなくして私の番がやってきました.
内容としては, 博進についてと4年セミナーと院での希望が若干違うことについて質問されたのでそれぞれ正直に答えました.
また, 4年セミナーでどんなことをしているかの質問に, 楕円曲線に関する本を読んでいますとだけ答えたところ, その話題はそれで終わってしまったのでもしかしたらその質問の段階でもう少し詳細を答えるべきだったのかもしれません. 後は調査書で競プロについて触れていたのでそれに関して雑談のような質問があり, 面接が終了しました.
入退室や名乗りを除けば5分もかからなかったと思います.
調査書に書いた好きな定理や4年セミナーでやった定理のステートメントや証明の概略などを聞かれると前情報を仕入れていたので, それらが全く無かったことに驚きました.
ただ, 分野によってはこのあたりをしっかり聞かれ, 雰囲気もかなり違ったらしいので, 先人から面接の様子を聞きたい場合は希望する分野の人から聞くと良さそうです.

その後

合格発表まで数時間あったので一旦帰宅して爆睡していました.

合格発表

合格発表の掲示は例年予定時間から少し遅れるらしいと聞いていたので, 17時から20分ほど遅らせて大学に向かいました.
数学棟の外に人だかりが出来ていたが, 掲示物らしきものは見当たらなかったので発表がまだなのだと思い, 近くにいた友人たちの会話に首を突っ込みました. しかし, どうやら建物の内部に合格者掲示があったようで, 合格発表にわき目も振らず会話に入ってくる強者のような図になってしまったらしいです(友人談).
建物の中で番号を確認したところ, ちゃんと自分の番号もあり一安心. これにて私の院試終了です.

さいごに

院試は過去問こそあるものの解答はほとんど出回っていません. 解答のすり合わせという点でもモチベーションの維持という点でも友人との協力体制が大事だと感じました.

2023-06-20

2023/6/8~2023/6/17

今週から日曜を一週間のスタートとする. (これまでセミナーの日がスタートで大変だったので)

2023/6/8 (木)

午前は講義をオンラインで聞いて午後から青葉山でセミナー.
今回かなり分からないところを残してしまっており, 本に書いてある主張に条件を足したり, 途中までだったりまでをこう考えましたと話した. どうやら, やはり一般的な議論の流れと, この本の議論の流れが逆になっているらしく, 後から立ち返ってみると良いとアドバイスをもらったので, 暫くしたらまた考えることとする.
その後は同級生の発表を聞いて帰宅.
夜は話題になっていたコードレビュービンゴをした.
すでにゴルフはかなり進んでおり, 乱択まつりになっていたのでそちらには参加せず, 全言語completeをした.

2023/6/9 (金)

1限から青葉山に登り, セミナーを聞く.
今回はヒルベルト記号の導入で, ヒルベルト記号をルジャンドル記号で表す話だった.
本に載っている証明は場合分けパワーで押していくもので, 一個一個の議論は簡単だが, 発表となると板書の量などが大変そうだった.
午後は帰宅して昼寝したらそのまま夜になったので雑務をして就寝.

2023/6/10 (土)

日中は散歩をしたり買い物をしたりした.
夜はABC305

A: 計算で頭のリソースを使うより先に給水所全探索のコードが完成していたのでそちらを提出.
B: 文字コード間の距離を利用して総和を計算.
C: クッキーの上下左右の端を求めてから中を全探索.
D: ちょっと面倒くさい二分探索+累積和. $f(R)-f(L)$ の形に帰着するのを思いつかなかったのはダメだった.
E: ダイクストラを逆向きにする感じ.
F: ちょっと考え込んでしまった. 気づいてしまえばグラフの情報を取得しながらDFSするだけであった.
G: 制約に行列累乗と書いてあり, さらに末尾の文字列を状態にすると良いと書いてあった. これもバグらせそうだったので, 小さい値では愚直解法を書いておいた.
Ex: 誤読していたが誤読していなくても解けていなさそう.

2023/6/11 (日)

午後は久しぶりにヒューリスティックコンテストにでた.
ほぼ貪欲only465M点

辺の全頂点MSTを求める
各局の強度を0で初期化
次の住民を圏内に入れるための増加コストを各局求める
増加コスト小さい順に強度を更新して3へ
内包されてる局を削除
圏内全ての住民が他の局から通信を受けれる局を削除
MSTで子に通信中の局が無い枝を削除

といった事をした.

2023/6/12 (月)

今日は夕方頃からICPCのチーム練習として https://codeforces.com/gym/103185 をした.

N: Non-Integer Donuts(考,実)
読解9割に不快1割を足したみたいな問題.

L: Lola's Schedule(考,実)
適当な全探索が間に合うのでそれをする.

C: Crisis at the Wedding(考,実)
ここまではほぼ読めてしまえば考察が要らない問題.

G: Game of Slots(考,実)
このセットで一番面白かった.
まず, 整数値の取る範囲がとる個数に比べて十分大きいので連続的な値をとるとして影響無さそうと思う.
すると, 適当に積分をするという発想に至るが, 上手く回らない.
そこで, 再び離散的な考えに戻ると, 先の積分の思考から同じ値は取らないとして問題ないことに気づく. すると, 3乗のDPが生えてきて解ける.

K: Keylogger(考,実)
累積和したりimosしたりDPしたり二分探索したりする.

J: Job Allocator(考)
グラフ上の遷移を考えるが, 状態が多くて大変.
直感的に, 遷移の大半は遷移先がかなり絞れそうだったので, 半分全列挙を提案.
これが想定ではなかったが, 十分通る解法になったようだった.

このほか, チームメイトがDEFHを解いていた.
全体的に面白い問題が多かった. (前半のやるだけもwelcome問題としては十分な感じだと思った. )

2023/6/13 (火)

午前は代数幾何の講義.
今日は友人たちが教育実習やらで全然いなかったので普段より板書書き写し系のノートをとっていたが, 終盤腹痛によって尻切れになってしまった. すまん.
午後は控室でうとうとしながら競プロと数学をしたのち, 下山してサークルの定例会.

今回からICPCに向けて国内予選と模擬国内の問題でバチャをした.
前半はすいすい解けたが, 幾何で積分する問題の答えが延々と合わず時間切れとなってしまった.
正直後からちゃんと通したいとも思えないが, 国内予選までに解くべきなんだろうなぁ.

2023/6/14 (水)

セミナーの準備. 今回は+αで話そうと思えばいくらでも話を膨らませてしまう感じなので, 適当な塩梅を探す.

2023/6/15 (木)

午前はオンラインで数学の講義.
今日もCAT(0)空間の話.

午後からは青葉山でセミナー.
今週は通例と違って, 今日が数論講義の方.
先週の場合分けの続きと, 積公式について.

2023/6/16 (金)

一限から青葉山でセミナー.
今日は代数曲線の写像の分岐指数と, フロベニウス写像について話した.

昼食後控室で数学. 帰宅後どっと疲労が出てしまい, 布団に倒れ込んだまま寝てしまった.
辛うじて夕食だけ取って就寝.

2023/6/17 (土)

起床後しばらく布団でグダグダして, 散歩に出たが暑すぎてすぐ帰宅.
夜は久しぶりにお酒な気分だったのでスーパーで総菜を買って, 何となく目に着いた杏子酒を飲んでみた.
梅酒よりさらに甘い気がして食事には合わなかったがまあまあ美味しい.
先に食事は食事で済ませることにしたので, 酒の当てが無くなってしまい, 出る予定の無かったABCをつまみにすることにした.

A: Echo
各文字を二回出力する.

B: Base 2
$2^{64}-1$ ってlonglongに収まるっけ?と思いながら投げたら案の定収まらないので久しぶりにunsignedした.

C: Centers
各値の出現回数を持ちながら走査.

D: Poisonous Full-Course
高橋君の状態をもちながらDP.
最近Dに程よい難易度のDPがでているのが良い傾向だと勝手に思っている.

E: Best Performances
以前実装に手間取りまくったので, 今回必要な機能をまるっとライブラリ化していたのでライブラリを探して貼るだけにできた.

F: Merge Sets
主客転倒をする. 座圧をすると, セグ木に載せられる.

G: Return to 1
閉路の最大公約数が欲しいが, 閉路全列挙は多分できない.
そこで, 各頂点を通る最短閉路と, 各辺を通る最短閉路だけ抜き出すことにして一回投げてみた.

ここで, どうやらジャッジが詰まっていたようで, 結果が返ってこなかったので, この日記を書き始めた.

今週は寝すぎたせいで日記を書いていなかったので, 思い出しながら書いているが, 書く内容が時間のしっかり記録されている競プロ位になってしまった. 3週目にしてこれとはそろそろ日記が途絶えそうな気がしている.

2023-06-09

2023/5/25~2023/5/31

2023/5/25 (木)

7:30起床. あさかつARC.

A: D[i]=#{(B,C)|B*C<=i} を累積和使って求めて置いて, Σ(D[K/A]) をする.
B: x=A/2 を全探索
C: 答えで二分探索
D: Qが奇数なら1回愚直に操作してQ:偶数にする. 操作を2回まとめると単にrotateになるので計何回rotateするか計算する.
E: xを右にずらしたときに答えが増える間右にずらす

その後は先週出れなかった一限のオンライン講義. これは数学の講義を英語で受けてみようという趣旨のもので元は留学生向けの講義であるが, 誰でも受けられる.
代数学, 幾何, 解析の3パートに分かれており, 今日は代数の最終回であった. 内容としては素数定理周りで, 後でちゃんと自分で手を動かさないと実感が無いというのが正直なところである. 課題も出たことなので時間のある時に色々いじるつもり.

その後昼寝をしたのち, こどふぉのバチャ.
https://codeforces.com/contest/600

A: Extract Numbers

正規表現で殴れるのかな?
分からんかったので前から文字列を愚直に舐めていった.
https://codeforces.com/contest/600/submission/207117620

B: Queries about less or equal elements

二分探索や尺取りなりをするだけ. なるほどEducationalって感じ.
https://codeforces.com/contest/600/submission/207117807

C: Make Palindrome

最終的に並べ替えるので, 各文字の出現数だけ記録しておけばよい.
奇数登場する文字の種類を, $c$ 種類とすると, 変更回数の最小値は $\lfloor \frac{c}{2}\rfloor$ 回である.
この時, できるだけ大きい文字を小さい文字に変更するのが良い.
文字を変更した後は貪欲に辞書順最小を構成.
https://codeforces.com/contest/600/submission/207118272

D: Area of Two Circles' Intersection

数学をして, 交わらない, 内包, その間それぞれで計算をする.
途中謎にlong long で計算してしまってペナを多数吐いてしまった.
https://codeforces.com/contest/600/submission/207120054

E: Lomsat gelral

各部分木毎に, 各文字の出現回数とその最大値等を記録していきたい.
しかし, それをするとマージの際に計算量が大変なことになる.
そこで, マージテクをする.
各頂点に記録を残していくのではなく, 各頂点の記録がどこに保管されているかをメモっておけば, 毎回コピーせずにその記録をいじることができる. よって, 子の記録のうち, 要素数が最大のところにその他の子の記録を追加していって, 最後に自身の記録がその子のところにある旨を保持しておけばよい.
https://codeforces.com/contest/600/submission/207124239

F: Edge coloring of bipartite graph

次数の最大値が答えになるのは知っているのが, 如何せん二部グラフの辺彩色の実装が面倒くさくて投げ出してしまった. いつかはちゃんとやります......

総括

5完5ペナ8位. みんなDでペなりまくっていた.

夜はOMCに出た.

A

一瞬ぎょっとしたが, $x\in \mathbb{Z}$ が不適なため, $\frac{n+1}{n}\le\frac{2357}{2345}$ を考えればよい.

B

最後に残った数を $(0,k)$ とすると, その直前は $(k,k)$ に限られ, さらにその前は $(k,2k)$ に限られる.
その前は2通りあり, $(k,3k),(2k,3k)$ のどちらか.

C

$AE,AF$ を延長して角度を追うと, $AE=AF$ が出るので, 角度が全て求まる.
角度が出てしまえば, 三角関数で殴りやすい.

D

$a_{1}=\frac{p}{q}(a_{2}+a_{3})$ , $a_{1}+a_{4}+a_{7}=S$ とすると, 条件式を全て足して $S=\frac{45p}{p+q}$ が得られる.
$S$ の範囲や, $S\in \mathbb{Z}$ を使って候補を絞る.

E

$f(1),f(2),f(3),f(4),f(9)$ はすぐに出る. ここで実験から $f(8)=8$ とエスパー. すると, 総和の条件から残りはほぼ決まる.

F

時間内に解けなかった.

総括

5完2ペナ29位. 久しぶりにしては健闘できた.

2023/5/26 (金)

7:30起床あさかつARCに出た.

A: $A,B$ をどっちも全探索.
B: 上の桁から決定.
C: どーせ片方 $(1,2,\dots,N)$ でいいだろ→ACしたので証明完了をした.
D: 二回操作しても, 一回の操作で代替できる. よって, 操作は一回のみとしてよく, 各bitの寄与で求まる.
E: 場合分けを頑張る.
F: 数十分遅れでAC.

日中は昼寝や数学をしていた.

夜になって, 一昨日までにやらなければいけなかったタスク(電気代振込)があったことを思い出したので慌てて深夜徘徊にでた.

帰宅後はこどふぉバチャ
https://codeforces.com/contest/1622

A: Construct a Rectangle

いくつかパターンがあるので丁寧に場合分け.
https://codeforces.com/contest/1622/submission/207365340

B: Berland Music

誤読してかなり時間がかかった.
読解をちゃんとやれば座圧的な事をするだけであった.
https://codeforces.com/contest/1622/submission/207367520

C: Set or Decrease

$a$ を単調非減少としてよい.
デクリメントは, $a_{1}$ のみにすれば良い. それ以外は $a_{1}$ への置き換えの方が真に強い.
また, 置き換えは大きい方から順にやるのが最適.
ここまでくれば, 置き換えを何回するかで全探索という方針が立つ.
累積和をもっておけば, 置き換え $x$ 回の時の, $a_{1}$ のデクリメント必要回数が求まる.
https://codeforces.com/contest/1622/submission/207368633

D: Shuffle

$1$ が少ない場合答えは $1$ .
そうでない場合, $1$ が丁度 $k$ 個ある区間の条件は, $1$ が丁度 $k$ 個以下の区間へと変えられる. (適当に両側を伸ばして $k$ 個含むようにしてその部分を動かさなければ良いので)
ここから重複を取り除くために, 区間の両端は必ず変更するという制約を付ける.
これで過不足なく数えられる.
後は二項係数とかで.
https://codeforces.com/contest/1622/submission/207371436

E: Math Test

絶対値の条件が厄介なので, bit全探索でこれを外す. すなわち, 生徒を二つの集合に分けて, 高得点を目指す集団と低得点を目指す集団にする.
すると, 高得点を目指す集団への得点の寄与-低得点を目指す集団への得点の寄与が大きいところに高い配点を割り当てればよい.
https://codeforces.com/contest/1622/submission/207372932

F: Quadratic Set

分からーん

総括

ooooo- 128位.
Bが10分早く解けていれば順位が50上がっていたらしい.
こどふぉのシステム的に前半で詰まると影響が大きい.

2023/5/27 (土)

7:30起床, あRC.
今回からあさかつdiscordサーバーにお邪魔しているので感想はそちらに書いているのをコピぺ.

ooooo- 31:57
1: 左上から貪欲に, 4近傍で使ってない色を塗っていく.
2: $a+b$ の値で全探索. $a+b=k$ の時, $a$ の範囲は $\lbrack\max(1,k-N), \min(N,k-1)\rbrack$ .
3: $10^N$ 未満でどの桁も同じ数は $O(N)$ 個だけなので全探索できる.
4: 上の桁から決める. その数にするために各 $A_i$ に加算する必要数を $C_i$ として $C$ の小さい $K$ 個の値が $M$ を超えないならそのbitを採用.
5: 繰り上がりを考慮しない桁和の和を求めて, 繰り上がりの回数だけ9を引く.
各桁毎での繰り上がリの回数を求める.
6: 区間スケジューリングぽくなる気がしたけど~~上手くできなかった~~ 出来ました(+30分, 嘘解法感有).

その後昼寝をしたら15時過ぎまで爆睡してしまった.
起床後目覚めのこどふぉばちゃ.
https://codeforces.com/contest/1644

A: Doors and Keys

前から持っている鍵の管理をしていく.
https://codeforces.com/contest/1644/submission/207440032

B: Anti-Fibonacci Permutation

フィボナッチになっている箇所がある数列が割合としてかなり少なそうだったのでランダムに順列を作ってチェックをした.
手元でやったら高速だったので提出 https://codeforces.com/contest/1644/submission/207440891

C: Increase Subarray Sums

まず区間長 $d$ 毎に, 区間和の最大値 $M_{d}$ を求める.
$f(k)=\max_{1\le d\le N}\lbrace M_{d}+x\times\min(k,d)\rbrace$ である.
https://codeforces.com/contest/1644/submission/207441777

D: Cross Coloring

操作を逆順に見ていくと, そこで塗った色が最後まで露出するか否かが分かる.
露出する色数が分かれば後はべき乗するだけ.
https://codeforces.com/contest/1644/submission/207442682

E: Expand the Path

対称性があるので最初に右に進むとする.
すると, 右移動を伸ばすのは, 最初の右移動の時のみとしてよい.
同様に, 下移動を伸ばすのは最初の下移動の時のみとしてよい.
すると後は座圧して寄与を求めるだけだが, これが添え字バグらせ祭りで大変.
https://codeforces.com/contest/1644/submission/207448086

総括

oooo1- 118位.

夜はABC303
https://atcoder.jp/contests/abc303

A: Similar String

頑張って全ての場合を尽くすように書く.

B: Discord

各写真で隣り合っているペアを記録していく. 制約的に $O(N^{3}M)$ でも通るので何しても良さそう.

C: Dash

setでアイテムを管理して移動をシミュレート.

D: Shift vs. CapsLock

DP[何文字目まで見たか][Capsの状態]=最小回数

E: A Gift From the Stars

レベル3以上の頂点を取り除く→残った(次数 $1$ 以上の頂点からなる)サイズ $n$ の連結成分は元々 $n//3$ 個のレベル $2$

F: Damage over Time

逆から見ると, $y=ax$ と $y=b$ みたいなグラフの集まりで各 $x$ での最大が欲しくなるので最大が切り替わる場所を求めてその区間での総和を求めて.......を丁寧にする. 添え字で頭が壊れる～～

G: Bags Game

Exの方が解けそうだったのでそっちへ

Ex: Constrained Tree Degree

知識ゲーとして求める式を閉じた形に持っていけるので後はFPSをすれば良い.

総括

oooooo-(1o) 46位!! 自己ベストに近い順位で良きかな良きかな.

2023/5/28 (日)

この日はARCの記憶が強すぎて後日この日の行動を思い出そうとしてもARCのことしか思い出せなかった.

夜はARC161

A: Make M

偶数番目に小さいのを, 奇数番目に大きいのを並べる.

B: Exactly Three Bits

もし $N$ にbitが $3$ つ以上たっていれば, 上 $3$ つを残して後全部 $0$ にするのが最適.
そうでない場合, 上に帰着されるまで $N$ をデクリメント.
デクリメントは雑に見積もっても $7$ 回で終わる.

C: Dyed by Majority (Odd Tree)

適当に根付き木とする.
葉から順に見ていき, 色がどちらかに確定するかしないかを追っていく.
子の内, 自身の色で塗られた頂点数と, 未確定の頂点数の和がその他より

真に大きければ, 親への制約はない.
等しければ, 親は自身の色で塗らなければならない. (そして矛盾が生じたら塗分け不可)
小さければ塗分け不可

である.
実装ミスでペナと時間をとられたのが痛い.

D: Everywhere is Sparser than Whole (Construction)

完全グラフより辺数が多いのは不可.
そうでない場合, 適当に対称的にやれば通りそうで実際通る.

E: Not Dyed by Majority (Cubic Graph)

これが解けたのが全ての勝因.
まず答えが存在しない場合があるかを考えた.
操作を, $\lbrace 0,1\rbrace^{N}$ (操作前の色を $0,1$ に対応) から $\lbrace 0,1\rbrace^{N}$ (操作後)への写像 $\sigma$ と思うと, これが全射ですか? (全射じゃないなら像に入らない元はどれですか?) という問題になる.
これは濃度の等しい有限集合間の写像なので, 単射性を調べればよく, 単射性を満たさないことは $\sigma(0,0,\dots,0)=\sigma(1,0,\dots,0)=(0,0,\dots,0)$ から直ちに分かる.
ここまで考えた段階で, 私は像では $0,1$ の分布が偏るのでは? という推測を立てた. 例えば, 元々 $0$ が $3$ 個で $1$ が $100$ 個あれば $\sigma$ で送った時に $0$ が減る傾向にあるだろうということである.
証明は大変そうなので, 適当なグラフを作り, $\sigma(\lbrace 0,1\rbrace^{N})$ の元で, $1$ の数が $\frac{N}{2}$ となるものの数を数える実験をした.
すると, 出現率はかなり低くいという事が分かった.
よって, 乱択すれば結構な確率で像に入らないようにできることが分かる.

後は高速に判定問題を解くだけである.
これについては, 実際に手作業で $\sigma$ の適当な元の逆像を求めようとして気が付いた.
ある頂点が $1/0$ の時, その隣接頂点 $3$ つのうち, 任意の $2$ つ組について, 少なくとも一方が $1/0$ である必要があり, 逆に全ての頂点でこのような制約が満たされれば, それは逆像の元となりうる.
これはまさに $2$ SATになるので $O(N)$ で判定問題が解ける.

こうして, 乱択をして $2$ SATで判定をしてを繰り返せば良いことが分かった. ( $N=4$ の時は別処理した)

総括

oo(3o)oo 24位(2190→2306)

自己最高順位更新
自己最高パフォーマンス更新
コンテスト中AC最高diff更新
自己最高レート更新
初赤パフォ

最高である. 先週のAGCで水パフォをとってレートを70近く溶かしていたのを大きく取り返した.
その後twitterで嬉しさを放流した後就寝. (後日一部のツイートは喜びがうるさかったので消した.)

2023/5/29 (月)

7:30 起床, あRC.
o(3o)oo--
1: $M=2N$
2: めっちゃ時間かかったうえ境界をバグらせ3ペナ
3: 差%3==0なら(差)/3
4: 縦横それぞれいくつ以上減らす必要があるか求める
5: 大変だった記憶があったのでパス
6: (5分遅刻)bit毎に見てよく, すると双方に何回寄与するかが分かる.

その後, 奨励賞の授与式のためスーツを着て大学へ向かう.
普段私服で行くところに違う格好で行くのは結構新鮮だった.
早く着きすぎたので, 薬学部の方を散歩してみた. 薬学棟に近づくにつれて薬局のにおいがしてなるほど薬学部だとなった. 気のせいかもしれない.

授与式自体は賞状を受け取って写真を撮った後軽く歓談をする簡単なものだった.
会話を切り出す人が少なかったのであのような場面ではもっと自分から話を振るべきだったと反省.

授与されるのはせいぜい賞状くらいだろうと思っていたが, 色々もらえたので嬉しかった. 特に, プリンストン数学大全(1000頁を超える網羅的な全ジャンル数学書)を頂けたのが嬉しい. 読み物として面白いものなのでちょっとずつ読んでいきたい.

2023/5/30 (火)

8:30 起床. 2限のため大学へ向かう.
今日は代数幾何の講義で, 層係数コホモロジーの準備. このあたりの話は存在だけ聞いたことがありそろそろ手を付けようと思っていた話題なので楽しみ.

午後は控室で友人と駄弁りながら数学をし, その後サークルの定例会のために川内へ下山.

今回のボス問( https://atcoder.jp/contests/arc114/tasks/arc114_e ) バチャ中はしばらく考えたが上手く整理できなかったが, 考えていて面白い問題であった.

夜はこどふぉのバチャ.
https://codeforces.com/contest/1821

A: Matching

先頭の桁は $9$ 通り, それ以外は $10$ 通りの場合寄与がある.
https://codeforces.com/contest/1821/submission/207863266

B: Sort the Subarray

絶対に含まないといけない区間をまず求める.
これは, 元と後で異なるindexの最大, 最小を求めればよい.
その後は, 前後の境界を伸ばす作業に入る.
これは, 伸ばせるだけ伸ばしていけば良い.
https://codeforces.com/contest/1821/submission/207863595

C: Tear It Apart

最後に残す文字を決め打ちすると, その文字で文字列を分割した後, 各文字列について問題を解けば, 全体の答えはそれらの最大値となる.
文字列 $s$ に関しては, 一度の操作で $\left\lceil\frac{|s|}{2}\right\rceil$ だけ文字が消せる.
https://codeforces.com/contest/1821/submission/207864099

D: Black Cells

最初に, 重なっている区間を一つの大きな区間にして扱い易くしておく. (後から気づいたが制約で重ならないようになっていたのでこれは不要だった. )
すると, 各区間は

先頭から途中まで塗る
全て塗る
塗らない

のいずれかとなるが, 途中まで塗るのは最後の位置区間のみ, 道中で区間が2マス以上ある場合, 全て塗るとしてよい.
よって, 1マス区間の個数を持ちながら, その区間で塗り終わる場合の最小コスト(あるいはその区間では塗り終えられない)を計算すればよい.
https://codeforces.com/contest/1821/submission/207868238

E: Rearrange Brackets

まず初期状態で, どの括弧とどの括弧が対応し, その括弧の内側にいくつの括弧があるかを計算する. これはstackを使えばできる.
その後の操作フェーズでは, 内側に括弧が多く入っている対の, 閉じ括弧を開き括弧の直右にもってくれば良い.
https://codeforces.com/contest/1821/submission/207869463

F: Timber

二乗の包除原理の形になって困ってしまったので就寝した.

総括

ooooo- 52位.
5完内最速だったらしい.

2023/5/31 (水)

8:00 起床即朝活ARC.
o-oo-o
1: 答えが高々Nlog(max(A))なのでシミュレーションできる.
2: 時間かかりそうなのでパス. (終了後AC. 答えの桁数を決めると, 周期させる整数の桁数はその約数で, Nのprefixかそれ-1のみを考えればよい. ←よく考えたら答えの桁数候補len( $N$ )かlen( $N$ ) $-1$ だけでした......)
3: $0$ を $-1$ にして累積和のrange
4: $X,Y$ は $A$ [0], $B$ [0]の約数なので先に決め打ち
5: 時間かかりそうなのでパス2
6: 連結の場合: 全域木をとると,(各辺を残すかは葉側から貪欲にきまるので)奇数次数頂点集合が実現可能かは集合サイズのパリティのみに依存するので残った辺は先に自由に決めちゃってOK.→ 一般の場合: 連結成分毎考えて畳み込み

4に関して, 割り算多いわりに計算量結構攻めてるねという話になり, 確かにとなった. 実際自分提出は毎回割り算するもので, 1500ms/5000ms かかっていた.
ここで割り算の大半は前計算できることに気が付いたので, ものは試しということで, こちらのバージョンも書いて見たところ 245ms/5000ms まで早くなりびっくり. これなら大抵の言語でも問題なく通りそうである.

その後は昼寝をしたのち, 本日までの課題をした. 課題内容は素数定理やリーマン予想の帰結について調べるもので, 先日いただいたプリンストン数学大全を早速活用した. 活用したいを優先した結果若干本旨と外れてしまった気もするがご愛嬌ということにした.

その後はセミナーの準備をして就寝.

追記

二週目にして早速下書きのまま公開を忘れていたらしい.

2023-06-08

2023/6/1~2023/6/7

2023/6/1 (木)

7:30起床. あさかつARC.

今回は後ろから解いてみた.

1: シートで区間が分かれて各区間ではいつもの切り上げ
2: 3分間に合わず. 各項の寄与を考えるとフィボナッチの積で端の方だけちょっと違う
3: ACしたので小さい値から貪欲で良いらしい.
4: $\min(N,M)=1$ の時は別処理. k:=max(A)を決め打ちすると, $\max(A)=k,\min(B)\ge k$ が構築可の必要十分.
5: 次に何個送るかをもってDP
6: 実装時間かかりすぎた. $i=1,2$ への操作回数を固定すると残りが全部一意に決まる. また, 全体に操作を一回ずつすると, 打ち消しあう. よって, $i=1$ への操作を $0$ 回, $i=2$ へ $y$ 回として $y$ を求めた,もし負回の操作をしている場所があれば, 全体に操作回数を加算.
6問目は以前時間がかかった記憶があったのにまた時間を掛けてしまった.

その後は数学概説のオンライン講義を受けた.
今日から3部構成の2部目である幾何パートに入った.
メインのトピックはCAT(0)空間で, 後から知ったことだが, 凸最適化とのシナジーがホットらしいのでそちらの面でも興味がある.

午後からは青葉山に登ってセミナー発表を行った.
今回から一般的な代数幾何から, 特に代数曲線に話を移行した.
曲線なら正則点で有理関数の正則性が繋がって良い話ということ等をしゃべった.

2023/6/2 (金)

一限からセミナーのため, 6:30起床.
シャワーを浴びた後うとうとしてしまい, 8:20再起床し絶望.
大大急ぎで身支度をし, 雨の中全力疾走をした.
青葉山駅から教室までもダッシュし, 8:55分頃教室に着いた.
ぎりぎり指導教官の先生が来る前に着けたので事なきを得たが, 朝から色々と非常に疲れてしまった.

セミナーは引き続き, $\mathbb{Q}_{p}$ の乗法群の話であった.
セミナー後は昼食をとって早々に下山. 保健管理センターで血圧の再検査をした.

私はどういう訳か, 診断とか検査の時に以上に緊張をしてしまう性格をしている. 聴診器で検査をする時など, お医者さんに「緊張してますね～リラックスしてください～」と毎回言われる程であるが, そんな私は血圧検査との相性が最悪という事が今回分かった.
自分でも分かる程心臓バックバクの状態でまともな結果が出るはずもなく, 心拍数136, 上の血圧160とかいう訳の分からない結果が出てしまった.
仕方が無いのでしばらく音楽を聴きながら休んで再度測定したら, 先ほどより多少は緊張がましになったのか心拍数110, 上140までは下がったが, 依然高血圧水準である.
それ以上緊張に改善がみられなさそうだったのでその旨を伝えたところ, 担当の方も緊張が一番の原因だろうというとのことで, もし心配なら家庭用血圧測定器を貸すこともできるという話をしてもらった.
いずれにせよ今日はもうできることも無いので帰宅. どっと疲れたのでそのまま早めに就寝

2023/6/3 (土)

日中は野暮用を済ませたり寝たりしていたら終わった.
夜はABC304

A: 始点を求めてそこから順に出力.
B: 場合分け. 最初のやつ以外はforループで省エネ.
C: BFS.
D: 最初2個の次元を一個ずつ処理しなければと思って実装に手間取ってしまった. よく考えたら各苺がどのピースにのるかは単にlowerboundするだけで良かった.
E: $x,y$ の代わりに, これらのdsu上のleaderをくっつけたり判定に利用したりすれば良い.
F: シフト表を周期ごとに折りたたむイメージで約数系包除. modを取り違えていてペナ+時間を喰ってしまった.
G: 考えたけど不明.
Ex: 後からupsolve. トポソして条件式を厳しくして貪欲.

今回提出からのresponseがかなり遅く, 後ろ二問を考えている間にどんどん状況が悪化してきたので早々に撤退してしまった. どうやら再び攻撃を受けてしまったようでunratedになったようだ.

その後はtwitterを眺めてたら一日が終了.

2023/6/4 (日)

7:30起床. あさかつARC.

ooooo(2o)
1: 左から順にその場所におけるカードの枚数を掛ける. (置くカードが指定されている場合は1)
2: $\min L$ と $\max R$ だけで値が決まる.
3: 前 $K$ 項から追い出すのは $1$ 枚だけとして良い. 追い出すカードを決め打ちすれば, そのカードを $K$ 番目に持っていく+後ろ $N-K$ 枚で決め打ちカードより真に大きいもので最も左のを $K+1$ 番目に持っていく $+1$ 回で目標達成.
4: 最終的なmexを決め打ちすると, 操作で書かなければいけない整数が決まり, 残りの操作で書く整数は自由に決められるのでその分は重複組み合わせ.
5: 初期状態で操作できない人が異なる荷物を持っていたら詰み. そうでなければ, 体重の軽い人から貪欲に正しい荷物を持っていく. (最小性は明らかで,体重が軽い人が持てていた荷物はそれより体重が重い人が持っても疲れないので正当性もOK)
6: $(2,1,3,4,\dots,N)$ と $(N,N-1,N-2,N-3,\dots,1)$ を組み合わせれば, 操作は $1$ 点に $+1,1$ 点に $-1$ をするに置き換えられる. 回数的にも十分なので, 全て等しくできる場合はこれをする.

午前中は数学をした.

午後からは西公園で日本酒のイベントをしていたので繰り出した.
これは, 東北を中心として多数の蔵元が屋台を構えているのでチケットと引き換えに利き酒ができるというイベントである. 毎年気になっていたが今回やっと出向くことができた.
飲んだのは以下の日本酒たち.

[気が向いたら写真を入れる]

しぜんしゅ純米原酒 (多分. 写真撮り忘れ): 仁井田本家(福島)
七郎兵衛純米吟醸: 竹浪酒造店(青森)
百磐純米吟醸: 磐乃井酒造(岩手)
濁酒: 大倉本家(奈良)
米鶴純米酒ピンクのかっぱ: 米鶴酒造(山形)

どれも美味しかったが, 個人的には最初のが一番好みであった.
その他豆腐を食べた. これも豆ゝしくて美味しかった.

帰宅後は酔い覚ましにPAST第14回を走った.

A: (N+S+T)の偶奇.
B: C++だと若干面倒?
C: IP[P[i]]=i
D: アイテム2は先に使う方が良いので使う回数を固定して考えられる.
E: 各行ソート
F: |S|+|T\S|
G: 全列挙してソート. なぜこの位置?
H: 小さい方から貪欲に組み合わせてよい.
I: ハンドを全探索.
J: シフトを全部試す. 一致判定は各行z_algを先にしておけば良い.
K: 後ろからDP. ペナルティの効力が1ラウンドのみなことに気づかずサンプルが合わなかった.
L: 入次数0で辞書順最小を貪欲にとる.
M: セグ木上二分探索.
N: 答えで二分探索して後ろから判定.
O: RUQ&RSQの遅延セグメント木をたくさん持つ. 実装に手間取ってしまった.

2023/6/5 (月)

7:30起床. あさかつARC.

ooo(1o)oo
1: 基本的に一要素だけ加算すれば良く, A_2を足す場合だけ偶奇によって[ tex: A_1] or $A_3$ に1加算する.
2: 愚直に, Tの要素が来るまで最短のシフトをすれば良く, 答えが存在すれば高々 $N+M$ 程度なので大きくなったら打ち切って $-1$ .
3: 答えで二分探索. 同じindexに $+a,-b$ をどっちもする場合考察が壊れるけど最適性が示せそうな雰囲気はあったので投げた.(後から考えたらそれはそうだった)
4: 初期状態の表裏が異なる隣接頂点の数 $+v_1$ が裏か表かが答え. 最初何も考えずに毎回隣接頂点全部調べてしまいペナ. 表頂点の次数の総和から表同士をつなぐ辺の本数の2倍を引けば良い.
5: $N$ が偶数の時, 後手の目的は総XOR=0であり, 後手がまねっこ戦略できるなら後手必勝. そうでない場合先手が一つの山の石の個数が最大になるように置き続ければよい. $N$ が奇数の場合, 後手の目的は総XOR $\neq0$ であり, 最初に先手が置いた山に最も多い石を積み続ければよい.
6: 差分と先頭を決めれば全体が決まる. また, $S_1$ での1の有無をflipすると1の個数は $k\to N-k$ に変化する( $2,3,\dots,M$ の有無も同様). よって, $S_1$ を全て試したときのスコアの総和は $N^M$ . 後は差分 $M^{N-1}$ 通りを掛ければよい. 考察9.9割実装0.1割みたいな問題だった. (実装はC++で10行)

日中は数学.

夕方からはICPCのチーム練をした.
ICPCやJAGの問題は結構解いてしまっていたのでこどふぉGYMの上の方に生えていた3時間コンをすることに.
https://codeforces.com/gym/104393

想定の数倍簡単セットで, 読解の方が時間のかかる感じであった.
特に面白い問題もなく全完.

その後帰宅しようとしたところ, サークル棟の扉が, あかない.
この建物は何故か外側から鍵を閉められると内側から開かない仕様であり, 他のサークルの人が鍵を閉めて帰宅してしまったようだ.
どうしようも無いので警備員室に連絡し, 外から鍵を開けてもらった. (~~何を思ってこの建物はこの仕様になっているんですか~~)

帰宅後, トマト茄子マッシュルーム鯖缶でパスタを作った. とても美味しく作れたが, 分量をミスって美味しく食べられる量を超すか超さないかくらいの満腹になった.

2023/6/6 (火)

2限の時間から大学へ向かう.
引き続き層についてで, 本日のメイントピックは脆弱層について.
午後からは控室で院試の過去問を解いた.
今回もごっつい積分やら二項係数やらを組み合わせた等式の証明があったのでそれを解いてみた.
この手の問題は見掛け倒し度が強く, 少しガチャガチャしたらいい感じになりそのまま解けた.
本番は解けなかったら時間を喰ってしまうし, 解けたらすぐ解けて良いしで解くか手を出すか迷う問題である.

夕方からはサークルのバチャ.
前の9問が実装が軽い問題ばかりでするする解けたと思いきや最後の橙が解けずに1時間椅子を暖めてしまった.
$O(n^4)$ を $O(n^3)$ に改善したかったが, どうやら本質的な部分を見抜けていなかったらしいのでまた日を開けて改めて考えることとする.

その後さわきで焼き鳥丼を食べて帰宅.

2023/6/7 (水)

ほぼ一日数学をしていた. セミナーの範囲をしばらく考えていたが, 結局詰め切れず, 他の参考書を見ても議論の回し方の順番がテキスト本とかなり違っており, 困った. そちらを全てきっちり追うのにはあまりにも追加準備が必要となってしまうのでざっくりとしたアブストだけ述べることにして就寝.

2023-05-25

2023/5/18~2023/5/24

日記

サークルの先輩が実に日記をつけていて良いなと思ったので今日から日記をつける.
過去に日記三日坊主経験もあり性格上長続きしない気がするがとりあえず続くところまで.

2023/5/18 (木)

8:30頃起床. ゴミ出しを済ませたり布団で本を読んだり朝ごはんを食べたりをし, オンライン講義の2限を受けるためPCに向かう. しかし, 勘違いをしており講義は1限であり, 既に終了していた. 出席等の概念は無いし, 講義ノートや動画が後からGCにあがるので被害は軽微.

その後はセミナー発表の確認をした後昼頃に青葉山へ.
昼食に豚野菜炒め丼を食した後, 原稿の確認をしていたらより簡潔な証明ができる場所を見つけたため修正.

15:00 からは四年セミナー. メンバーは5人であり, 2冊の本に分かれている. 木曜は楕円関数論に関する本で, 私ともう一人がこちらの班に属する.
そのもう一人が今日は都合でお休みだったため, ソロライブとなった.
本の流れ的には代数多様体の正則な点での局所環に離散付値を入れる話であったが, 相方が休みのこともあったので本の内容は余り進めずに離散付値環周りの話をした.
発表と担当の先生からのコメントを合わせて2時間半くらい.

その後友人宅に寄り道したのち帰宅. 適当な夕食を済ませた後, 競プロの精進をしようとして, そういえば昨日AtCoder黄色diffを埋め終わったことを思い出しTweet.

黄色以下を埋め終わった!! pic.twitter.com/ynd0ohkr2u
— 仮の人数学+競プロ (@kari_math) 2023年5月18日

結構反応がもらえてちょっと嬉しかった. (いつもよりFF外からの反応も多いのは先日に若干注目されたTweetをしたためおすすめとかに出やすくなっていたとかあるのだろうか?)

ここ数日していた黄diff埋めが終わってしまったので適当な橙diffを解くことにした.
F - Sorting a Matrix
これはコンテスト中にSubmitはしたけど解けていなかった問題.
改めて考えると, まず列と行を独立に考えて良いことに気づく.
行の並べ替えの方は簡単で, 列の方は少し厄介.
列の組で片方が片方の左側に来るといった制約が生えるので, それらが全て満たせるか, すなわち制約を有向辺と思ったときにDAGかの判定をすれば良い.
ただし, 愚直に辺をはると, 最悪で $\Theta(HW^2)$ 本もの辺が生えて大変なことになるので超頂点を適当に設けて回避する.
これらの方法は大体公式解説のものと一緒だった.

その後は布団でぐーたらしていたが, そのまま寝るのも味気なかったのでこどふぉのバチャをすることにした.
https://codeforces.com/contest/1800

A: Is It a Cat?

入力では大文字小文字の区別があるが, その後は区別する必要が無いのでまず大文字を全て小文字に変換しておく.
後は文字列を前から見ていって, "meow" の何文字目までが出現したかを見ていけばよい. 見ている段階で現れてはいけない文字が出てきたかも同時に判定する.
後から思えばランレングス圧縮的な方針の方が楽だったかもしれない.
https://codeforces.com/contest/1800/submission/206348403

B: Count the Number of Pairs

まずペアがあれば貪欲にペアにしてよい.
これが終わると, 各文字に対して, 大文字と小文字の一方のみが残る. そのうちの半分をもう一方に変換するのがペアを最大にする方法なので, 変換回数が残っている限りこれをする.
https://codeforces.com/contest/1800/submission/206348735

C1,2: Powering the Hero

操作を言い換える.
bonusカードを全て山に積み, heroカードが出た時は山に積んだbonusカードから好きな一枚を選ぶとする.
一見できることが増えているようだが, これで選びうるbonusカードの集合は元のルールでも選ぶことができることは容易に分かる.
言い換え後の操作では明らかに山に積んだbonusカードから最も大きいものを選べばよく, これは優先度付きキューなどで実装できる.
https://codeforces.com/contest/1800/submission/206349053

D: Remove Two Letters

最初は, 異なる箇所から2文字除いて, 同じ文字列となるのは, 同じ文字が連続する箇所だけかと思ったが, これは最後のサンプル ("ababa") で棄却される.
次に, ローリングハッシュを使うことを思いつく.
2つの文字列の連結も, 適当な冪を掛けることで可能なので, 取り除く $N-1$ パターン全ての文字列のハッシュ値を $O(N)$ で求めることができる.
ハッシュ値を決める多項式において, 冪の並ぶ順番を逆向きに勘違いしていたせいで実装に苦戦してしまった.
https://codeforces.com/contest/1800/submission/206353874

E1,2: Unforgivable Curse

まず隣合う二文字がswapできるかを考えたい.
一番swapさせにくいのは真ん中の文字であるので, これとその隣がswapできる条件というのを探ることにする.
すると, 真ん中の文字が1回でも動かせれば, その隣の文字とのswapが可能と気付く.
手順は以下の通り. (真ん中の文字 $s_m$ とその左隣 $s_{m-1}$ をswapする場合)

$s_{m},s_{m+k}$ をswap
$s_{m-1},s_{m+k}$ をswap
$s_{m},s_{m+k}$ をswap

これで, 元の状態からは $s_{m},s_{m-1}$ のみが入れ替わることになる.

真ん中以外もほぼこれと同様に出来るので, 結局1回でも動かせるもの同士は任意にswap可能.
(これはバチャ中にこう思っただけで, 実際には動かせる文字, 動かせない文字, 動かせる文字が並んでいる場合に動かせる文字同士をswapできるかはこの段階では非自明であるので別途証明する必要がある. )

よって, 動かせない文字の場所が2つの文字列で一致しているかを判定すればよい.
https://codeforces.com/contest/1800/submission/206349991

F: Dasha and Nightmares

この問題は結構好きである.
まず, 使わない文字を1つ固定すると, その文字を含まない文字列同士の組で, それ以外の文字は全て計奇数個含むようなものを数えればよいことになる. (文字列長の偶奇は自動で満たされる.)
まず, 使わない文字を含む文字列は省いておく.
各文字列について, どの文字を奇数個持つかを表す集合を用意して置くと, 二つの文字列がペアになれる必要十分は, それらの集合が交わらないかつ, 和集合が全体になることである.
よって, 集合をbitで管理するなどして, 連想配列に入れる等すれば良い.
固定した使わない文字を変えた時に同じ組を重複して足す恐れはないため, 単純に足し合わせればよい.
https://codeforces.com/contest/1800/submission/206355184

G: Symmetree

問題名が好き.
解法自体は, 各頂点に対して, その頂点を根とした部分木が左右対称かを木DPでボトムアップに求めていけばよい.
遷移の際に, 木の同型判定が必要なので, 事前に各部分木のハッシュ値を求めておく.

木DPの遷移は, 各子のハッシュ値を並べ, 同じもの(=同型なもの)があれば, ペアにする.
その後は,

ペアにできなかったものが複数あれば, 左右対称でない.
ペアにできなかったものが1つあれば, その残った子の部分木が左右対称かに依存する.
ペアにできなかったものがなければ, 左右対称である.

という判定ができる.
木の同型判定パートは実装が簡単な $O(N\log{N})$ の決定的なものでも余裕で間に合って良かった.
https://codeforces.com/contest/1800/submission/206358160

総括

91分全完32位. 良い方な気がする. Cの後間違えてEを開いてしまったが, Dの方が時間がかかる問題だったため, 結果としてスコアが良くなった.

その後この日記に解法をメモって就寝.

2023/5/19 (金)

6:30起床. 朝食身支度を済ませて大学へ向かおうとした瞬間雨が降り始めた. ただでさえ混む地下鉄がより混んでいてややげんなり.

1限から昼過ぎまでは4年セミナー.
今日はSerreの『数論講義』(の英語版)を読む班で, 昨日あった楕円関数論班でない3人がこちらに属する.
私はこの本を和書版で3年講究セミナーをしていたのでしばらくは既習内容が続く.
そのため, 適度に助け船とかを出しやすいというメリットはあるのだが, 早起き+ある程度既知の内容を聞くということで睡魔と闘う必要もあり大変.
今日は $Q_{p}$ の乗法群まわりの話だった.

13時頃にセミナーが終わり, 辛口カレー丼を食べた後下山.
どうやら同級生が卒業アルバムの写真を撮りにいくらしいので便乗することにした. 相変わらず眼鏡のせいで限界まで顎を引くよう指示されてしまうのでかしこまった写真は苦手である.

この後は睡魔が限界になってきたので帰宅して仮眠をとった.
19時頃に起床して夕食.
この日は試しに冷凍させていたもやしを使うことにした.
買い物した後しばらく数日バタバタすると足の速いもやしが痛んでしまうので冷凍もやしを試してみて良さそうなら購入後即冷凍することにしようという魂胆である.
調理方法はひき肉と卵でとじながら炒めて中華調味料で味をつけるというシンプルなものにした.
結論から言えば十分美味しく食べられるが, 冷凍しないものからは遥かに劣るといった感じであった.
もやし内の水分が凍って解凍時に流れるようで, シャキシャキ感がかなり弱まってしまった.
消費期限が迫ってきたら冷凍庫で数日延命くらいの向き合い方が良さそう.

夕食後は昔買った小説を読んでいたが内容があまり面白くなかったので今日もこどふぉのバチャをすることにした.

https://codeforces.com/contest/1811

A: Insert Digit

前から見ていって, 追加する数より真に小さい数が現れたらその直前に追加するのが最適である. そのような箇所が無ければ末尾に足す.
https://codeforces.com/contest/1811/submission/206475276

B: Conveyor Belts

外周からの距離の差を考えればよい.
https://codeforces.com/contest/1811/submission/206479563

C: Restore the Array

両端は直ちに分かる.
それ以外のところは, $a_{i+1}=\min(b_{i},b_{i+1})$ とすれば良い.
この変換は, $b_{i}\le max(a_{i},a_{i+1})$ を $b_{i}\le a_{i}$ かつ $b_{i}\le a_{i+1}$ と思うと気付きやすい.
こうしてできた数列が条件を満たすとは限らないが, 今回は条件を満たす数列が存在することが制約で保障されているのでOK. https://codeforces.com/contest/1811/submission/206481969

D: Umka and a Long Flight

各サイズの正方形は2個以下とあるが, この制約を満たそうとすると, $n+1$ 個のピースは1辺を $F_{1},F_{1},F_{2},F_{3},\dots,F_{n-1},F_{n}$ とするものに限られる.
さらに, これらの正方形の位置を決定しようとすると, 可能性は左右(上下?)のどちらかに詰めて配置するしかない.
すると, 残りのマス目及び正方形は, 全て $n$ を $n-1$ に置き換えた状況になる.
また, ここで配置した正方形に, $(x,y)$ が重ならないような配置は, 存在するなら1つだけである. (すなわち左右どっちに詰めるかで再帰的に場合分けが増えることはない.) https://codeforces.com/contest/1811/submission/206490500

E: Living Sequence

この位置の問題としてはかなりeasyに感じた.
10進法の数が与えられるので9進法に変換するだけである. (ただし用いる数は4を除いた9個の数)
https://codeforces.com/contest/1811/submission/206493130

F: Is It Flower?

問題文が弱い上にサンプルが不親切(YESケースをもう一個置いてくれ～～)だったので飛ばして結局戻ってこなかった.

G1,2: Vlad and the Nice Paths

DP $\lbrack c \rbrack\lbrack i \rbrack\lbrack k \rbrack$ を, 既に $i$ ブロックが決まっていて, 色 $c$ を $k$ 個目まで列を作っている場合の数として定める.
但し, 丁度 $i$ ブロック作り終わった状態というのは別で持たせておく.
これは一見状態数 $O(n^3)$ , 遷移 $O(1)$ で間に合わないような気がするが, 作れるブロックの数が最大で $n/k$ 個なので, 状態数 $O(n^2)$ , 遷移 $O(1)$ となって間に合う.
しかし, この方法には一つ問題があり, mod をとった後 $0$ となったのかもともとが $0$ なのかが区別がつかないのだ.
そのため, 同様の方法で, 存在/非存在のみをbool値でもたせるDPを追加したが, これがかなり大変だった.
二つのDPを同時にするとMLEしてしまい, 分けるとTLEしてしまい, お茶を濁したらWAになった.
結局, 定数倍高速化+二つのDPを分けるという方法でなんとかなった.
https://codeforces.com/contest/1811/submission/206539959

総括

7完7ペナ106位. G問題があちらをたてればこちらが立たずでとても苦しかった.

バチャが終わったらdiscordに人がいたので雑談を聞いた後就寝.

2023/5/20 (土)

起きたら15:00で布団でごろごろしていたら19:00に. 買い物と夕飯を済ませたら20:00を過ぎていた. ABCにも出ずにそのままグダグダしていた.

2023/5/21 (日)

午前はセミナーの資料作りをした. 夕方ごろから前日のABC302のバチャをした.
https://atcoder.jp/contests/abc302

A: Attack

切り上げ.

B: Find snuke

8近傍直線探索.
dy={1,-1,0}, dx={1,-1,0} として, $3\times 3$ の方向を探索すると楽.

C: Almost Equal

順列全探索で通る.

D: Impartial Gift

$A_i$ を固定したら $A_i+D$ 以下の最大の $B_j$ を選ぶのが最適.
考えるよりコピペで書くのが早そうだったので $B_j$ を固定したverも書いておいた.

E: Isolation

次数を愚直に管理する.
削除される辺の本数の総和は高々追加された辺の本数の総和であるので十分少ない.

F: Merge Set

集合の番号と集合に含まれる数の間に辺を張ると最短経路に帰着される.

G: Sort from 1 to 4

1,2,3 のスワップで正しい位置に来るものをカウントしておくと, 少ない方から貪欲が最適らしい. かなり早解きされていたので投げたら通った.

Ex: Ball Collector

UndoDSUを持っていなかったので人のコードを見ながら整備も兼ねて解いていたら細かい所を詰め切れず時間切れになった. 後からAC.

21:00 からはAGC062に参加. 1完で激冷え.

AGCがあまりにも悔しかったのでその後こどふぉのバチャをした.
https://codeforces.com/contest/213

A: Game

コンピュータ間の移動が複雑なようだが, 実は $1\to2\to3\to1\to\dots$ の移動のみで良い.
また, できるタスクがあれば常にしてよい.
よって, 最初のコンピュータを決め打ったら後は貪欲に出来る仕事をしながら上記の移動をするのが最適となる.
https://codeforces.com/contest/213/submission/206763377

B: Numbers

先頭の数を固定する.
DP $\lbrack i\rbrack\lbrack j\rbrack$ を, $0,1,\dots,i$ まで数字を計 $j$ 使ったときの, $\prod_{k=0,1,\dots,i}\frac{1}{b_{i}!}$ とする. $b_{i}$ は数字 $i$ を $b_{i}$ 個使うことに対応する.
条件を満たすようなところだけ遷移させれば目的の値が得られる.
https://codeforces.com/contest/213/submission/206764701

C: Relay Race

良くあるグリッド上のDPで, 現在地の情報を2点分持たせて更新すればよい.
その時, 同じ位置を通ったかの処理が面倒になるので, 常に2点の, $x$ 座標 $+y$ 座標が同じ値になるように遷移させていく.
また, なんかバグらせを踏んでしまったので, 始点と終点の両側からDPして, 真ん中で結果をマージした.
https://codeforces.com/contest/213/submission/206767288

D: Stars

水平に $N$ 本分対角線を一直線に引き, 始点に戻りながら星を形成していく.
https://codeforces.com/contest/213/submission/206769844

E: Two Permutations

時間が足りず見ていない.

総括

4完で30位.

その後就寝.

2023/5/22 (月)

8:30に起きてゴミ出しやら掃除をした後, セミナーの資料作成の続きをした. 週末中に完成させるつもりが怠惰していたら月曜になってしまい申し訳なさみ.

昼過ぎからはコドフォのバチャ https://codeforces.com/contest/1833

A: Musical Puzzle

連続二文字をsetに突っ込んでサイズを出力.
https://codeforces.com/contest/1833/submission/206798484

B: Restore the Weather

$a,b$ をどっちも昇順に並べればよい.
https://codeforces.com/contest/1833/submission/206798658

C: Vlad Building Beautiful Array

偶奇を固定する.
すると, 目標と偶奇が一致していない場合, 奇数を引くことで調整しなければいけないが, この奇数は最小の物をとればよい.
実際は, 奇数の有無等で最終的な偶奇も一方のみが適することが分かるがどっちも試しても問題ない.
https://codeforces.com/contest/1833/submission/206798981

D: Flipper

$N=1$ の時は良い.
基本的には, $N$ を先頭にすることができる. これができないのは, もともと先頭が $N$ の時で, この時は先頭が $N-1$ となる.
先頭が決まれば, それを先頭に持ってこれるような $(l,r)$ の組は $O(N)$ 個となるので, 全て試して辞書順最大を求めればよい.
具体的には, 先頭に持ってきたい数のindexを $m$ とすれば, $r=m,m-1$ の時が適する.
https://codeforces.com/contest/1833/submission/206799709

E: Round Dance

隣り合う人に辺を結ぶと, サイクルかパスとなる.
サイクルはそれ以上手を施すことができず, パスは他のパスとつなげるか, 両端を閉じてサイクルとするかを選べて, 前者をたくさんすれば最小値を与え, 後者をたくさんすれば最大値となる.
https://codeforces.com/contest/1833/submission/206800237

F: Ira and Flamenco

現れる数を重複を取り除いて昇順に並べた物を $p_{1},p_{2},\dots,p_{k}$ とする.
すると, $p_{i+M-1}-p_{i}=M-1$ となるような $i$ に対して, $p_{i},p_{i+1},\dots,p_{i+M-1}$ の値を持つ人を一人ずつ連れてくれば良い集合になって, またこれに限る.
後は各値を持つ人を数えておいて人数の累積積を用意しておけば各 $i$ に対して $O(1)$ で組み合わせ数を計算できる.
https://codeforces.com/contest/1833/submission/206800718

G: Ksyusha and Chinchilla

木DPで葉側から貪欲に枝を作っていく. 子の頂点のうち, いくつが枝に属していないかを計算していく.
枝に属さない子が多い場合は枝分割が不可能. そうでない場合は, 上に持ち上げる.
https://codeforces.com/contest/1833/submission/206801566

総括

ノーペナ全完12位!! 素晴らしい!!

適当に夕食をとった後, TLに流れて来た問題を解いたり院試の過去問を解いたり.

院試は東北大のH26年度.
解析が若干面倒だが後は簡単目な気がした. 位相やその他枠が簡単なので望む傾向とは結構離れて居るけど解けたっぽいのでヨシ.

就寝前にこどふぉのジムにある良く分からんコンテストのバチャ

Dashboard - Олимпиада школьников РС(Я) (5-8 классы) 2022-23, 1 день - Codeforces

ルールが分からんのでコピペなし, 翻訳機OKとした.
難しくは無いし, これと言って面白い問題も無かったので詳細は書かないことにする.

2023/5/23 (火)

7:30 起床. あさかつに出る. まずはあさかつARCから
あさかつARC
A: Sum and Product O(sqrt) のいつものやつである. 積の方が圧倒的に候補を絞りやすい.
B: Copy and Paste Graph ワーシャルフロイドで, 対角線の初期化をしなければ良い.
C: String Invasion 前からみて, 同じ文字が2つ並んでいたらその文字に何回変更するかはほぼ残り文字数で決まる. 変更予定の文字と同じ文字が出てきたらごにょごにょする.
D: Swaps 2 A_i+i が操作によって変わらないことが分かる. よって, この変換をすれば, 単に隣接swapで並べ替えられますかという問題となる.
E: I Wanna Win The Game 2進法の下の桁から決めるDPをする.
総XORが0というのは全ての桁でbitが立っているような変数の数が偶数個という事である.
下から何桁確定させて, 今の総和がいくつの場合の数を持っておく.
遷移は対称性を生かして二項係数で計算できる.
F: LEQ and NEQ 1週間前くらいに解いたので解法を覚えていた.
stackを使って包除原理させながら遷移をする.

その後時間が余ったのであさかつnotARCの方にも出たがラスト問題の実装が間に合わなかった.

シャワーを浴びた後青葉山登山.
2限は代数の講義で, 前回から層の話に入った.
前回休んだことをすっかり忘れており, 1回分のブランクがあったので話についていくのが大変だった.

昼食後は資料室に行って本を漁った後, 学生室で競プロと院試の勉強をした.
競プロはLibrary Checkerを適当に解いた. LCAをずっと人のをパクっていたので一度一から書き直して, Jump on tree にも対応させた.
院試は東北のH27の共通を途中まで解いたところで飽きたのでH26の専門を解いた.
代数2問はとんとん解けて残りの一問は見た目が面白かった大問6を解いた.
二項係数に関する問題で, 非自明な結果が出てきて見た目に違わず面白かった.

下山後サークルの定例会.
最後の問題が面白かったが途中嘘考察をはさんでしまったまま実装してしまって間に合わなかった.

帰宅後布団にごろんてたら転寝してしまい, 目を開けた時には一日がほぼ終了していた. かろうじて買い物に行き, そのまま就寝.

2023/5/24 (水)

昼頃起床.
数学等をした後, 2時頃からこどふぉバチャ

https://codeforces.com/contest/1816

A: Ian Visits Mary

1回で行けない場合, $(x-1,1),(1,y-1)$ のどっちかを挟めば2回で到達可能.
https://codeforces.com/contest/1816/submission/207007845

B: Grid Reconstruction

各マスを通った場合正の寄与か負の寄与かは一意に定まる.
正の寄与に大きいのを配置し, 負の寄与に小さい値を配置.
後はいい感じにしたら通った.
https://codeforces.com/contest/1816/submission/207008190

C: Ian and Array Sorting

奇数の時は, 上手く操作すると, 一点加算, 一点減算ができるので, 任意の数列を昇順にできる.
そうでない場合, 一点操作ができないため, 端から貪欲に前 $n-1$ 項が等しくなるように操作をしたのちに最後の一項が小さくないかを判定すればよい.
https://codeforces.com/contest/1816/submission/207008695

D: Sum Graph

面白い.
$x=n+1,n$ をすると, グラフが直線グラフになる.
その後の $n-1$ 回のクエリで, 端を確定させる.
その後の $n-1$ 回のクエリで, 端からの距離を確定させる.
これで, 確定させた端がどちらの端にするかによる2パターンの順列が求まる.
https://codeforces.com/contest/1816/submission/207010807

E: Between

$b\to a$ で辺を張り, 頂点 $1$ から最短経路距離 $+1$ を求めると, これが数列にその数字を置ける数の最大値になる.
ただし, 到達できない頂点があれば答えはINFになる.
最大値を求めた後は, 以下の通りに配置すればよい.
丁度 $n$ 個配置する数の集合を $D_n$ とすると,
$D_m\to D_{m-1}\to D_{m}\to D_{m-2}\to D_{m-1}\to D_{m}\to\dots,D_{1}\to D_{2}\to\dots D_{m}$
とすれば良い. 但し $m$ は適当な最大値.
https://codeforces.com/contest/1816/submission/207012305

F: XOR Counting

$m=1$ の時は考えることは無い. (mod とり忘れでぺなったけど) $m\gt 2$ の時は, $n$ との偶奇が一致している $n$ 以下の数が作れる全て.
( $a,\frac{n-a}{2},\frac{n-a}{2},\dots$ とすればよい. )

$m=2$ の時は, $1$ の位から再帰的に確定させる.
https://codeforces.com/contest/1816/submission/207013893

総括

途中でdiv1があることに気がついた.
高レート帯の人がそっちに出ているのでdiv2順位表で相対的に超高順位となった.
全完5ペナ3位.
div1の方に放り込んでもかなり上位な結果で満足.

夜はサークルの新歓があった.
新入生が結構来てくれてとても嬉しい. 競プロのことはもちろん数学科のこととかも結構話した.

帰宅後豆乳を飲んだら頭が痛くなってきたので気分転換にこどふぉのバチャをした.
https://codeforces.com/contest/1594

A: Consecutive Sum Riddle

良くある二冪の奴ですね～と思ったら負も許されていたので $l=-(N-1),r=N$ でOK.
https://codeforces.com/contest/1594/submission/207053264

B: Special Numbers

2進法展開して $2^k$ の代わりに $n^k$ を掛ける感じ.
https://codeforces.com/contest/1594/submission/207053700

C: Make Them Equal

$gcd(n,n-1)=1$ であるので, 最大でも2回で達成可能.
よって, 1回以下で出来うるかを判定すればよい.
変更する必要のある箇所を変えられるindexの集合に共通部分があるかを判定すればよく, これは補集合をとって, 変更できないindex集合の和集合が全体にならないかを判定する方が楽.
https://codeforces.com/contest/1594/submission/207054536

D: The Number of Imposters

clue判定がされたなら, 嘘正直問わず, 指名した人された人は同じ陣営.
impo判定がされたなら, 嘘正直問わず, 指名した人された人は異なる陣営.
この時点で矛盾が生じたらその時点で切る.
よって, clue判定された人同士をdsu等で一つのまとまりにマージした後, impo判定された関係で辺を張って, 二部グラフかを見ればよい.
二部グラフであれば, 大きい方の集合をimpoとしてよい.
https://codeforces.com/contest/1594/submission/207055767

E: Rubik's Cube Coloring

easyの方は1か所自由に決めれば後は4通りから選べる.
hardの方は分からんかった.

F: Ideal Farm

$s,k$ を決めた時に, 条件を満たさない最大の $n$ を考える.
これは, $s+1$ 個のマスがあり, $0,s$ マス目は黒くなっている. $i$ マス目と $i+k$ マス目の少なくとも一方は黒く塗らない.
最大で何マス黒く塗れるか? という問題になる.
$2k$ マス毎をブロックとすると, 各ブロック中前より $k$ マスは黒くでき, ブロックに含まれない $(s+1)%(2k)$ マスの内, $k$ マス以下なら黒く塗れる.

https://codeforces.com/contest/1594/submission/207061188

その後このを日記書いていた.
初週なので書くことが定まっていない感が強い.
初日なんかは精進で解いた問題についても触れていたが, 以降はバチャの形で解いたものしか触れていなかったりする.
ここら辺の塩梅はだんだんといい感じにしていきたい.

2023-05-05

HUPC(Hokkaido University Competitive Programming Camp) 2023 day1 参戦記

ソロオンライン参加 9完10位

各問題の考察内容

ここでの問題順番はAC順.

B: Merge Sequences

$NM$ 個を全て列挙は当然できない. そこで, 大きい $K$ 個のみを列挙しなければならない.
列挙する必要がある数のうち, 最小の値が分かっていればそれ以上の値になるものだけを列挙すればよくなり, 判定も構築も二分探索でできる.
かなり典型度が高い問題なので実際は考察を挟まず実装に手を付けた.

C: Range Same Query

全て等しいことと, 最大値 $=$ 最小値に気づけるかが肝.
前者は基本的には範囲内の全ての要素を確かめなければいけないが, 後者は最大値と最小値の $2$ つの値のみを高速に取得できればよく, segment木を使えば一点更新とも相性ばっちり.

A: Converse and Inverse

二つの操作を同時に考えると大変なので一つずつ操作を吟味する.

長さが $3$ 以上なら区間上下反転で一点上下反転ができる. ( $s_x$ を反転したければ $\lbrack x,|s|\rbrack\to\lbrack x+1,|s|\rbrack$ のように上下反転を $2$ 回行えばよい. $x$ が大きい場合は反対側に寄せる.)

よって, 文字列の長さが $2$ か $3$ 以上かで場合分けをする.

文字列の長さが $2\to$ 操作を全探索
文字列の長さが $3$ 以上 $\to$ 最後に一点の上下反転ができるのでpとb, qとdを同一視してよい. (以下全てp,qに統一.)

これで扱うべき文字種が減ったので見通しが良くなる.
しばらく, 転倒数や偶奇ごとのp,qの数の方針で攻めたがあまり筋が良さそうでない.
次は操作の可逆性から考える.
左右反転の操作は可逆なので, $s,t$ をそれぞれ操作するとして良く, 特に特徴的な形に変換できるか考えればよい.
今回の考察で特徴的な形として一種類の文字のみからなる文字列を採用した.
すると, すぐに以下のことが分かる.

左右反転については, 同じ文字が並んでいるところがあればそれを中心に全体をその文字にできる. (q"pp"qp→"qqqq"p→ppppp)

後は, pqpqpq... のように交互に並ぶ場合であるが, "pqp"q...→qpqq... とできるので, 文字列長が $4$ 以上であれば交互でない場合に帰着できる.
文字列長が $3$ だと pqpかqpqにしかならない.

これで全ての場合の考察が終わったので場合分けや判定を実装してAC.

F: Euler Query

直感的には $\varphi(z)=x$ を満たす $z$ を探しまわるのは困難そう.
そこで, 操作が可逆な事を利用して, $x,y$ を $\varphi(x),\varphi(y)$ に置き換える操作と考えることにする.
ここまでくると, かなり最小共通祖先の香りがしてくる.
実際, $1\le \varphi(n)\le n$ で, $n\gt 1$ の時は二つ目の不等号の等号部分は外れるので, $\varphi(n),n$ に辺を張れば木になり, まさにLCAとなる.

I: Sum of Tree

問題をみてまず行列累乗かな? と考えた. その後に制約を見て行列累乗だと TLEする場合が有りそうとなった.
経験則からこういう変な制約が見えている時は複数方針を組み合わせれば良く, (cf. ABC032-D: これは大分見え見えな例) 今回も愚直解と組み合わせればよい.
計算量を吟味せず, 行列累乗の方は $N\le 100$ 位だろうの肌間隔で投げたらTLEした.
$NK\gt 3e7$ のように, 愚直が通らないぎりぎり位にちゃんと照準を合わせて無事AC.

K: Power Game

$3$ 枚くらいのカードで試すと, 初手の $x$ 以外の選択は結果に影響しないことが分かる. ( $a^{b^c}=a^{bc}$ なので)
よって, 最初の値の選択さえすれば良い.
カードの数の相乗を $S$ , 最初に選ぶカードを $x$ とすれば最終スコアは $x^{\frac{S}{x}}$ となる.
これは数学としての有名問題で $x$ が正の整数の範囲では $x=3$ で最大値をとる.
実際にスコアを求める時にも少し工夫が必要で, 繰り返し二乗法を使用するにも指数が大きくなりすぎるので, フェルマーの小定理から指数部分は $\mod{p-1}$ で求めれば十分な事を利用する.
~~このゲーム2回で飽きそう~~

J: Range Xor Query

範囲の制約が無ければ, BinaryTrie の典型利用例となる.
BinaryTrie での通常での minXOR の挙動を考えると, ある頂点から存在する子に向かうパートがある. 今回はこの時に, 単に子が存在するかではなく, 範囲内のindexを持つ子が存在するかを見るようにすればしたいことが実現できる.
indexの存在管理最初, 各頂点に直接子のindexの最大最小を持たせようとしたが, 特にlog倍を気にする必要もないので全ての頂点に set を用いれば良い.

M: Fish Tank

問題概要を整理すると多次元カタラン数の雰囲気がある.
カタラン数周りの概念で高次元に応用しやすそうな話題として鏡像法とヤング図形が思いついた.
鏡像法の方が出題されがちな気がするので先にこっちを考えたが, 上手く折り返せなかったのでヤング図形考察に移る.
最初は逆向きに考えていたため微妙に標準タブローでなかったが, 正しい方向にすると標準タブローど真ん中の形になった.
実はこの段階まで $M$ の制約を勘違いしていて実装がちょっと面倒そうと思ったが, よく見たら一個一個ヤング図形のフック長を計算できる制約だったのでありがて～になった. (後からよく考えたら $M$ が大きいと分数の分母にmodの倍数が来ちゃったりしてかなり面倒なことになる.)
フック長公式はもともと知っていたが余り日の目を見ない知識だったのでお目にかかれて嬉しみ.

H: Counting Repdigits

まず $N$ 以下のぞろ目数が昇順に ( $\mod p(=998244353)$ で) 列挙できる量なことに気が付く.
すると座圧のようなことができる. 隣合うぞろ目数の間隔を列挙しておけば, 問題の答えは, これらの間隔の積の和の形で表せ, さらに畳み込みによって高速化ができる.
持っていたNTTが遅かったり添え字があらぶったりしてしまったが, 何とか時間内に通せた.

どの問題も面白かった.
day2以降も楽しみ～～

2023-03-06

TUPC2022 開催記

はじめに
各問題の感想
準備について
おわりに

はじめに

　東北大学プログラミング2022を開催しました. この記事はその開催記と感想的なものです.

atcoder.jp

各問題の感想

　自分がWをした問題についてのみ言及. ネタバレや解法を大いに含みます.

B: Snowy Aobayama

　Writerをした. 簡単枠かつ大学ネタの入った問題を作りたかった. 少し捻りを入れたかったので $O(N)$ の素朴な解法から座圧的な事を要求する制約にした. 2問目に置くにしては難しかったかもしれないので $O(N)$ のままの方が良かったのかもしれない.
　実際にコンテストで自分が解きたいかと言われるとそうでないかもしれないが, 私はこのような問題が有志コンテストにあるとちょっと嬉しくなる. そんな問題にすることができたと思っている.

D: Zeta Sum

　Writerをした. 式の見た目が厳ついし難易度評価がムズすぎる. 出来てしまえば簡単だけど時間を掛ければできるかと言えばそうでもないし......
　この問題は賛否が大きく分かれそうだなと思っていたので感想ツイートで面白かったと言ってもらえたのを見つけて安心した. (もちろんそうでない感想もあったので次回以降もちゃんとバランスも考えないとなとは思いました.)

J: AMidA

　とても好きな問題なのでこの問題の制作過程も含めて少し長めに話す.
まず最初に対称群から問題を作ろうとした. (このころ体論, ガロア理論を学んでいたので.) 対称群で競プロ問題っぽくするならアミダクジとかが良さそうと思っているとamidaの中に数学で恒等的を表すのに用いられている "id" が潜んでいることに気が付く. ここで恒等的なアミダクジを題材に問題を考えようとなった. 色々問題設定を考えては自分で解いてを繰り返して取りあえず今回の問題で言うところの最小回数を求めるパートまでで良さげな問題となった.
最小回数を与える操作についても, どうすれば良いかまでは分かったが, 実際に実装する方法が分からなかった. 削除可能UnionFindで一応可能ではあったのでこれを実装してここまでの考えがあっていることを確認.
しばらくたっても解けなかったのでSota君に相談したところ, 色々なconectivityについてが書かれた記事を教えてもらい解決. 無事に今回の問題の形になった.

　これで問題が完成で万歳となるかと思いきやここからはテストケースづくりに苦労する.
逆マージテクをサボる解法は落としたかったが, これを落とすのが中々難しい.
というのも, マージテクサボりが落ちるのは, デカいサイクルからサイクルをちょっとずつ切り落とすケースであるが, 超意図的に作らないと中々これができない.
そこから, 少々の横線を追加したりシャッフルしたりは耐える(テストケースのstairarbがこれに相当)が, それ以上変化させると, 逆マージテクをしなくても結構通る.(stairに相当).
　その後色々試してはコードを走らせて実行時間を計測する中で, 作ることになるサイクルを先に作ってそれになるように横線を設定するという方法を思いつく.
しかし, これにも問題点はあり, 適当にサイクルを決め打ってしまうと, 横線の本数が $O(N^2)$ のオーダーになってしまう.
そこで, 横線の本数を $O(N)$ 程度に収められるようなサイクルを用意する必要があり, これは $\sum|i-p_i|$ を小さくすることを目指せば大体良い.
最終的には, $N$ を $X$ 個のブロックに分け, 各ブロック内でサイクルを作り, それをつなぎ合わせるという方法をとった. (permケースの前半)
ここまで作って満足していたが, どうやらこれだと削除可能UFや変更する頂点のすぐ近くだけ調べるといった方法で通ってしまうらしい.(全体testerのお二人に教えていただいた).
正直それらの解法は通ってしまっても仕方ないと思っていたが, permケースの $X$ の値を変えてみたり, 適当にシャッフルを加えたりしてみたらこれらの解法に対して強いケースとなった(permケースの後半).
こうしてこの問題は完成を迎えた.

　この問題は最小回数を求めるまでと, TLに間に合うように実装するところに2つ考察の山場がある. しかし実装は丁寧にやればかなり軽く, データ構造としてはvectorがあれば事足りる. testerのこたつがめさんの提出を参考に書き直したところ, C++で43行に収まった. これもお気に入りポイントである.
https://atcoder.jp/contests/tupc2022/submissions/39489976

準備について

　ここからは運営としての準備について書く.
次回以降の開催のためのメモとしての役割も持たせている.
各内容を思い出したら随時更新をする.

2022年8月頃

　TUPC2022というdiscordサーバーが生える.
メンバーが集まったところで役割分担をする.
役割は,

進捗管理: 全体のスケジュールや進捗をまとめる係
連絡係: 各所と連絡をとる係
技術係: rimeやgitの使い方の管理をする係

である.
この時点でメインwriterが4人, 有志コン経験が豊富なアドバイザーが2人といった運営パーティーとなった.

　その後2022年末くらいまではひたすら問題を生やす.
問題は, writerが問題設定や簡単なテストケースを作った段階で他のwriterにtesterをしてもらいながら問題をブラッシュアップといった流れ.
問題の作成はrimeで, 問題の管理はgithubで, 進捗の管理はスプレッドシートで, 問題の議論はdiscordの個別チャンネルで行った.

2022年末頃

　コンテスト開催形態について会議をする. 希望としてはオンサイトあり&AtCoder上開催であったのでその方向で調整をしていく. また, ICPCAsiaの折にhenoさんに全体テスターをお願いし, 承諾をいただいた.

2023年1月

　問題セットを一通り組んでみる. オンサイト会場も大学で話が付きそうとなったので, 実際にAtCoder側と連絡をとり, 日程が3月4日に決定.
　問題作成としても, 草稿状態だったものも含め全て一旦の完成状態とする.

2023年2月

　全体テスターからのフィードバッグをもとに問題を磨く. その他告知を出したり, 全体の会の流れを考えたり細かい準備を進める.

2023年3月

　問題の最終チェックをしたり, 同一のWifiから大人数がAtCoderのサイトに繋ぐのヤバイ!!ってなって慌てて連絡をしたり, 他コンテストによる問題爆破にひやひやしたりしているうちに本番を迎える.
　本番は開場から解散まで大きなトラブルもなく楽しんでもらえたようで良かった.

おわりに

快くサイトを利用させていただいたAtCoderの皆様, 全体テスターを引き受けていただいたhenoさん, ご参加頂きコンテストを盛り上げて頂いた皆様, ありがとうございました.
現在開催を目指しているTUPC2023もよろしくお願いします.