これに違反したら0通り。かけた値が、答えとなる。「偶数本の辺」と聞いたら「二部グラフ」と答える。(本当か?)今回の場合、頂点をAグループとBグループに2分割してしまえば、Aの1点とBの1点を結ぶ辺は、全て同じレベルに設定してよい。同じ頂点に戻ってくるには偶数本の辺を通るしか無いことは明らかである。8さて、こうした場合に残る辺を考える。これは先ほどの二部グラフにおける同一グループ同士を結ぶ辺であり、しかもそれぞれで完全グラフとなっている。小さい元の問題に帰着できるので、再帰的に解ける。頂点を2分割する場合、単純に2等分(奇数の場合はどちらかが1つ多い)でよい。頂点数に対して必要なレベルは広義単調増加なので、全体のレベルを低く抑えるには、分割後のグループの大きい方を最小化した方がよい。「この解法で最小化するなら2等分がいい」ことは言えるが、そもそもこの解法で最小化できるかの証明は、いまいちできていない。1:])解説pdfやYouTubeでは、Bitを使った解法が、最小値の証明付きで紹介されていた。番号を付けて、その2進数表記から、2頂点間の辺に設定するべきレベルが求まる。1001この時、xorで1が立っているビットの桁(この場合1,4のいずれか)を、19と26の間にはる辺のレベルとしてよい。「レベル」を「辺を辿る時に、頂点番号の下から[レベル]ビット目に注目する」と解釈する。そのビットが0である頂点と1である頂点の間にのみ辺を貼るようにすれば、これは二部グラフになる。12つの頂点番号のXORで1が立っている桁が、両者が異なっている桁であるため、その中から1つ選んでレベルに設定すればよい。どれを選んでもよいが、Pythonではn.bit_length()で最上位の桁を取れるため、記述が簡潔になる。以上の理由から、頂点番号は必ずしも0からの連番である必要は無い。仮に全く同じ頂点番号の2点が含まれてしまうと、その2点間に設定できるレベルが無くなってしまうため、頂点番号は全て異なっている必要がある。2進数表記の桁数分のレベルは、必ず必要になる。ソースコードはめちゃんこ短くなる。10^5$解法カードに書かれた値の大きい方から貪欲。取ってよいかの判定がやや難しい。数字の大きいカードを考えると、これは必ず取られる。取られなかった場合と比較して、そのマスが該当する行と列のいずれかで、最大のカードを取るようにした方がよくなる。次に大きい8,7も、必ず取られる。行と列のいずれかで8,7に変更できる余地が残っている。└──┴──┘しかし、5は、もう5が所属する行・列のいずれでも、それより大きい数字で取られることが決まっており、組み替える余地も無い。5を取るならそれより大きいカードを1枚諦めざるを得ないため、取る意味が無い。この「組み替える余地も無い」というのは、どうやって判定すればよいか。行と列に記号を割り振る。└──┴──┘この時、9は「AかD」、8は「AかC」、7は「AかD」で取る。この行/列が繋がっている範囲内では、各数字を取る行/列は互いに融通できる。(行/列が繋がっているとは、「AかD」と「AかC」があった時に、共通のAを介して「A-C-D」が繋がっているということを表す)しかし、行・列とも1つずつしか取れないので、繋がっている行/列数より多いカードは取れない。5は「AかC」で取れるが、この時、繋がっている「A-C-D」の3つは既に9,8,7で埋まっており、取れない。次に大きい4は「BかC」で取れるが、これはつながりが「A-B-C-D」に拡張され、もう1枠空くことになるため、取れる。ikatakosメディアマネージャー文書の先頭へ。