ik-fibTweet前回に引き続き、SRM参加したので、簡易解説もどきと一緒にコードを貼っていきます。今回は、システムの不具合か本来日曜開催だったのが水曜に延期の上、延期された時間から更に1時間遅延しての開始という状態でした。飾り付けの星とリボンがあり、リボンiはx[i]とy[i]の星をつなぐ。この時、違う色の星を結ぶリボンが何本あるか答える。COL[i]は星の色を表し、{x,y}[i]はその星の色がcol[{x,y}[i]]の色であることを表している。星の数は最大50なので、全てのx,yについて色が等しいか否かの数を数えればOKです。x[i]で表しているcolの位置は1-indexedに対して、colはvectorで与えられるので、o-indexedになります。そこの変換を忘れると失敗します。なる数値をx=1から初めて、(2^k-1)まで繰り返し数える。tableで与えられる禁止数字のリストがあり、そのリストの数値およびその数値から始まる2x,2x+1はカウントしない。kとtableが与えられるので、作ることのできる数の総数を答える。解法kは最大40、すなわち2^40(>10^12)まであるので、1から初めて全ての2x,2x+1を繰り返し計算していると間に合いません。この数値を合計((2^k)-1)から引いていくことで最終的な総数を求めることができます。注意する点として、その禁止リストの数字が親となる2分木で共通する、すなわちすでにその箇所の数値を合計から引いている箇所を再び探索する可能性があります。そのため、数値を最初に昇順でソートして、その数値の親をたどった時すでに探索済みか否かを判定します。親はi/2を繰り返すことでたどることができるので、その全ての数値が禁止リストの数字でなければ、その数値以降の木の数値は未処理のため、その木の数値を削除します。BoardFoldingDiv2コンテスト中に問題把握すらしきれなかったでしたので、後日追記します。コメントをキャンセルメールアドレスが公開されることはありません。コメントデータの処理方法の詳細はこちらをご覧ください。ik-fib東京のどこかの会社のエンジニア基本的に思考も行動もカオスです。WordPress.com.。