atcoder.jp 解説読むとめっちゃ簡単ですよね...。 なぜ解けなかったのか...。 こちらの動画のコードを丸パクリさせて頂きました。 他の人のコードを読むのも勉強になります。 youtu.be N = int(input()) N += 1 A = [0] + list(map(int, input().split())) A…

atcoder.jp コンテスト中はコストの計算量の抑え方が分からずにsubmitできませんでした。 公式解説にもあるように生徒hを昇順にソートし、前と後ろからの累積和を予め計算しておけば$O(1)$でコストが計算できます。 累積和系のテクニックの大事さを痛感しま…

文字列に含まれる数字の順番を入れ替えて8の倍数が作れるかどうかを判定する問題です。 atcoder.jp 1000が8の倍数で割り切れるのがポイントです。 1000が8の倍数で割り切れるので当然それより桁の大きい10000も8で割り切れます。 つまり並べ替えた数列の下３…

巡回セールスマン問題(TSP)です。 atcoder.jp $N$が17なのでビットDPを使えば計算量的に間に合うようです。 $S$をビット列の集合として以下のDPを作成します。 DP[S][v]: 訪問済みの集合Sの頂点vからスタートする時の距離の総和 例えば$N=5$の場合、右から順…

最近Cまでしか解けずレートが全然上がりません...。 今回のD問題も方針自体は分かったのですが、友達の数が最も多い集団を探す関数の計算量が抑えきれずTLEしてしまいました。 解説動画でも紹介されていたUnion Findを用いた実装をしてみました。 こちらを参…

ゼロからできるMCMCの練習問題4.3について考えます。 練習問題4.2ではステップの偶数番目と奇数番目でステップの幅$\Delta x$を変更していましたが、練習問題4.3ではステップごとにサイコロを転がしてステップ幅を決めて更新します。 今回シミュレートする分…

ゼロからできるMCMCの練習問題4.2について考えます。 シミュレートしたい真の分布は です。分布の山が$x=0, x=100$に集中していることを考慮して、偶数番目のステップと奇数番目のステップで遷移幅$\Delta x \in [-c, c]$の値域cを変更しています。 具体的に…

というタイトルですが実際は以下の動画を見た感想になります。 【医師解説】全員にコロナウイルス検査をしても意味がない理由 実際に新型コロナウィルス(COVID-19)のデータを使って計算している訳ではないので注意して下さい。 (※内容に誤りなどがあれば遠慮…

ゼロからできるMCMCを現在読んでいます。 修士課程で量子モンテカルロ法を使った数値計算を行っていたのでMCMCについてはある程度知っているのですが初心に戻って基礎から勉強し直しています。 実は現在のお仕事でもSAを使って計算することがあり、MCMCを使…

蟻本(プログラミングコンテストチャレンジブック)のp25に記載されているハードルが上がった「くじびき」をDP(動的計画法)で解きました。 (間違っていたら教えてください。) 問題文はp8に記載されています。 次のDPテーブルを定義します。 DP[i][j]:i枚の紙の…

「ABC 164 D - Multiple of 2019」をC++で実装しようとした。 butch416.hatenablog.com 数年ぶりにC++を触ることになる。 intの範囲とかをもう少し勉強する必要がある。 ・参考ページ： 【C言語入門】整数(int、long int、short int)の使い方 | 侍エンジニア…

問題文 1から9までの数字のみからなる文字列Sが与えられます。 次のような条件を満たす整数の組$(i, j)(1\le i \le j \le |S|)$の総数を求めてください。 条件：$S$の$i$文字目から$j$文字目までを$10$進法の整数としてみると、この整数は$2019$の倍数である…

機械学習や競技プログラミング、数学、物理・・・に関する個人的なメモ置き場です。 Qiitaにも投稿しています。 qiita.com 大人の事情でアカウント名は異なりますが。