2020/04/25
だらけがちなので今日から簡単に進捗日記をつけます。
研究
- 読んだ論文1本
- 論文執筆1h
- セミナー準備3h
論文執筆がなかなか進まなくてきつい。集中して終わらせたい。
AtCoder
4問AC
(解説AC含むが)ABC-C埋めと700ACを達成できたのでよかった。
ABC009-C とABC025-Cを解説ACした。青相当はやはり難しい。以下ネタバレ含みます。
提出例を参考に、先頭から見て、それ以降でswapすべき最適な文字を見つければswapする(その結果差分が箇所を超えてしまう場合はswapしない)という貪欲的なやり方で解いた。解説のように各アルファベットについて見ていっても良いが、十分に3重ループを回せそうだった上に、こちらの方が実装が軽そうだったのでこの方針を取った。解法ガチャは、計算量が多い順に考えていくのがいいのかもしれない。
この手の問題(お互いが最善を尽くす系)はかなり苦手で、10分考えただけで解説を見た。最終形態から遡っていけばパターンを漏れなく列挙できる。また、制約が軽いのでdfsで全探索すればいい。
過去に解説ACした C - 双子と○×ゲーム も最善尽くす系だったので軽く見直しておいた。最善尽くす系は適当に実験してみて方針を考えるのが鉄板だなと思った。
英語
DMM英会話 (streak : 1)
---
明日も頑張りましょう。