最終更新: 2020-05-06T23:27+0900
階乗が法外な大きさになるので余りを答える問題。割り算を含む式の余りが求められなかった。もちろん階乗を計算しきってから余りを求めるというのは実行制限に引っかかるので無理。
モジューラ逆数っていうのがあるんですね、これはすごい pow(down,mod-2,mod) 昨日のD問題逆元の計算どうやればいいのかわからなくて1時間くらい経ってしまった
AtcoderのABC145D問題しっかり理解して頭の中整理してすっきりかけた気がする。Python3です。 pic.twitter.com/Dcs3IfoZ95
mod って演習込みでイチから習った記憶がない。「割った余りですよ」以上の理解がない。キーワードすら知らなくてググりようがない。
Ruby には Python と違って「冪剰余 - Wikipedia」が求められる関数が用意されていないみたいなので(※補足訂正)、拡張ユークリッド互除法を使う方の求め方を Wikipedia(ja) からコピペ実装した>https://atcoder.jp/contests/abc145/submissions/8508807。明日には理解できないとしても「モジュラ逆数」というものの存在くらいは覚えておきたい。
速いからには変わったことをしてる。derive_inverse メソッドが理解できない。法のビットを利用しているみたい。理解できないのは本質を掴んでいないから、演繹が働かないからだろう。「冪剰余#さらなる最適化 - Wikipedia」を実装してるのだろうか、雰囲気的に。
pow メソッドを使って実装された derive_inverse がコメントアウトして残されている。
試したら Ruby 2.5 には冪乗余が求められる Integer#pow メソッドが用意されていた。2.6 の「数値関連のメソッドを実際に定義しているクラス一覧」には載ってなかったんだよなあ。Ruby 1.9 時点では pow メソッドはなかった。AtCoder の 2.3 でもまだないかもしれない。
つらつら眺めてると、require 'matrix' して lup.solve で勝手に方程式を解いてもらえるとか、require 'openssl' すると mod_inverse が利用できるとか、知らない方法が色々あるもんだ。でも LUP 分解が解らなければ見ても使うべきときが判らないし、知っても使えない。『[単行本] 平岡 和幸, 堀 玄【プログラミングのための線形代数】 オーム社』は中座してるし、『[単行本] ロナルド・L. グレアム, オーレン パタシュニク, ドナルド・E. クヌース【コンピュータの数学】 共立出版』もちょっと眺めただけ。若いうちに学校で広く浅くでも詰め込んでおくべきなんだよ。基礎がないと何も積み上がらない。
最終更新: 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)」)、ムーブは面倒くさいなあ。これまで通りコンパイラの最適化に期待するだけにして、面倒は避けたい、必要に迫られるまでは。