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 (水)

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