最終更新: 2020-08-27T19:59+0900
解けなかった。まだ解けていない。考慮すべきが漏れてるのか、何か思い違いがあるのか。
とりあえず、完全に並べ替えても題意を満たせないケースに No を返してみた。該当(AC)１件>https://atcoder.jp/contests/nikkei2019-2-qual/submissions/8356932。
N-1 回の交換だと N 要素の A 数列を完全に思い通りに並べ替えられると思った。ぎりぎり１回足りないのが N-2 回なのかな、と。
ぎりぎり１回足りない条件とは？
A 数列のすべての要素があるべき位置から外れた状態にあり、A 数列のすべての要素が数珠つなぎに位置を交換している、だと思った。
ソート済みの A 数列のどの隣接要素を入れ替えても題意を満たせなくなることだと思った。
逆の例は、B 数列に重複する値が存在する場合や、B 数列の最小要素以下の要素が A 数列に複数ある場合など。その場合は A 数列に区別が不要な要素が存在するということであり、交換回数を節約できてしまう気がした。
これもそうではない例を考えると、A 数列が k 要素と N-k 要素の２グループに分かれて位置を交換している場合が該当する。k 要素をあるべき位置に並べ替えるのに k-1 回の交換を要し、N-k 要素を並べ替えるのに N-k-1 回の交換を要するのだから、計 N-2 回の交換で A 数列のすべての要素があるべき位置に納まってしまう。
だから A 数列のすべての要素が唯一のグループを作って位置を交換していなければいけない。その場合に最大 N-1 回の交換を要する。
というのをコードにして提出したのだけど、WA が半分>https://atcoder.jp/contests/nikkei2019-2-qual/submissions/8366469。答えが二択なんだから惜しくもない。わっかんねーなー。
T v; c.push_back(move(v)) みたいなコードを書いて呼び分けることになったと思う。■たぶん std::move って書いても書かなくても同じな場面が多くあると思う。ムーブしてきた値を受け取る側からしても、&& と書いたからといって特別な何かが必ず期待できるわけではないらしいし。俺は煩わしいからできるだけ書きたくないし、書いた方がちょっとだけ嬉しい場面でも書かずに済ませたいクチ。■コンストラクタと代入演算子がムーブとコピーがオーバーロードされる例か。かつての auto_ptr の所有権移転コードのようなものを書くみたい。うっかりリソースを共有した状態にすると二重解放の罠。auto_ptr と違ってちょっとわかりにくいのは、値に対して所有権を持っていないというのがどういう状態か想像しにくいこと。ポインタであれば値が NULL であるとか、値はあっても弱参照でありいつまでデリファレンスできるか不明であるとかが想定されるのだけど。■おべんきょ。「C++のムーブと完全転送を知る - Fixstars Tech Blog /proc/cpuinfo」「メイドでもよく分る右辺値参照 - TXT.TXT」■git もだいぶ時間がかかったけど(ものぐさなだけとも言う)、だいぶ煮詰まってきたんじゃないだろうか。かつての C++ In-Depth シリーズのような本が読めないのが残念でならない。そういう研究が必要ないというのなら、C++ が言語として進化したのではなく単に充実しただけであるということ。進化がないのも研究書が読めないのもどちらも不満。■ムーブってついつい一時オブジェクトの省略(※コピーや移動の終着地点に最初から一度だけオブジェクトを構築して済ませてしまう)と結び付けて効率化の手段だと考えてしまうけど、プログラマが書いたムーブコンストラクタが実行されるなら、それはコピーコンストラクタが実行されるのと変わりがないのでは？ 利点があるとすればメンバとして保持する外部リソース(ヒープメモリ、ハンドルなど)の確保が省略できる、奪い取って間に合わせられるという点にしかないのでは？■俺は auto_ptr が大好きだし、その制約も喜んで受け入れるし、Rust のメモリ管理も好きだけど(「Rustは何が新しいのか（基本的な言語機能の紹介） - いもす研 (imos laboratory)」)、ムーブは面倒くさいなあ。これまで通りコンパイラの最適化に期待するだけにして、面倒は避けたい、必要に迫られるまでは。[ か ] を含んでるファイルを再生してくれないので、それぞれ %5B と %5D に置換する必要があった(※手を加えたのはファイルシステム上のパスではなく、プレイリスト内のパス)。なんで？ 二重にパーセントエンコードされても不思議じゃないんだけど、なんで OK なの？ これじゃ %5B という３文字を含むパスと [ という１文字を含むパスを区別できないじゃない。