2023年　まとめ

年末に一年の振り返り記事を書くのは今年で3年目です。今年はかなり忙しい（当社比）年でしたが、何とか生き残っています。まずは今年の12ヶ月を振り返ります。

 

1月

　私は薬学部薬学科（6年制）に所属しているので、5年生になる今年は薬局と病院でそれぞれ2ヶ月半の実習を受ける必要がありました。実習に参加するには1月末に行われる CBT（座学の試験）と OSCE（実技試験、調剤や患者応対など）に合格しなければなりません。このため、1月は研究室をサボり試験対策をしていました。

　CBT の方は模擬試験で一応合格点を出していたため何とかなると考えていました。一方 OSCE の方は患者対応など人間性が問われる項目を含む試験であるため、専らこちらの対策をしていました。対策の甲斐あってか、本番でも人間性を捻出することができ、試験に合格しました。

 

2月

　2月後半から薬局実習が始まりました。薬局実習では基本的に二人組でそれぞれの薬局に配属されて実習を受けるのですが、幸運にも私だけ一人での配属になりました。他の実習生との人間関係をやる必要がなくなり、とても助かりました。その代わりなのか、実習先の薬局は大学から一番遠いところ（バスで10分くらい）に設定されてしまいました。実習後の研究室までの移動費は出ないので自腹を切る羽目になり、かなり気分が悪かったです。

　薬局実習の内容は配属される薬局にある程度任されているようです。私の配属された薬局では 実務 >>> 座学 といった方針で、初日から患者応対をすることになりました。OSCEで磨かれた人間性を駆使し、ノリと勢いで話を適当にすり合わせ、いい感じのコミュニケーションを築くことができました。OSCE ありがとう。

3月

　薬局実習に多少慣れてきた頃です。目薬にシールを貼って袋詰めをするのもだいぶ上手くなりました。ほとんど座学をせずに実務ばかりをしていたので、気分は完全にバイトでした。当然報酬は出ないし、何なら学費として大学経由で金を払っており、さらに交通費も出ないのでかなり気分は悪かったです。

　実習先の薬局には前年も東大生（つまり一個上の先輩）が配属されていたらしく、その悪行を聞かされるなどしました。実習先の薬局の狭い休憩室で、他の職員さんもいるのに横になって寝るのは普通に考えて非常識だと思います。こういった人間が東大生の評判を落としているのだととても良く勉強になりました。

　競プロでは Toyota Programming Contest 2023 Spring の予選に通り、Final に出場しました。オンサイトのコンテストは初めての参加だったので良い経験になりました。


4月

　薬局実習も残り1ヶ月の時期です。薬局ではあまり座学を受けなかったのと、自分も勉強をする気がなかったので薬の知識はそんなに身に付きませんでした。一方で患者さんとのコミュニケーションの取り方については色々教えてもらい、かなり勉強になりました。接客業で働く時に使えそうですね。

　薬局実習で印象的だったのは地域による客の質の差でした。実習先の薬局では比較的粗暴な爺さん婆さんが主な客でしたが、半日だけ実習をした、郊外ののどかな地域にある薬局では温厚なおじいちゃんおばあちゃんしか来ませんでした。あまりにも差が大きく、とても驚いた記憶があります。住む場所の大切さを実感しました。認知機能の怪しいおばあちゃんと1時間近くタイマンでバトルしたのもいい思い出です。

 

5月

　薬局実習が終わりました。薬局実習で学んだことを発表する必要があり、「白内障日帰り手術における術前後処方の問題点と調剤薬局の取り組みについて」という題で発表しました。おばあちゃんとのタイマンバトルの経験を活かし、そこそこ良い発表にできたと思っています。この時期から10月の学会発表を見据えて要旨を書いたりしていました。

　

6月

　病院実習が始まりました。遅刻に厳しく、朝8時には病院にいなくてはいけなかったので、毎日5時半起きの生活が始まりました。実習内容は病院内の5つの部門を順番に回っていき、そこで2週間ずつ実習を受けるというものでした。最初の部門では主に肉体労働について学び、サンダルで白衣をきたまま 10 kg くらいの輸液が入ったダンボール箱を運ぶ訓練を受けていました。次の部門では抗がん剤の調製などを学びました。普通に針刺しが危なくてめっちゃ怖かったです。

 

7月

