WARushスマートフォン用の表示で見るWARushSRMの結果とか、解けた問題のコードを書いていきますこの広告は、90日以上更新していないブログに表示しています。Statement訳アンドリューはダイアル錠を持っている。この鍵は複数のダイヤルが並ぶようにしてできている。それぞれのダイヤルは0~9の数字が順番に並んでいる。各ダイヤルでは、ただ1つの数字が見えるようになっている。combination"と呼ぶ。ダイヤルでの見えている数字は、それを上か下に回すことによって変えることができる。上に回せば0が1に、1が2に、となっていく。9ならば0が再び見えるようになる。下に回す場合は、この逆である。隣接したものならば、複数のダイアルを一気に回すこともできる。正確には、隣接した複数のダイヤルを1ステップで同じ方向にいっぺんに回すことができる。combinationが"123"だとする。1ステップで"012"(全てのダイヤルを下に回す)や、"133"(真ん中のダイヤルを上に)や、"013"(最初と2番目のダイヤルを下に)など、いろいろ変えることができる。"123"を"224"と1ステップではできない。combinationである。ダイヤルを回転させることによってSからTへと変化させ、鍵を開けたい。最小のステップ数を返せ。2500Editorialsを見てDiv2の簡単版はN(ダイヤルの数)=50なので、O(N^3)でいけた。Div1では2500となり、O(N^3)なんてやってられない。するか?どうやらDiv2の考え方をそのままに、最適化すると(N^2)まで減らせるとのこと。Div2では、状態(ダイヤルの位置・回した方向・回した数)のそれぞれを更新するのに、MAX_OP回=O(N)かかっていたが、ここが無駄らしい。ダイヤルの初期状態がこんな感じだとする。AB例えば、ダイヤルAをプラス方向に15回して揃えました~って時に、ダイヤルBを1003回して揃えた時のコストはいくつかな?とか考える必要あるかと言われれば、確かに無駄である。ダイヤルA・プラス方向・15回。いう情報を元に、ダイヤルBを更新するとき、以下の3パターンだけ考えればよい。1.足りない分は頑張ってもうちょい回してみるプラス方向に15回してダイヤルAを揃えたということは、ダイヤルBもプラス方向に15回までなら、コスト0で回せるということである。それで回しが足りない場合が当然ある。例に沿うと、Bをプラス方向に15回すと3になり、目標の5まで2回足りない。そこを頑張ってさらに2回回して揃えてみようか、というやり方である。コストは2だけ余計にかかってしまうが、B以降のダイヤルは、コスト0で17も自由に回せるようになる。2.途中でそろったからなまけるプラス方向に15回すうちに、ダイヤルBが目標の数字は通り過ぎている。15回さないで、ダイヤルBを途中で止めればよくね?5で止めちゃえばよくね?という回し方もある。確かにこれだとコストをさらにかけることなく、ダイヤルBを揃えることができる。5へと7回しか回していないので、B以降のダイヤルは、コスト0で回せる幅が7回に狭まってしまう。3.流れに逆らう前までプラス方向に回していたなんて関係ねぇ。いうことで、あえてマイナス方向に回すやり方もある。前のダイヤルたちが頑張って、コスト0でプラス方向に15回せるようにしてくれた訳だが、その恩恵は受けられず、コストは3かかる。B以降のダイヤルは、コスト0でプラス方向に回せなくなる代わりに、マイナス方向に3まで回せるようになる。"ABBADiv1"月別アーカイブリンクはてなブログブログをはじめる(無料)お知らせはてなブログをはじめよう!Ekaingさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。