俵言スマートフォン用の表示で見る俵言しがない社会人が書く、勉強とかのこと。昨日のABC024に参加しました。abc024.contest.atcoder.jp前回(ABC023)に比べるとオーダーの制約は優しかったんですけど、Dが解けなくて残念。逆元の話とか勉強になりました。動物園の一人当たりの料金(こどもA円、大人B円)が与えられるので、こどもがS人、大人がT人だったときの料金を求める問題。団体割引さえちゃんと考慮すれば特に問題ないです。自動ドアN人のお客さんそれぞれが店を訪れる時刻と自動ドアが開いてから閉まるまでの時間が与えられるので、自動ドアが空いていた合計時間を求める問題。大きさの配列とかなめるだけでTLEの気配が漂ってきますわ。for文回すので、python的にはギリギリな感じ。そもそも最初から配列を使う必要は無くて、i人目のお客さんが来たときにまだドアが開いていれば、被っている時間(赤い部分)をTから引いた分だけ加算するドアが閉じていればTだけ時間を加算するという方針で行きました。これなら計算量O(N)なのでpythonでも問題なく通ります。自動ドアが開き続ける時間Tが一定だからこんなにシンプルに書けてるんだなあと。ドアの開き続ける時間がバラバラだと、もう少しだけ工夫が必要ですね。解説放送でimos法でやったってコメントがあったのでやってみました。time))計算量はO(10**6+T)、時間は1206msでした。上の配列を使わない方法は376ms。オーダーが一桁違うだけで大分違いますね。民族大移動それぞれの民族が目的の街に移動できる一番早い日を答える問題。ため、難しいこと考えずに民族ごとに何日でたどり着けるか求めれば大丈夫でした。愚直に解いたら良かったorz解説では貪欲に解けるって話をされていて、言われてみればそうだなって感じです。あればOKという方針でやっています。1貪欲な方法もあとからやってみました。T)わざわざmove_leftとmove_right作ってるんですが、pythonはif文が遅いのでこれが大分効いてます。貪欲の方が360msでした。頑張ろうとしてたりしたんですけど、108以上の階乗が必要になってきてどうしようってずっと悩んでました。あとから方程式で求めれるって気付いたときにはもう手遅れ。逆元の事分かってなかったのでどっちにしろ無理だったと思います。(2)と(3)を組み合わせて、この連立方程式を解いたものがこちら。modをとったものが答えになるの実は少し納得いってないんですが、時間がないので割愛。今回一番勉強になったのは逆元の話でした。あったとき,が成り立つというもの。加減乗算に関してはmodとっても大丈夫だと知ってましたが、除算だとこんなことするんですね。この逆元ですが、法が素数pであった場合はフェルマーの小定理によりが成り立つそうです。素数なので使うことが出来ます。一つ勉強になったのは冪乗を高速に求めるアルゴリズム。解説聞いたときにピンと来てなかったんですが、あとから納得しました。求めるときに、Nの二進数表示を考えると、の形に分解できることを利用してます。二進表記は1011なのでに分解できるわけですね、なるほどなるほど。高速で求められるのでXの逆元を求めれます。冪乗の高速計算は他でも使えそうな知識なので覚えていて損はなさそうです。次のABCこそは全完目指したいなあ。俵言は、Amazon.co.jpを宣伝しリンクすることによってサイトが紹介料を獲得できる手段を提供することを目的に設定されたアフィリエイト宣伝プログラムである、Amazonアソシエイト・プログラムの参加者です。はてなブログをはじめよう!Tawaraさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。