2022-01-01から1年間の記事一覧
起きたのは9時ごろ.昨日解けなかった#797div3のG問題を考えていた.前日の時点ではdp[i]=iからtrainをはじめたときの連結の個数,と定義すればできそうだと思っていたが実装がクソだるになりそう.もうちょっといい方針がないかとずっと悩んだ挙句,trainの…
ポイント:最大最小の値に注目 1つのコンテストの楽しさは最大のLと最小のRで決まる。よって与えられた問題のうち最大のL,最小のRはどちらかのコンテストの右端左端になっていなければならない。 この変換は早く気づきたかった。
解くのに恐ろしく時間がかかったので簡単にまとめたい。 最小操作になるにはどうするかにめっちゃ時間がかかった。 まず、P[j]>P[i]となっているjの個数がKより大きくなっているところを見ると1回のswapでどこかのiについて-1しかできないから、xを個数とす…
初回ミーティングについて 10月11日に発表がある。 作るものは思いに2つでプレゼン資料(15枚くらい)と前刷りである。 前刷りはA4裏表で論文を要約したもの。 毎週水曜8:50~10:20にミーティングをすることになった。毎回論文2ページ分をスライド(2~…
久しぶりに日記を書く気になった。というのも一日を無駄にしすぎてそろそろ自分を顧みたいという気持ちになったからだ。 月曜は1~3限まであるが、3限は休講だった。1限は電気電子回路IIでクォーターが変わる今日から始まった。思ってたのと違って内容は理論…
解法 ワーシャルフロイド法を用いてすべての頂点間の最短経路を求める。必要な辺はその辺を使わないと最短が達成できなくなる辺 証明 仮にその辺を使わないとすると、2辺以上を用いた最短経路が存在する。閉路に入る意味はないため、使われる変数は高々 。こ…
atcoder.jp
方針はdpですぐ決まったが、メモリオーバーフローに苦しめられた。関数外で定義した関数が配置されるメモリを静的メモリ、関数内で定義したメモリはスタックメモリと言い、スタックメモリより静的メモリのほうが容量が大きい。そのため、グローバル変数を定…