今日解いた競プロの問題。
ABC275-F:
問題文のようにAに対して部分列の削除を繰り返すと歯抜けになり、残っているブロックと削除されたブロックが交互にあるような感じになる。削除されたブロックの数は最小操作回数に等しい。そしてこれは、残っているブロック→削除されたブロックと並んでいる境目の数に等しい。ということでN個の要素を順に見ていきながら、残すブロック→削除するブロックという遷移でコスト+1する感じの遷移をするDPをする。
具体的なDPの内容としては、Aの先頭からi要素分の部分列に関する同様の問題を解いていく感じのことをする。
DP[i][j][k]:=(数列Aの先頭からi要素分の部分列に関して, 連続する部分列を消去する操作を行って総和がjかつ最後の要素の状態がkであるようにする最小操作数)とした。kは「残す」か「削除する」の2値である。jがMより大きい場合については考えなくてよい。$O(NM)$で解ける。
オーディオミキサーを作るためにいろいろ回路をいじっていた。USBから電源をもらってスイッチング電源ICで負電源を作って、ジャックから音声信号をもらってオペアンプを通して増幅する、というだけの単純な回路なのだが、どうも出力音声を聴くとノイズが乗っている。そしてこれがなかなか消せない。
色々試行錯誤した結果、こんな感じでノイズが大別された。これに辿り着くまでにもかなり色々あったのだがその辺は端折る。疲れたからもう詳述する気力もない。
- 負電圧用スイッチング電源起因のノイズ
- 適当にコンデンサを負電源のラインに入れて解決
- オシロスコープ起因のノイズ
- プローブを外したら消えた
- オシロスコープは接地を確認、なぜプローブを当てた途端ノイズが出るのか意味が分からない
- オーディオジャック周辺の回路、もしくはPCのオーディオ回路起因のノイズ、「ザーッ」という音
- オーディオ入力と並列にインダクタを入れたら軽減された(なぜ？
- USB電源起因のノイズ、「ザザザ」という音
- PCやACアダプタではなくモバイルバッテリから駆動すると消える。
- PCやACアダプタから給電する場合についても引き続き試行錯誤したところ、ディファレンシャルモードノイズフィルタを入れたら多少軽減
かなり色々回路をいじってアナログ回路の感覚が多少身に着いたかもしれない。まあ、ノイズがまだ消せているとは言えない状況なのでまだまだなのだが。
USB電源起因のノイズが厄介で、どうしても完全に消えない。電源ノイズはシリーズレギュレータで軽減するという手があるのを思い出したので、明日やってみようと思う。
Categories: 未分類