blog主に競プロ問題の解説を載せてますこの広告は、90日以上更新していないブログに表示しています。コンテスト久しぶりに全完できたけどD問題で時間がかかりすぎた。木の基本的な知識が抜けてた。高橋くんと年齢3つの数字が与えられるので、その中の中央値(2番目に小さい値)を答えよ。なる文字列sが与えられる。aaabbbccdをa3b3c2d1のように圧縮する圧縮法をsに適用したときの結果を答えよ。空文字列のansを用意する。前から順番に見ていき、異なる文字が出てくるたびに圧縮結果をansに足していけばいい。ループから抜けた後の足し忘れに注意。高橋くんと魔法の箱ある値xをいれるとある値を返す箱がある。基本的に異なるxでは異なる値を返すが、xと2xは同じ値を返す。数列を与えらえるので、その数列に含まれるxを箱に入れると一体いくつの種類の値が出てくるかを答えよ。解法ある素因数の2の倍数はどれも同じ値を返すので、与えられた数列中の数字を2で割り切れるだけ割り、最後に異なる数がいくつあるかを数えればいい。50)の木が与えられる。それぞれの辺には重みがついており、各頂点間の距離はこの重みを足し合わせたものとする。今、ある2頂点間の距離を何度か尋ねることができる。そこから木の直径(最も距離の遠い2点間の距離)を推測して答えよ。部分点はすべての頂点間の組み合わせについて尋ね、その最大値を答えればいい。満点解法は、まず1とそれ以外の頂点の距離を訪ねる。これで最大49回の質問となる。そのあと1からもっとも遠い頂点とそれ以外の頂点の距離を訪ねる。その最大値が答えとなり、100回以下で木の直径が求まる。木の直径の求め方として、まずある点からもっとも遠い点を探し、さらにそのもっとも遠い点から一番遠い点を探すというのが一般的なアルゴリズムのようだ。読者になるリンクTopCoderCodeforcestwitterGitHubQiitaはてなブログをはじめよう!roiti46さんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。