問題 チェスの団体戦を行う。自チームと相手チームの各人の強さが数値で与えられる。勝てば2ポイント、引き分けで1ポイント得点が入るとする。相手チームとの組み合わせを好きにできるとき、自チームの最大の得点を求めよ。 やりかた 強さでソートした上でDP…
問題 やりかた 問題では頂点から出ている辺が3本以上の時を星として数えているが、2本の時、1本の時、0本の時もそれらを星と認めると、出次数がnの頂点で構成される星の総数はになる。このうち2本の星と1本の星と0本の星の総数はになるので2^nからこれらの数…
問題 半径5の円に内接する三角形の面積の最大値を求めよ。ただし、頂点は角度angleFrom[i]からangleTo[i]の間になければならない。角度は1000分の1度で与えられる。 やりかた 頂点の位置に関して4つのケースが有る。 すべての頂点が、角度範囲の境界にあると…
問題 あなたは川の中にいて、2次元座標上の原点から目的地(x,y)に向かって速さVで泳ぎだす。川はx軸正方向に速さUで流れている。目的地に着くための最小の時間を求めよ。 やりかた t秒後に着くとすると、ある方向に距離Vt進んでいった時にちょうどゴールにつ…
問題 数列Aと整数Pが与えられる。を満たす整数Xの個数を求めよ。 やりかた 数列の中央値に近い部分をXとすると題意の和は最も小さくなり、中央値から離れると和は大きくなっていく。式を満たすXは中央値付近でひとつづきに現れるので、これらの内の最大値と…
問題 電車がx軸正方向に速さtrainSpeedで動いている。電車は車両数がnCarriagesで車両の長さはいずれもlengthである。時刻0の時点では電車の左端が座標0に位置している。この左端に強盗が立っており、時刻0になると電車の屋根の上を速さrobberSpeedで右端に…
問題 NxNのチェスボード上にいくつかのナイトが置かれておりそれらの位置がposで与えられる。（表記の仕方は問題文参照） 任意のナイトを一回だけ移動した時に、移動先に別のナイトがいないようにしたい。取り除かねばならない最小のナイトの数を求めよ。 や…
問題 飛行機を使ってdistanceの距離を移動したい。xリットル給油するとの距離を航行できる。それとは別に離陸して高度を得るまでにtakeoffFuelリットル燃料を消費する。着陸した地点で必ず給油できるものとしたとき、distanceの距離を航行するのに必要な燃料…
問題 どの要素も互いの接頭辞にならないような文字列の集合をprefixfreeな集合と言う。与えられた文字列の集合のうちprefixfreeとなるような部分集合の数を求めよ。空集合も含める。 やりかた メモ化再帰による。 文字列をソートするとprefixfreeとならない…
問題 長さLの丸太がある。この丸太はK箇所で切断でき、位置はであたえられる。この丸太を最大C箇所で切断できるとした時に、もっとも長い丸太を最小化せよ。返す値は最小化した値と最初に切断する位置とせよ。最初の切断位置が複数取れる場合は最も小さい値…
問題 6x6のチェス盤があり、セルには石と旗の2種類の障害物がある。右下の4セルにコインが置かれており、これらのコインは隣接する空白のセルに移動できる。また、隣接するセルに別のコインが置いてある、もしくは石が置いてある場合で、更に隣のセルが開い…
問題 面数がmaxSideのサイコロをnDice個ふる。少なくとも1つがvの目を出す条件のもと、出た目の和がtheSum以上になる確率を求めよ。 やりかた 条件付き確率を求める問題。まずvの目が一回は出つつ、合計がtheSum以上になる同時確率をdpで求める。 dp[k][i][j…
問題 N人の人がいて、それぞれの身長がheights[]で与えられる。これらを車座に配置した時に隣り合う身長差の最大値が最小化するような配置パターンを求めよ。複数あるときには身長差順で辞書式最小なものを返せ。 やりかた 単純に身長差順で配置すると最後の…
問題 （意訳）数直線上に線分が幾つか与えられる。任意の地点で重複する線分はseats以下にしたい。取り除かねばならない線分の最小の数を求めよ。ただし線分の端点は重複と数えない。 問題 線分の右端でソートして貪欲。 ソートした上で数直線上を最初から見…
問題 目の数が異なるサイコロが複数与えられる。各サイコロの目の数はsides[]である。サイコロを一斉に降った時に、サイコロを区別しないとして出る目のパターン数を求めよ。 やりかた サイコロを目の数でソートしてDP。 dp[i][j]:=（サイコロを目の数の小さ…
問題 'A'から'Z'までの26種類の物質が存在しており、あなたが持っている物質は文字列initialで表されている。また、いくつかの物質を1つずつ組合わせて別の物質を1つ錬金することができ、これらの組合せがreactionsに記述されている。持ち合わせている物質か…
問題 CSの授業がいくつか用意されており、i番目の授業にはtheoreticalValue[i]とpracticalValue[i]とexpire[i]という3つの数値が与えられている。各授業の履修期間は一ヶ月で、あなたはひと月に授業を一つだけ取ることができる。そしてあなたは理論スキルと…
問題 長さarrayLengthの配列がある。ここから無作為に2つの要素を取り出し、交換する動作をswapCount回行う。この後に当初a番目にあった要素がb番目に移動している確率を求めよ。 やりかた 典型的なDP。 dp[0][i]:=（i回スワップした後にbに移動している確率…
問題 コインが複数種類あり、それらの金額が与えられる。各金額のコインは無尽蔵にあるとする。1～Xまでのすべての金額を支払えるようにコインを選ぶとき、このコインの枚数を最小化せよ。 やりかた 公式解説を参考にしました。 ある時点で選んだコインの総…
問題 都市がいくつかあり、都市間の道の情報とその道を壊すコストが与えられる。任意の都市間で往来ができるように道路が敷かれており、そのパスは必ず1つだけである（要は閉路がない）。敵に征圧された街の番号が与えられるので、道路をいくつか壊して、征…
問題 グリッド上の町にN人の競技者がいて、i番目の競技者が(street[i], avenue[i])にいる。競技者は道路の交差した位置で出会うと競技を行って勝敗を決める。この競技で総当り戦を行うとき、全競技者の総移動量を最小化せよ。 やりかた どこかの交差点に全員…
問題 2x1セルのドミノが複数あり、各セルには0~9の数字が書かれている。ドミノの右側の数字とその隣のドミノの左側の数字が同じになるようにドミノをつなげていき、ドミノがループをなるようにする（最左のドミノの左セルと最右のドミノの右セルの数字がおな…
問題 プログラミングコンテストがいくつか開かれ、それらの開始時間、終了時間、勝率が空白で区切られた１つの文字列"s t p"の形式で与えられる。あるコンテストに出場している間は他のコンテストには出場できない。最適な出場の仕方をした時に、勝てるコン…
問題 直線の棒がいくつか与えられ、それらの長さはpieces[]である。この棒からいくつか選んで長さL上の板の上に、はみ出ないように、かつ区間が互いに重ならないように置いていく。棒を置いていない区間に残りの棒が１つも置けないようになったら終了とする…
問題 4x4の数独があり、ところどころは数字で埋められている。この状態での正解パターン数を求めよ。 やりかた 深さ優先探索で通る。1～4の順列を生成して各行を試していき、マスが全部埋まったところで正解かどうか調べればいい。マスが小さいので枝刈りは…
問題 フェンスが複数あり、それらの長さが与えられる。フェンスを使って三角形をいくつか作るとき、できた三角形の面積の総和を最大化せよ。ただし、複数のフェンスを使って1辺とすることや、1つのフェンスを複数に分割することはできない。 やりかた bitDP…
問題 各ノード間の距離が与えられる。任意の2点間の最短距離を求めた時、それらのなかで最長距離を求めよ。 やりかた Warshall-Floydして、最長のものを求める。 class EscapingJail { public: int p(char c){ if('0' <= c && c <= '9') return c - '0'; if(…
問題 文字列がいくつか与えられる。これらをすべて連結してできた文字列のうち、'?'をランダムに置き換える。その文字列の部分文字列のうち回文の個数の期待値を求めよ。文字列長 やりかた 文字を一つ選び、それを中心に文字列を左右に広げていき、それが回…
問題 数字xとyがあたえられる。数字には0個以上の!がついており、これは階乗演算を表す。x,yの大小比較をせよ。 やりかた たとえば100!!!と1000!!を比較するとき、!の多いほうが、少ない方と同じになるまで階乗計算を行えばあとは数字の部分を比較するだけで…
Div1 Easyの556～615、315～354の計100問を2周した（2周目はできなかったもののみ）。ほぼ予定通り。これで315～615のEasyは埋めることができた。 引き続き、要復習のものに絞って3週目を行う予定。ほとんどブログを更新できなかったのがちょっと残念だった。
