問題 直線上にビー玉がいくつかあって，ビー玉は各ビー玉に割り当てられたコストを払うことで固定することができる． ビー玉を質点とし，左へ転がる場合，(固定したビー玉のコストの和)+(動いたビー玉の距離の和)を最小化する． ただし，各ビー玉の位置と固…

久しぶりの参加．

問題 文字列Tがあった時，それをi個だけ横に循環シフトしたものをT(i)とする．ここで，T(i)=Tとなるiの個数がKの時，この文字列をmagicwordと呼ぶ． 文字列の配列Sと個数Kが与えられ，その配列の文字列を順列で並び替えてくっつけた大きな文字列のうちmagicw…

問題 2つの数列の要素同士で組を作り，その組の掛け算の和の最小値を返す． 考え方 和を最小化するので，なるべく大きい数字*小さい数字にしなければいけない． 片方を昇順ソート，もう片方を降順ソートしてそれぞれ掛け合わせればいい．

問題 36進数(0-9A-Z)で考える．36進数で使われる文字のうちk個の文字をZに置き換えられるとき，36進数の文字列の配列の和で可能な最大値を返す．leading zerosは許されない． 考え方 実装． 36進数で使われる文字のうちk個を選んだ組み合わせをそのまま計算…

問題 数字の2次元配列が与えられる．行iと列jがそれぞれ等差数列になるように変化する場合，それで構成される数列で完全平方数となる最大の数字を返す． 考え方 それぞれのインデックスが{1,3,5,7}だったり{5,4,3}とかの場所で数字を構成する． なので，テー…

問題 5つの数字が与えられる．これらの数字の「least majority multiple」とはこれらの数字の3つ以上で割ることができる最小の整数である．このleast majority multipleを返す． 考え方 3つを選んでその3つの最小公倍数で一番小さいものを返す． 3つ以上とあ…

問題 2分木で構成される細胞がある．各細胞の親の番号と途中で死んでしまう細胞の番号が与えられる．この時，最終的に生き残る端の細胞はいくつか． 考え方 生きているかどうかを表すbool配列に記録していった．最後に残っている途中の細胞も消してカウント．

問題 スキー板と路面の各領域での摩擦値が与えられる．スキー板と路面の和で最大の摩擦の部分だけ滑るのに時間がかかる．全部滑りきるまでにかかる時間を求める． 考え方 やるだけ．

問題 友達かどうかを表す隣接行列(対称)が与えられる．「2-friends」とは，Aについて「AとBが友達同士」もしくは「Aの友達Bの友達C」となるB，Cを指す．この2-friendsの友達数が最大の人のその友達の数を返す． 考え方 距離1または2である頂点の数．ワーシャ…

問題 野鳥が全部でbNいる．一日のはじめにcPDだけ捕まえて調査し夜には放す．調査では鳥の足にマークをつける(すでについてたらそのまま放す)．dN日繰り返したあとで，マークが付いている鳥の数がbMである確率を求める． 考え方 dpかdfs． dp[日][マークの付…

問題 1つしかレジスタがないコンピュータに命令を送って処理させる．入力sと出力tが与えられるので，sからtを作るための一番短い命令列を返す．命令は，「+」「-」「*」「/」がありそれぞれ「レジスタの値 op レジスタの値」が結果としてレジスタの新しい値…

問題 文字列が与えられる．それを単語に区切ったときに略語に変換する．「スペースはそのまま」「母音のみの単語はそのまま」「子音が1つでもあれば，母音をすべてなくして，元の単語で子音が続かないものだけ残す」． 考え方 書いてある通りにやるだけ．単…

非常にくやしいミス．

問題 10進数の正の整数nの各桁をswapする．全部でk回swapするとき，できあがる最大の値を返す． 考え方 全探索+メモした． 最大の数字と交換するというgreedyだと，n=35766,k=3のとき「36635」だけど，正解は「36653」で間違い． メモ化は，グローバルにmemo…

久しぶりにどっちも解けた．

参加してた。2完1半。

問題 2台の砲台から2か所の軍事施設を攻撃する．ただし，2発目を撃つための時間やミサイルの速度が与えられる．2か所を破壊するまでにかかる最小時間を返す． 考え方 やるだけ． いくつかのパターンにわけれるので，そのパターンをそれぞれ調べるだけ． 反省…

問題 lucky番号がいくつか与えられる．ある範囲[x,y]にこのlucky番号が含まれないと不幸．ある数字nを含む範囲が不幸である組み合わせはいくつあるか． 考え方 lucky番号の集合をソートして，どの範囲にnがあるかを見つける． その範囲[x,y]でnを含むx,yの組…

0223 BFSで探索した． 一応メモ化して同じ状態を何度も計算しないようにした．

問題 ある等差数列がある．しかし，偶数が嫌いな人がいるので，全部奇数になるように直してある数列が与えられる． そこから元の等差数列を見つけて返す． 考え方 最初のa[0]とa[1]が決まれば他のa[i]は自動的に決定できる． なので，このa[0]とa[1]について…

問題 末尾に9が続くような価格の賞品が人気を呼ぶ街で電子レンジを売る．9099の場合，末尾に9が2つ．0999だと9が3つなので，2つのモノより売れることがわかる．ある範囲minPriceからmaxPriceの中で一番人気の出る価格を返す． 考え方 やるだけ． "末尾に"連…

ひさしぶりに．爆死．

新しい問題を少々．

問題 ある文字列が与えられる．それが回文になるためには「1文字挿入する」「1文字消す」「1文字を他の文字と変える」「2つの文字を交換する」の操作を最低何回行わなければならないか． 考え方 編集距離(レーベンシュタイン距離)． 文字列aと文字列bの文字…

問題 N本のいくらでも水が入るボトルがある．最初それぞれ1リットルずつ入っている．同じ水の量の2つのボトルは1つに合わせることができたとき，K本以下にするには1リットルのボトルを何個追加すればいいか． 考え方 すべてのボトルは最初全て１リットルであ…

問題 あるグリッドが与えられる．各要素は0から9までの数値がはいってる．四つ角が同じ数字になるような正方形の最大の面積を求める． 1255 3455 なら5で面積が４の正方形があるのでこれを返す． 考え方 あるセル(i, j)から一辺がkの正方形を作ることを考え…

時間を勘違いしてて参加できなかった．眠いのでとりあえず2問だけやった．

問題 迷路が与えられる。迷路をねずみがゴールまで進む時、分岐点はいくつあったかを求める。 考え方 制約に「there will exist exactly one path between them.」とあるのでdfsで計算できる。 再帰するときに分岐点数を保持しておいて、分岐点を通ったら+1…

問題 ある重力加速度gの環境で何個かボールを落とす。1個目が地面についたら2個目、、のように次々に落とす。それぞれのボールを落とす高さhiと全部のボールが落ちた時間Tが与えられた時、重力加速度を求める問題。高さと重力加速度と時間の関係式は与えられ…