　病院実習の続きです。3つ目の部門では指導してくださる薬剤師のお姉さま方のお気立てに難がおありで、複数回手が出そうになりました。しかし OSCE で磨かれた人間性により抑えることができました。OSCE はこのためにあったんですね。OSCE ありがとう。4つ目の部門は病棟で、ここでも認知機能の怪しいおばあちゃんとバトルしました。勝ちました。5つ目の部門は微分方程式解いてたら終わりました。

 

8月

　病院実習も終わり、研究室にまともに復帰できるようになりました。10月の半ばに学会発表があるので、それを見据えて研究の続きに取り組みました。嘘です。実習で完全に疲弊していたのでそんな気力はありませんでした。夏休みをとって天井を眺めていました。

　病院実習中に同期の皆さんが就活してるのを見て、何か就活に役立ちそうなことでもするかという気になり、応用情報技術者試験の受験申し込みをしました。天井と参考書を交互に眺めていました。

 

9月

　流石にそろそろ学会の準備をしなくてはならないので発表に使うポスターをぽちぽち作っていました。応用情報の勉強はしていません。研究室同期の皆さんもそろそろ就活しようかな〜という雰囲気になってきており、進路に悩んでいた私も諸事情のため就職を考えることになり、インターンシップの申し込みをしました。完全に就活を舐めており締め切り2時間前にESを提出しましたが、なんか通りました。

 

10月

　一番忙しかった月です。月初めに応用情報を受験しました。結局参考書は8割ほどしか目を通せず、午後試験は完全に無対策でした。全く受かる気がしなかったため試験前日は勉強をせず、二次創作の小説を書いてpixivに投稿していました。試験本番は国語力と算数力と当て勘とプログラミング力でどうにかしました。

　月半ばには学会発表がありました。初めての学会発表だったのでぼちぼち緊張しましたが、直前に先輩方が質疑応答の練習に付き合ってくださったのもあり無事いい感じに終えることができました。

　学会発表が終わった直後でしたが、なぜか研究室内の発表があったのでそれの準備でまた資料をぽちぽち作っていました。

 

11月

　研究室内の発表を適当に処理し、岐阜で行われた学会に見学に行きました。研究室の先輩方の発表をみた後は名古屋を観光しました。おしゃカヘでパヘを食べたかったのですが、2軒行ったおしゃカヘではどちらもパヘを提供しておらず、食べることは叶いませんでした。月末は申し込んだインターンシップに参加したりしました。この辺は実習+学会発表+その他諸々の疲弊が積み重なっており、よく天井を眺めていました。

 

12月

　インターンシップの謎の業務課題に頭を破壊されました。研究の方も諸事情で上手く行っておらず破滅です。たすけて。

　学会の発表で賞を頂いたり、なんやかんやで応用情報に受かってたり、良いことはいくつかありましたがトータルで見ると厳しい状態が続いており、精神状態はかなり悪いです。

 

振り返りが終わったので、次はこの1年でプレイしたゲームについて書きます。

 

・ブルーアーカイブ

　去年の11月に発狂した時に始めたソシャゲですが、何やかんや今まで続けています。この一年は精神的、肉体的な疲弊があったり、まとまった時間をとるのが難しかったりしたため、短い時間で手軽にプレイできるこのゲームを好んでやっていました。月平均2500円程度の課金ですが、ランキング戦で最上位のトロフィーを継続して手に入れることができています。二次創作の小説を初めて書いて pixiv に投稿しましたが、特に宣伝などをしていないにも拘らず100ブックマークがつき、ジャンルの強さを実感しました。面白いのでぜひ。

 

・AtCoder

　今年はあまり精進したりコンテストに参加する時間が取れませんでした。特に rated は3回しか出ておらず、レートの変動もほぼありませんでした。一応 ABC にはそれなりに出ており、2桁以内の順位もそこそこ取れるようになりました。

 

・ポケットモンスター バイオレット

　DLC が来たのもあって少しだけプレイしました。ランクマッチもレンタルパーティでやってみたのですが、マスターに上がってから5連敗したのでもうやりません。

 

・7 Days to End with You

　おされな感じのゲームです。未知の言語で喋りかけてくるキャラクターと対話し、その言葉の意味を推理していくというゲームです。なかなか面白かったです。この記事を読んでいる人なら結構興味を持つ人も多いと思います。

　

www.famitsu.com

 

・Refind Self: 性格診断ゲーム

