WARushスマートフォン用の表示で見るWARushSRMの結果とか、解けた問題のコードを書いていきますこの広告は、90日以上更新していないブログに表示しています。Statement訳カラーランドにおける通貨は様々な種類のコインによって成り立っている。コインの額面には次の3つのルールがある。額面は一意の正の整数である。1円のコインが必ずある。額面が違うコインのペアは、必ず割り切れるようになっている。valuesが与えられる。異なる額面のコインを見分ける方法は、それに塗られた色によってのみである。カラーランドにある各コインは一色の色で塗られており、次のような単純なルールがある。同じ額面のコインは同じ色で塗られている。違う額面の2つのコインが同じ色で塗られていることはない。あなたは額面の全ての種類を知っていはいたが、それぞれがどんな色で塗られているかは知らなかった。どのような色が使われているかも知らないでいる。あなたはそれぞれの額面にどんな色が使われているか知りたくなった。それを成し遂げるため、無限大の額が使えるキャッシュカードを使用することにする。あとは無限大のお金を引き出せるATMを操作する。1回の操作ではATMから何円引き出すかを指定することができる。ATMは指定された金額を払いだす。あなたは、ATMがコインの数がなるべく少なくなるように払い出す事を知っている。(このルールにより、払いだされるコインの種類とその数は一意に決定されることに注意して欲しい)あなたが全ての額面と、その色を認識するために、最小何回ATMを操作すればよいかを返せ。1考えたこと(1日以上・・・)ATMからめちゃくちゃ大きな金額を引き落とせば、一番高いコインをたくさん出せるため、一番でかい額面のコインはすぐ判断できる。1円~2番目に高いコインは一度に出せる数に制限がある。1円、3円、6円とあったら、1円は2枚しか出せないし、3円は1枚しか出せない。ATMがコインの枚数を最小化するためである。操作の特徴はこんな感じ。と全て1枚しか出せない場合を考えてみる。効率よく見分ける方法は、2分木的に出す出さないを繰り返すといい。いうことかというと、下の図のようにそれぞれの額面を葉に見立てて2分木を作って、左の子は出さない、右の子は出す、みたいにやる。「出ない・出た・出ない」←これ4円玉だな「出る・出る・出ない」←これ64円玉だなとなり、8種類を3回で見分けることができる。実際には全ての色を1回は出さなくてはいけないので、「出ない・出ない・出ない」のパターンを除いて7種類見分けることができる。63]なので最大6回操作を行えばよいことになる。問題ではコインは1枚出せたり2枚・5枚と出せる場合もあり、それが混在している。これをどうするか・・。2枚だせるコインは0枚出す・1枚出す・2枚出すの3パターン使えるため、N回の操作でN^3-1種類見分けることができる。ここは操作回数を2回に固定して考えてみる。8種類のコインを見分けることが可能。観察すると、1枚しかだせないコインがあったとしても、ここに潜り込ませられることが分かる。矢印で示すコインは判別するのに1枚のコインしか使っていないため、2回の操作だと1枚しか出せないコインを3種類までなら判別することができるのだ。同様に、2回の操作だと2枚まで出せるコインを7枚まで判別することができ、3枚まで出せるコインだと15枚(2^4-1)まで判別可能となる。まとめると、2回の操作で全てのコインを判別できるかは、1枚まで出せるコイン・・・・・3種類まで1~2枚まで出せるコイン・・・7種類まで1~3枚まで出せるコイン・・・15種類まで1~4枚まで出せるコイン・・・31種類まで。これらを全て満たせばよいことになる。これを1回~6回の操作までで判断してやれば答えとなる。"ABBADiv1"月別アーカイブリンクはてなブログブログをはじめる(無料)お知らせはてなブログをはじめよう!Ekaingさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。