10/14(月)
午後5時起床。今日は祝日だが大学の講義は休みにならなかったようで、大学生協も変わらず営業している。学食で食事して購買でラノベを受け取り、帰りにコンビニに寄ってきた。
先週の週記を書き進めて午後11時過ぎに投稿。またしてもスカスカである。先週・先々週は読んだハーメルンの感想すら埋まっていなくて大変。「よう実」の二次創作ばかり読んでいたので、どの話がどんな展開だったか頭の中で混ざってしまった。
午後11時半からECR170。
Dashboard - Educational Codeforces Round 170 (Rated for Div. 2) - Codeforces
Aはコピーは高々1回。
と
のLCPを求める。LCPの長さが0のケースではコピーする必要がないことに注意。Bは表を書くと
だとわかる。
のケースがないのはかなり優しい。Cはソートして尺取り。
Dは片方の現在のレベルを持つdp。ポイント獲得時は
かけて更新してよい。それ以外は区間インクリメントになるので、imos法で処理する。ポイント獲得の度にまとめて反映しても変わらずで処理できる。
Eはスートごとに、先手がカードを何枚持つかを状態としてdpする。後手に勝つような出し方があるかは、カードをランクの昇順に見ればチェックできる。
でdpした後、スート
の分として
個畳み込むと、後手が何枚余らせるかわかるので、その通りそれぞれについてスート
に関するdpを行う。合計
。
Fは
を後から決めてよく、このときインデックスごとに
と
を交互に行うのが最適だから、各インデックスをできるだけ偶数回操作するのが目標となる。これは辺
を集めて作ったグラフにおいてEven Degreesをすればよい。
B - Even Degrees
Gは
ラウンドで1ダメージ食らうと解釈するのが良い。これをヒーロー
と防具
それぞれの寄与に分解すれば、ペア
に対してラウンド数が
だけ伸びると分かる。最大化するためにはとを降順に並べてマッチングしていくのが良い。しかしこれでもまだ計算は難しい。
ここで、
から損する分
を考えてみる。この値を数直線において区間
に対応させ、幅1の区間
にバラすと、実は次のようにして計算できる：すべての防具について
に、すべてのヒーローについて
にしたとき、
の総和。これは平方分割で計算できる。
Gのoff-by-oneで配列外参照を起こし、3回ほど37ケース目で落ちることを繰り返したが、ギリギリ時間内に気づいて修正できた。全完6位。
www.youtube.com
ハーメルン「『パワプロ成長』でダイヤのA」を読了。面白かった。投手全振りだと思っていたらいつの間にか打撃も最強格になっていて爽快。原作のことは全く知らないが、特に問題なかった。
同じ作者の「二郎になりました…真君って何？」も読んだことがある。どちらも300話前後あるが、1話あたりの文字数が少ないので総文章量はそれほどでもない。話の内容・展開が結構あっさりしていて、重たいシーンや重要な見せ場などをさっさと通り過ぎていくのも共通。ある種の読みやすさではあると思う。
syosetu.org
午前8時就寝。
10/15(火)
午後4時過ぎに目を覚ましたら、JOI一次予選の第2回が公開されていた。気づくのが遅すぎてShortestもFastestも取りつくされていたが、Bだけ1B更新することに成功した。Nibbles。
JOI 2024/2025 一次予選 (第2回) 過去問 - AtCoder
布団に戻って2時間ほど二度寝したあとは、R18のハーメルンを読み漁っていた。四つばかり読了。
「無口無表情でダウナー系の幼馴染は僕の部屋でくつろぎすぎている──ダウナー系で隠れ巨乳美少女な幼馴染がオナニーしているところを見かけてしまってから、僕が彼女と生ハメセックスを繰り返す仲になるまでの七日間」。良かった。タイトルからして短くまとまりそうなのも嬉しい。もう少しで完結するのではないか。
syosetu.org
「一色開発日記」。設定・シチュエーションに興味を掻き立てられたが、ほとんど進展なくエタりかけているのが残念。
syosetu.org
「俗物な転生者が天竜人になるようです」。ワンピースの通常の二次創作として面白かった。ところで、そもそも自分はワンピースの原作キャラをそういう対象にするのが苦手な気がする。頭の中にあるデフォルメされた原作イラストとR18の相性が悪い。
syosetu.org
「多分子供向けTCG世界か何かに転生したっぽいが、俺だけ成人誌の世界なんだが？」。エロではなくグロのR18。まあそんなにグロくはなかった。3話でエタりかけているが、TCG世界の最強キャラとして非常に良い雰囲気が伝わってきた。
syosetu.org
午後10時過ぎに寝落ち。
10/16(水)
午前2時半起床。
昨日に引き続いて、R18ハーメルン「最強雌殺しチンポ持ちのマスター君がサーヴァント達をハメ潰しまくる短編集」を読了。1話1話が長い。またFateにおけるキャラのビジュアルを詳しく知らないのだが、かといって一次創作のように自分で自由に想像するのも違うだろうから、頭の中でどのようにイメージすべきかが難しい。
syosetu.org
今週末のUniversal CupはTUPC2023セットである。準備が大詰めを迎えており、自分も英語問題文のチェックで参加した。やはり読むのと書くのは大違い。競プロの英語問題文なんてこれまで大量に読んできたはずなのに、典型フレーズをちっとも覚えておらず、文章に違和感があっても修正案をうまく出せなかった。
午前5時くらいからセミナー準備を始めた。セミナー準備というか、前回資料の英訳。これも修論とは別のpreprintになる予定である。
午後1時過ぎに学食に行った。今日の麺メニューは「濃厚魚介つけ麺」。以前からある「黒胡椒つけ麺」はつけダレの粘度が低いが、こちらは濃厚の名に恥じぬとろみがついていた。粘度が高いほうが好みな自分としては非常にありがたいところである。
ラノベを買って帰宅。セミナー準備を続けようとしたが眠気に負け、3時間ほど仮眠をとった。起きてから再開し午後9時くらいに完了。セミナー参加者にメールを送信した。
ハーメルンを読んで、日付が変わるくらいに寝落ち。
10/17(木)
午前3時過ぎ起床。
ハーメルン「俺がカードゲームで無双できる都合のいい世界 〜カードゲームアニメの世界に転移したけど、前の世界のカード持ち込めたので好き放題します〜」を読了。面白かったが周囲のレベルからあまり逸脱しないように力をセーブしているのはちょっと残念だった。一家揃って転移してきたから、家族のことを考えると悪目立ちもできないのだろうと理解はする。
この作品オリジナルのTCGは、詳細なルール説明はなかったが、読んでいるとだんだんわかってくる。基本的には遊戯王っぽくモンスターの召喚・魔法の発動にコストが必要ない。さらに簡単にするためか、召喚権がターン1ではなく、さらに魔法の発動を任意のタイミングで（相手ターンでも！）手札から直接行えるようになっている。その分、モンスターゾーンは3体分しかない。
syosetu.org
セミナーについて、昨日はほぼずっと資料の英訳をしていたため、今日新たに話す内容がほとんどない。そこで追加の準備を試みた。数値計算によってある条件を満たすグラフのリストが手に入っているのだが、そのリスト全体で何か共通する性質がないかを探してみた。
これまでは一つのグラフに注目してできることをずっと詰めていたから、全体を見渡すのはやったことがなかった。さらに言えば、そのような性質は簡単には見出せないだろうと思っていた。ところが、試しに部分グラフの関係を見てみたところ、なんとリストのうちある一つのグラフが他のすべてのグラフを含んでいることが判明。ここから何がわかるかまだ不明とはいえ、かなり顕著な性質であった。
午前9時ぐらいから3時間半二度寝して、原付で登校。悠長に学食で食事する時間がなかったため購買でパンを買って食べ、教室に向かった。
午後1時半からセミナー。今朝の内容を話したがふーんという反応だった。自分でも今のところふーんとしか言えないので、まあそれはそう。あとはpreprintに何を書くべきかと、数値計算で得られたデータをどのように工夫して見やすく表示すべきかという点について助言をもらった。
2時間で終了。しかしそこで解散ではなく、それから後輩の発表を少し聞いたり、先生が担当するセミナー形式の講義に参加したりした。講義には10月から先生の下に来ている留学生も参加しており、挨拶した。去年と同じ半年だけの留学プログラムで、今年は後輩が留学生のチューターを担当している。
学食で食事して午後7時から麻雀を打った。2半荘でどちらも2着。上がった回数は少なかったが、高い手が多かった。日付が変わる前に帰宅。
家に帰ってからもフラッシュゲームで麻雀を打っていた。ツモれば四暗刻の手が舞い込んだのに先に上がられて残念、と思ってふと相手の手を見たら国士無双だった。これに負けるなら納得感がある。
シャワーを浴びて、午前4時前からYandex Cup 2024のQualificationを走った。参加できる期間が週記公開前に終わるので、ここに感想を書く。
https://contest.yandex.com/contest/69390
Aは算数で判定して二分探索。Bは左右から前計算しておく。Cは全部Lまたは全部Rに置換するのが最適。Dは上限を倍々で探索した後二分探索。そういえば去年のQualの最終問題は、Stern-Brocot treeの探索にこのテクを使うことで
が一つ落ちるという話だった。運営はこれが好きなのか？Eは適当にdpしたら
から
しか出てこないという、正直親の顔より見たやつ。
まず二分探索の上限を指数探索で調べれば判定回数が全体でlog log 回になるらしい。自分の実装はおそらくここがlog log 二つになっていて落ちたのではないか。
週記（2023/10/23-2023/10/29） - kotatsugameの日記
Fは問題文に最適なクエリ回数が書いてあってありがたい。15クエリの最適な聞き方があって、それへの正しい返答を15bitの数だと思うと、1bitまでflipされて返ってくる。つまり答え一つに対して返答が1+15個存在するから、識別できる最大値は
。よって0から2024を区別するにはほぼ理論上の最大値を達成する必要がある。
しかし非常にあっけなく見つかった。結論だけ言うと、15bitの数を小さいほうから探索して、1bitまでflipした数16個がすべて未使用だったら採用して16個を使用済みにするという方法で、互いに識別可能な2048個の数が見つかる。あとは正しい返答がこれになるようにクエリを定めればよい。
何も悪いことをしていないのにジャッジから-1が返ってくることがあるらしく、1REに加えてバグ探しで14分ロス。結局バグはなく、1ペナ支払ってREではなくWAになることを確かめようとしたら通ってさすがにひっくり返った。確かに、問題文を正確に解釈しようとすれば、ジャッジの気分次第で答えが返ってこないことがあると読めなくもない。マジで言ってる？
少し日記を書いた後、数値計算に取り組んだ。今日のセミナーで、求めたグラフのリストに平面グラフはなかったのかと聞かれたため、チェックしてみた。見つかった。まあ平面性が関係しそうな話は今のところ一切ないので、やっぱり部分グラフの話と同じく現状ではただ見つかったというだけ。
午前9時就寝。
10/18(金)
午後6時から2時間ほどの中途覚醒を挟みつつ、午後11時起床。そこから少しハーメルンを読んだら午前2時。起き上がって食事した。
朝まで数値計算と格闘していた。また一つのグラフに注目する作業。以前対象に選んだグラフについては決着がついたのだが、もう一つくらい例があっても良いかもと言われた。せっかくなので昨日発見した平面グラフを使うことにした。
しかしこれが全然うまくいかなかった。手法をあまり確立できておらず、以前もガチャを回したのだが、今回はそれ以前の段階で躓いている。延々試行錯誤していた。全探索のようなことも何度か行っており、小刻みに待ち時間が発生して、気を抜くとすぐダラダラしてしまう。
どうやら「当たり」のパラメータを引き当てたようだ。
週記（2024/08/26-2024/09/01） - kotatsugameの日記
その待ち時間で先週の集中講義の課題レポートに取り組んだ。講義資料にいくつか用意されたExerciseのうち二つ三つ解くという形式。せっかく先生にいろいろ質問しに行ったのだから、それなりに難しいものを選ぼうと思ったのだが、最初に選んだものがどれもポンポン解けてしまった。
とはいえ残っている問題のうち難しそうなものには手が出ないので、諦めて解けたものを書くことにした。今はとりあえずアイディアをメモしておくだけにして、後から清書する予定。ちなみにClassroomにはまだ課題の提出先が用意されていないため、締め切りがいつになるのかは不明である。
午前10時くらいになって寝ようとしたが、せっかくなので学食が開くまで待ち、生協でいくつか用事を済ませることにした。こちらの待ち時間ではラノベを読んでいた。
午前11時半に出発。すっかり秋だと思って長袖の上からパーカーを着たが、なんと今日は夏日らしい。非常に暑かった。食事してラノベを買い、散髪して帰宅。
シャワーを浴びて午後2時前に寝た。
10/19(土)
午後7時起床。昨日読んでいたラノベ「バスタード・ソードマン」4巻を読み切った。
このシリーズは主人公のしょうもない日常が良いという話を以前にした。しかし3巻ラストの衝撃を受け、それでは物足りなくなってしまった。4巻も戦争の気配が漂ってきて何かありそうではあるのだが、まだ何も起こってはいない。そもそも戦争が始まったとして、それに主人公が関りを持つともあんまり思えない。先行き不透明。
食事して午後9時からABC376に出た。
AtCoder Beginner Contest 376 - AtCoder
Aはよい。Bは算数をしたくなかったので愚直に数えた。Cは二分探索。Dは
の最短経路と辺
に分解する。Eは
を固定、正確には値
であって
となるものを固定すればよい。
Fはdpで、直前の操作によって状態数が
通りになる。また遷移は手を時計回りに動かすか反時計回りに動かすかのみ。操作回数は頑張って算数するしかない。まあBを読んだ時点で、これは回避不可能だとわかっていた。場合分けとコピペが大量発生してかなり怪しかったがサンプルは一発で合い、幸いそのままACできた。
Gは何もわからず。頂点を探索する順番を長さ
の順列
としたとき、すべての
について
であることが条件であり、また期待値は分母を除いて
になる。このを探す問題。どうせ貪欲だろうと思ったが、自分が思いつく範囲では何をキーにしてもうまくいかなかった。
6完23位。コードゴルフはAのみ、Nibblesで書いた。scanl1を使って「直前に飴をもらった時刻」の列を作成し、重複を除いた長さを求める方針。
午後11時から、普段より30分早くCF #979 div.2。
Dashboard - Codeforces Round 979 (Div. 2) - Codeforces
Aは、
以降はすべて
、
以降はすべて
とできる。
なのでこれが最大。Bは
とするべきであり、を1文字だけ1にすることで達成できる。
Cは端に1があれば先手勝ち、途中に11があってもその間にANDを入れることで先ほどと同じ議論が回り先手勝ち。逆にそれ以外のケースは後手勝ちである。
DはLRで区切ってみると各成分の内部では自由に交換可能で、成分が異なると交換不可能である。
を見ると成分の区切りになってはいけない箇所が列挙できて、ダメな区切りがいくつあるか差分更新できるようになる。
書く
午前2時からはMHC Round 2に出た。
Meta Hacker Cup - 2024 - Round 2
書く
MHCはファイル提出のため余計なものが映り込む可能性が高く録画したくなかったのだが、ABCとCFの振り返りが間に合わなかったので、録画を中断してMHC後に30分ほど追加で録った。二つの録画ファイルを繋げて計5時間半の動画をエンコードするのに3時間くらいかかり、午前9時を回ってようやく公開できた。
www.youtube.com
今日も数値計算に取り組んだ。平面グラフはいくつかあるので、昨日のように一つのグラフに対して適用できる方法を探し求めるのではなく、一つの方法について適用できるグラフを探し求める方針にしてみた。するとめでたく発見。
実のところ、計算がうまくいきそうというだけで、本当に成功するかはもっと長い間待たなければわからないのだが、ともかく長い時間CPUをぶん回すフェーズに入ることができた。前回は7時間かかった計算を、今回はもう少し大きな入力に対して行う。果たしてどれだけの時間がかかるだろうか。
午後0時半就寝。
10/20(日)
午後5時半起床。午後6時からCF #980 div.1に出た。同時開催のdiv.2は、ついに到来したIDが2024のコンテストである。
Dashboard - Codeforces Round 980 (Div. 1) - Codeforces
書く
www.youtube.com
動画投稿を終えて午後9時半。それからゲーセンに向かい、閉店までで8クレプレイした。14+の「Trackless wilderness」と「Megameteor」のAJを出すなど成果は上々。この2譜面はもともとのスコアが低かったので、オーバーパワー的にも嬉しい。
ラーメンを食べて日付が変わってから帰宅。
数値計算が思ったより遅い。今回している入力に対してかなり効きそうな高速化ポイントがあったため、改善したものも同時に走らせることにした。
様子を見守っているうち椅子の上で意識を飛ばしそうになったので、慌てて布団に移動。午前2時過ぎに寝落ちした。