　一時期流行ったゲームです。性格診断というよりはゲームのプレイスタイルの診断と言った方がより正確な気がします。

・Pokémon Sleep

　無課金でやっていますが、どうするのが最適なのか全くわかっておらず、途方に暮れています。

 

最後に、去年にたてた目標の達成度合いを確認し、来年の目標を立てます。

 

2022年のふもふもさんは次のように述べています。

来年の目標をリストアップします。

  • 生存
  • CBT+OSCEを通す
  • AtCoder 2400
  • 運転免許をとる
  • 就活(できるのか？)
  • 研究する
  • 病院実習+薬局実習から逃亡しない
  • ゲームする

どれか一つくらいは達成したいですね。

 

・生存: 状態は悪いですが、何とか達成しました。

・CBT+OSCEを通す: 滞りなく。

・AtCoder 2400: 流石に無理でした。

・運転免許をとる: 時間的余裕が……。

・就活: 一応インターンシップ一つは受けてますけどそれ以外は……。

・研究する: 一応賞取ったんでまずまずと言ったところ。

・病院実習+薬局実習から逃亡しない: 何とか。

・ゲームする: ぼちぼち。

 

では、来年の目標をリストアップします。

 

・(可能な限り健康的に)生存

・薬剤師国家試験を通す

・AtCoder 2400

・内定を得る

・研究する

・卒業する

・ゲームする

 

どれか一つくらいは達成したいですね。

 

良いお年を。

　

 

 

2022年　まとめ

2022年に自分がやっていたことを書きます。こういうのを書くときに Twitter をやっていると思い出しやすくていいですね。Twitter によると今年一年でやっていたことの8割はゲームなのでゲームの話をします。結構長くなってしまいました(約6000字)。

 

  • 1月
    年始は逆紅クイズにハマっていたようです。そこそこ自信作です、ぜひ解いてみてください。


    後半は wordle をやっていました。ちょっとした解析もしていました。


    研究室も決まったようです。第一志望に決まったのでよかったですね。有機化学をやる研究室ですが、有機系とは思えないくらいめちゃくちゃホワイトです。土日に登校しなくていいの最高すぎる。正直他の研究室だったら間違いなく失踪していました。

    タコピーもこの時期らしいです(親が本買ってた)。

  • 2月
    試験期間が終わって2月は丸ごと春休みでした。 Pokémon LEGENDS アルセウス をやっていたらしいです。ともしびを自力で全部集め切ったみたいです。この頃はだいぶ暇だったんですね。

    あとは競プロをやっていました。Google Hash Code で椅子を温めたりしました。

     

  • 3月
    まだ春休みでした。前半は追加コンテンツが来たこともあり、ずっとアルセウスをしていました。アルセウスはポケモン初のオープンワールド風アクションRPGということでその点も面白かったのですが、個人的には戦闘システムにとても興味を抱きました。行動順がリール制になったため使う技やポケモン次第で無限に自分のターンを得られたり、隠しパラメータのクールタイムがすばやさに依存するためそれを考慮した育成が重要になったりするなど、仕様さえわかっていればいくらでも悪用できるシステムであり、考察のしがいがありました。

    上記の応用として敵を倒すのに必要なターンの最小化を考えていたようです。先制技で自分のクールタイムを縮め、早業で相手のクールタイムを伸ばすことで相手が死に出しであってもこちらが先制できてしまうことが重要です。ここでは9手を紹介していますが、8手もあります。これは思いつくのに少し時間がかかりました*1。ターンを縮めるには威力の高い先制技で一撃で倒す必要があるのですが、これに該当するのはウェーブタックルのみになります*2。一方ウェーブタックルを覚えるのはエンペルトとイダイトウ系列のみで、エンペルトもイダイトウもすばやさが遅く、クールタイムの関係から自分の手番が継続できません。これを解決するのがイダイトウの進化前のバスラオです。バスラオはイダイトウよりクールタイムが1小さく、ギリギリ手番の継続ができます。火力面でも*3問題なく、8手で突破することができます。あえて進化前を使う点に意外性があり、手数、成功率の面でこれ以上の解はおそらくなさそう(ほんまか)なのでお気に入りの考察です。もしこれより良い結果が得られたらぜひ教えてください。

    競プロはレート-65とかしてました。絶対アルセウスやってたせいでウケるな。UTPCに4人チームで出たりもしました。

    後半は 星のカービィ ディスカバリー をやっていました。100%までクリアしたあと、少しタイムアタックをしたりして遊んでいました。こちらも面白かったです。ジャスト回避のシステムのおかげでカービィなのにめちゃくちゃ戦闘がスタイリッシュでしたね。ストーリーも終盤の展開が非常によかったです。道中の謎解きもよかった。おすすめです。

  • 4月
    研究室が始まりました。6年制の授業もあるので、両立が大変になって困っていたようです。


    流石にゲームをやる余裕はなく、競プロだけ少しやっていたようです。Google Code Jam の Round 1C に出て6500人中67位をとったらしいです。この回はあと10分あったら全完*4、順位1桁台も狙えていたので少し惜しかったですね。

  • 5月
    研究室に通うのがしんどくなってきたようです。春休みでぽにゃってたのもあるし、やはり片道2時間の通学を毎日やるのは結構大変です。一応指導教員ガチャでは元々教わりたいと思ってた人を引けたので大当たり(確率1/6)でした。

    GWには モンスターハンターライズ の金冠埋めをしていました。サンブレイクに間に合わせようと思ったのですが普通に間に合いませんでした。

    名取さな - モンダイナイトリッパー！【オリジナルソング】 - YouTube

    5月中はこれをずっと聴いていました。

    Google Code Jam Round 2 に出ました。4500人中104位とそこそこの好成績でした。みんなが詰まったBのHardがすんなり解けたり、残り3秒でDのSmallをACできたり結構運がよかったです。


    後半は6年制特有の院試休み消滅が発覚してメンタルがぽよぽよになっていました。運転免許とか取ろうと思ったんですけどそんなことはできませんでした。

  • 6月
    ある日研究室に行ったら同期が全員いなくなっていて非常にびっくりしました。大体2か月後に戻ってきました。

    この辺は研究(というか練習実験)がうまく行っていなかった上に院試休みが消滅したのもあり、しばしば研究室から逃亡していました。1週間ほど逃げ回ったあと指導教員に上手く行きませんでした……と報告したら、その指導教員から渡されていた実験の手順書がそもそも間違っていたらしく、ややウケでした。

  • 7月
    モンスターハンターライズ：サンブレイク が発売されたので進めていました。DLC第一弾まではプレイしたのですが、それ以降は手をつけていません。そのうちやります。モンハンはかなりプレイしているシリーズですが、やはり面白いですね。多人数でやるゲームや対人戦がメインのゲームが嫌い(苦手)なので、ソロでできるアクションゲームシリーズは貴重です*5。ただやはり装備のシミュレータを回したりダメージ計算したりするときが一番楽しいですね。ゲームでも研究でも、効率最適化を考察しているときが一番面白いです。

    第三回日本最強プログラマー学生選手権-予選- に出ていました。国内学生の順位で50位以内だとオンサイトの本戦に招待されますが、落ちてしまいました。おそらく55位前後なのでだいぶ惜しいですね。6完早解きがボーダーでしたが、6完遅解きになってしまい少し残念。

    研究はだいぶ怪しい実験を重ねてなんとか入り口にたどり着きました。計算化学に手を出したりもしました。計算化学はうまく行かなかったときにちゃんとエラーメッセージを吐いてくれるぶん実験より気が楽で良いですね。研究室の先輩に連れられて野球を見に行ったり花火を見に行ったりしました。人に誘われないといくらでも家( or 研究室)に籠る人なので、誘ってもらって嬉しかったです。

  • 8月
    本格的な研究が始まり、毎日異常な実験をしていました。

    8月中の研究はこの超常現象に翻弄されていた感じがあります。今では多少その原因がわかってきています*6。

    少し夏休みをもらってモンハンをしていました。DLCの第一弾が来たので装備の更新と周回の効率化について少し考察をしていました。

    WCSもこの時期ですね。カードゲーム部門を中心に見ていたのですが、ポケモンGO部門もかなり面白かったです。

    同期が夏休み終わっても研究室にこなかったため、話し相手がいなくて少し気が狂いはじめました。日記を始めましたが数日でやめました。研究の詳細を書くわけにはいかないのであんまり書くことがなかったんですよね。

  • 9月
    研究は多少軌道に乗ってきて、そこそこ良い結果が得られるようになりました。

    流石にこれは横転しました。私は研究室で合成されたある新規化合物について研究しているのですが、関連分野の論文を読んでいたらそれにそっくりな構造式が出てきてめちゃくちゃビビりました。論文をよく読むといくらでも差別化できることがわかったのですが、見つけた時は研究終わったかと思いました。ちなみにこのテーマを与えてくれた指導教員はこの論文の存在を知らなかったらしいです。ややウケ。

    ARC でぶち当てて、初の赤Perf、700+800点のACを出しレートをいっぱいもらいました。


    スプラトゥーン3 を始めました。FPS、TPSは今までやったことなかったので中々新鮮でした。スプラシューターでS+までは簡単に上がりましたが、そこから無限に借金を積み、返済した頃にはアップデート直前でS+10には全く届きませんでした。アップデート後は全く触っていません。そのうちやります2。

  • 10月

    700点問題をエスパーで倒してレーティングが2200+になりました。実質誕生日プレゼントでした。2000と2200↑は表示上は半色の差しかないですが、ABCとARCのレーティングの歪みを考えると実質1色近い差があると思ってるのでかなり嬉しいです。来年は2400を目指したいですね。

    スプラトゥーンもちまちまやっていました。

    友情破壊コンテストとして名高い PG BATTLE 2022 に出ました。

    惜しくも表彰台には届きませんでしたが、友情は破壊されることなく無事に商品を手に入れました。実数さん @rityo_masu 焼肉ありがとう。

  • 11月
    薬学科のカリキュラムが始まりました。研究室も普通にあるので、薬学科の授業と研究室の用事が無限回激突していました。特に険しかったのが11月冒頭の進捗発表会で、当日の深夜まで発表資料を作る人になっていました。ついでに指導教員に資料作りを手伝わせたりもしました。深夜2時まで働かせてしまい大変申し訳ありません。

    ブルーアーカイブ を始めました。存在は7月くらいから知っていたのですが、ソシャゲにはあまり乗り気でなかったので特にやるつもりはありませんでした。進捗発表会の準備が忙しすぎて気が狂ってたときに、競プロは落ち着いてできないしスプラも飽きたな〜となって始めました。最初はキャラクターとBGM目当てで始めたのですが、今はゲームシステムの面白さ目当てでやっています。このゲームは毎日決まった量配られるリソースをキャラクター育成に割り当て、そうして育ったキャラクターで高難易度のコンテンツの攻略を目指すというゲームになっています(もちろん、好きなキャラクターを気ままに育成するのも遊び方の一つです)。ブルアカは配られるリソースを課金によって増やそうとするとある程度のところで頭打ちになるシステムになっており、その分プレイ日数が運用可能なリソースの総量に直結します。そのため自分より先に始めた人間を追い越すには、限られたリソースをより適切に配分する、あるいはプレイヤースキルや知識によって育成度合いの差を誤魔化すことが重要になります。そういった最適化に頭を悩ませる必要があり、なかなか面白いゲームだと思います。おすすめです。

    ポケットモンスター バイオレット を買いました。1日やってそれ以降全くプレイしていません。薬学科と研究室が異常に忙しいのとブルアカを始めたのが原因です。一応ネタバレは極力避けるようにしてはいるのですが、どうやらウルガモスちゃんとウルガモスもどきが出てくるということがわかってしまいました。そのうちやります3。

  • 12月
    概ね11月と同じで、薬学科と研究室の両立が大変でした。研究室のソースコードをいじって遊んだりブルアカをしたりしていました。忙しすぎて記憶がないです。

 

来年の目標をリストアップします。

  • 生存
  • CBT+OSCEを通す
  • AtCoder 2400
  • 運転免許をとる
  • 就活(できるのか？)
  • 研究する
  • 病院実習+薬局実習から逃亡しない
  • ゲームする

どれか一つくらいは達成したいですね。

 

良いお年を。

*1:ある程度安定して出せる手数を考察しているため、急所は考慮しない

*2:オーラウイングは確か火力が足りなかった気がする

*3:アルセウスのダメージ計算は特殊で、こうげきのパラメータが技のダメージにあまり影響しません

*4:OEISエスパーですが

*5:多分探せば無限にある……

*6:実験の条件を変えるとある程度回避できることがわかった

Convolution 練習問題まとめ

NTT (高速数論変換)を利用した Convolution の各種テクニックが学べる問題をリストにしました。Karatsuba乗算についても少し触れています。

  1. F - Convolution 
    まずはNTTライブラリの確認から。

  2. A - コンテスト
    簡単な問題です。NTTだと mod をとってしまうため畳み込み後の値が 0 なのか 998244353 の倍数なのかが判定できませんが、この問題では撃墜するようなケースは入っていません。心配なら複数の NTT-friendly な mod で計算して全て 0 になることを確かめると良いと思います。

  3. 065 - RGB Balls 2（★7）
    一手考察が必要ですが、基本的な問題です。
    ヒント：それぞれの条件を言い換えます。二色についての条件になっているのが厄介なので、K を使って一色ごとの条件に言い換えましょう。

  4. No.1195 数え上げを愛したい（文字列編） - yukicoder
    素朴なDPをNTTを使って高速化します。
    ヒント：遷移の係数を、i のみに依存する項、j のみに依存する項、i + j のみに依存する項の積の3つに分解できると畳み込みができます。

  5. https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=3281
    木DPでは部分木のDPテーブルをマージする操作が畳み込みの形になっていることがよくあります。
    おまけ：No.196 典型DP (1) - yukicoder　これと比較してみると面白いかもしれません。こちらはNTTが要りません(”二乗の木DP")。木DPの畳み込みだと二乗の木DPの方がメジャーですかね？

  6. No.206 数の積集合を求めるクエリ - yukicoder
    少し工夫すれば畳み込みで解くことができます。
    ヒント：各 v について、 i = j + v となるような (i,j) について A[i]*B[j] の和が取れれば良いです。これは i - j = v について畳み込みをすれば良いです。

  7. F - Substring 2
    少し難しいですが、畳み込みで解けるとわかった上で考察を進めれば多少楽になります。下のパターンマッチングの記事も参考になります。
    ヒント：({0,1}, xor) は ({1,-1}, *) と置き換えることができます。

  8. C - Product Modulo
    有名問題です。少し知識が必要です。積に関する畳み込みをうまく和に関する畳み込みに帰着します。
    必要な知識：原始根。一応NTT内部でも原始根は使われていますね。ヒストグラムにしてから畳み込むというのも少し面白いです。

  9. Multiset's Subset's Product Sum Hard | MojaCoder
    多数の小さな配列を畳み込む必要があります。
    必要な知識：いわゆるマージテク。マージテクにはいくつかの種類があります。 マージテクと高さ O(logn) のマージ過程との融合 | Mathenachia　

  10. https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2959
    少し考察が必要ですが、中央を固定すると畳み込みの形で書くことができます。畳み込みに i < j の制約がついていますが、頑張るとNTTで畳み込むことができます。
    ヒント： j - i = k - j で j について畳み込めば良いですが、これは i + k = j * 2 ( i < k )とすれば良いです。不等式の制約は分割統治で解消できます。配列を前後2つに区切ることでより小さい問題に帰着しましょう。ちなみにKaratsuba法だと計算量が悪化しません。

  11. 工事中
    ヒント：online-convolution, relaxed-convolution とか呼ばれるタイプの畳み込みです。9, 10, 11 はどれも分割統治NTTと呼ばれることがあるので、少し混乱を招きそうですね。online の問題を offline の問題に帰着して解く問題だと、他には Monotone-Minima を使うものが有名でしょうか(この手の問題を募集しています)。

 

興味深い資料

その他

  • long long での畳み込み
    長さN、各要素が long long に収まる配列A, Bを畳み込んで配列Cを得るとします。 こういった時に mod 998244353 を取った値ではなく本来の値が欲しくなる時があります。これは簡単で、複数の mod を用いて NTT を使った畳み込みをした後、中国剰余定理で復元すれば良いです。C の各要素の大きさが 1e18 以下であることが保証されているならば、NTT-friendly な mod の組として (998244353, 1224736769) の組が使えます。この2つの積は 1.2e18 程度で、1e18 を超えるため中国剰余定理で復元できます。long long は最大で 9.2e18 程度になるので、そこまで見るなら3つの組にする必要があります。ACLだと (754974721, 167772161, 469762049) を使っています。この積は 6e25 程度なので余裕ですね。

  • 任意modでの畳み込み
    例えば mod 1e9+7 などで畳み込みをしたい時があるかもしれません。とりたい mod を M とします。A,B (mod M) から C (mod M)を得ることにします。これもlong long の時のように A,B (mod M) から C (mod をとる前) を得て、C の各要素を mod M で置き換えれば良いです。*1求めたい mod が 2^32 以内かつ配列の長さが 1e6 程度なら C (mod をとる前) の最大値は 1e25 程度なので、 先ほどの(754974721, 167772161, 469762049) が使えます。mod をとる前の C の最大値は long long には入らない場合があることに注意してください。 int128 を使ったり、garnerのアルゴリズムを使うことでオーバーフローを回避できます。

*1:正当性: 畳み込みを定義通り計算すると和と積を取るだけなので一時的に mod を外して後でとり直しても大丈夫。

22/08/26

みんなも日記を書こう！

 

  • 朝
    • 眠すぎるが電車の中で寝れなくて微妙な感じ。
  • 昼
    • 寝不足のためかかなり実験操作が雑だった。良くないね。
  • 夜
    • 7時に帰宅するつもりが手際が悪く8時になってしまい悲しい。帰宅してすぐyukicoderのコンテストに出る。結果は6完38位。20分遅刻したとはいえ微妙な成績。
    • Aは後ろから貪欲。Bはかなり難しい。DPの遷移をグラフにすると、最終的には同じサイクルを回るだけになるとわかる。最終的に回るサイクルというのは、1を続けるか、1と-1を往復する形になっているので周期2を持つ。あとは小さいところを愚直にDPして補間する。
    • Cは式変形でなんとかしようと思ったが実験したら一発だった。Dも実験した。偶数番目の山を操作は相手の直後の操作で打ち消されるため意味がない。そこで奇数番目に注目すると規則性がわかる。Eは式変形して桁DP。
    • Fはbinary_trieを思い浮かべれば簡単。Gはコンテスト中にはわからなかった。コンテスト終了後に高速なsubset sumの話を思い出し、Library-checkerのコードをパクって通した。形式的冪級数のライブラリをそろそろ整備するべきなのかもしれない。

 

  • 日記に少し飽きてきたところがある。

 

22/08/25

一応三日は継続した。

 

  • 朝
    • 研究室に着く。昨日放置して帰った試験管の中身を覗くとよくわからん状態になっていることが発覚。微妙な気持ちに。
    • シールドチューブの凄さに感動する。DCMを入れて45度で加熱還流して一晩放置したがほとんど溶媒が飛んでいなかった。今度からDCMで実験する時はこれを使おう。
  • 昼
    • 学食に行く。今まではコンビニで300円程度の昼食を買っていたので、学食より安上がりだと考えていた。しかし同時にペットボトルのお茶などを買うので実際には400円程度使っていた。しかし学食では無料で水を飲めるため、こちらも400円+αで(コンビニよりまともな)昼食と水分を確保できる。したがって、学食まで移動するコストを差し引いても十分学食に行く価値があると考えた。
    • カツカレーを注文する。なぜか味噌汁を勧められたのでそのまま受け取ってしまった。カレーに味噌汁が付いてきた理由がわからず、頭がバグって味噌汁をスプーンで飲む人になった。
  • 夜
    • 別の実験を見ていたがNo Reactionっぽくてまた微妙な気持ちに。8時半に研究室を出る。

    • No.535 自然数の収納方法 - yukicoder
      こういうのは円環を切ってDPするのが定石なのでうまく切れないかを考える。A_N-1とA_Nの関係がかなり緩く、A_N-1 = NのときにA_N != 1、そうでない時A_Nは自由な値を取ることができる。そのためこの2つでそれぞれDPすれば良い。DPの中はよくある累積和で高速化でき、O(N^2)。

    • No.550 夏休みの思い出（１） - yukicoder
      中間値の定理から二分法が適応できて、解の一つが求まる。残りは二次方程式なので解の公式で終わり。誤差が気になるが、適当に書いたら通った。

    • No.534 フィボナッチフィボナッチ数 - yukicoder
      ググると周期があることがわかるので2回行列累乗すれば良い。

 

  • 研究、一喜一憂というより一喜千憂くらいしている気がする。
  • 帰宅が遅くなると睡眠時間が死ぬ。

 

22/08/24

日記を書くことで自律神経のバランスを整えることができるらしい。この日記は睡眠時間を削って書いているので逆効果な気がするが。

 

  • 朝
    • 昨日は日記を書いたせいで睡眠時間が4時間半程度になってしまい異常に眠い。なんとか寝坊せずに登校。
  • 昼
    • 学食で昼ごはんを食べた。普段はコンビニで買ったものを食べているが、たまにはまともなものを食べようという気持ちからの行動であった。辛味噌ラーメンを食べようと思ったがなかったので赤門ラーメンを食べた。ぼちぼちの美味しさ。
    • 学食からの帰り道、道の真ん中で五体投地している子どもを見つけた。15秒ほど動いていないように見えたので少し心配だったが、普通に立ち上がって走り去ったので一安心。
  • 夜
    • 仕込んだ反応の様子を見たが大して進んでいなさそうなので放置してさっさと帰宅。7時に研究室を出ると寝る前の時間を2時間ほど確保できるので精神的に良いとされている。

    • No.818 Dinner time - yukicoder　昨日の続きを進めた。下に白文字で考察を書いた。
      昨日は平方分割でなんとかすると言っていたが、流石に実装が厳しいのでもう少し良い方法を考える。DPテーブルが常に下に凸になっているという観察が重要で、実は左端と右端だけ見ておけば最適値を計算できる。これで状態数がO(1)となり、ACできた。かなり良い問題なのでfavが多くついているのも納得。

    • No.919 You Are A Project Manager - yukicoder　
      N<=10000なのでO(N^2)とかを考える。Kを全探索した後、左からとるチーム数と右からとるチーム数の組を全て試せば答えが求まる。左と右のチーム数の組を試すのは累積和によって線形時間できるので、中央値を求めるためのソートが律速になってO(N^2logN)になる。これで一度投げると微妙にTLEする。よく考えると中央値を求める部分はA_iの昇順に見ていくことで線形時間になり、O(N^2)となる。これで書き直した後、適切な定数倍高速化を行うとギリギリ通る。想定解はMo's AlgorithmによるO(Nsqrt(N)log^2N)らしい(全く頭になかった)。yukicoderをやると定数倍高速化のテクニックが身につくので良いとされている。一応非想定解ではあるが、C++でしか通らない解法を紹介するのもなと思い解説記事は書かないことに。

 

  • 日付が変わる前に書き上がったので、今日は睡眠時間を削らずにすみそうだ。

22/08/23

気が狂ったので日記を書き始めた。

 

  • 日記について
    • なぜ書き始めようと思ったのかは謎。多分自分の思考をアウトプットする場所が必要になったからだと思う。最近人間と話さない日々を送っているのでそういうことかもしれない。
    • 平日は頑張って書こうと思っているが、あまり長くは続かない予感がしている。平日は大体研究をしているので大して書くことがないかもしれない(研究の詳細について書くわけにはいかないので)。

 

  • 朝
    • 電車で寝てたら終点に着いたことにしばらく気づかず、逆向きに輸送されかけた。疲れていたらしい。
    • 昨日の手の痺れは無事に治った。いい話。日記を書いていたらまた痛くなってきた。悲しいね。
  • 昼
    • 研究をする。生成物を無限に精製する謎の人になっていた。

  • 夜
    • 反応を仕込んで帰宅。新規反応を試すのに貴重な原料の大部分を使ってしまったのはかなりアホだった。半分残しておけばよかった。NMRを見る限り謎の現象が起こっているので良い方向に進むことを期待したい。

  • 家

    • No.818 Dinner time - yukicoder を考える。考察を下に白文字で書く。

    • dp[i][j]をi日目まで決めたときに、1~iを選ぶような日数がちょうどj日ある時の最大値と定める(各日で決めるKの順番は考える必要がない)。この時のDPの更新は、全体に傾き正の一次関数 or 傾き負→0となる一次関数を足したあと、jの大きい方から累積maxをとる形になっている。したがってDPテーブルはjに対して、傾きが負である下に凸な関数になっている。
    • この性質を利用することで遷移を高速化したい。これは平方分割を利用すれば可能だと考えている。ここまで考察して力尽きた(もっといい方法がありそう)。また明日。
  • その他

    • 1000年生きてる / 月ノ美兎 cover - YouTube 　最近よく聴いている。かなり良い。イラストが描けるようになりたいなと思って二週間くらいちまちま練習を続けていたが断念してしまったことを思い出した。時間があるときしか練習できないが、時間があると競プロをしてしまうのでなかなか難しい。

    • Stable Diffusionに興味を持った。権利関係とかその辺のことがよくわかっていないのでしばらく様子見。
    • ブログの編集に毎回困っている。HTML編集とかで書いた方が良いのかもしれない。