解いた問題のソースコードと解説など。


POJ 3126 Prime Path

問題 素数が2つ与えられる。素数のいずれかの桁の数字を一つ書き換えて別の素数に変える操作を、与えられるひとつ目の素数から始めて、ふたつ目の素数に到達するまで行う。最短の操作回数を求めよ。ただし与えられる素数はともに4桁の素数で、経由する素数も…

POJ 3032 Card Trick

問題 マジシャンが1からnまでの数字が書かれたn枚のカードを次のような手順で場にディールしていく。1回目はカードデッキの一番上の1枚をデッキの一番下に移し、新たに一番上になった一枚をディール。 2回目はカードデッキの一番上の2枚をデッキの一番下に移…

POJ 3062 Celebrity jeopardy

POJ

問題 symbol = valueという形で変数が与えられるので、その変数を解に持つ最も簡素な形式の数式を出力せよ。 やりかた 最も簡単な形式はsymbol = valueという式そのもの以外にないのでそのまま出力すればいい。要は標準入力をそのまま標準出力にだせばいいだ…

POJ 2739 Sum of Consecutive Prime Numbers

問題 2以上10000以下の整数nが与えられる。nを連続する素数の和で表したい。何通りの方法があるか求めよ。素数一つで表せる場合も該当する。 やりかた エラトステネスの篩をして10000以下の素数の数列を求めておき、それらの部分数列の和を全列挙して該当す…

POJ 2909 Goldbach's Conjecture

問題 4以上の整数は2つの素数の和で表せる、という予想をゴールドバッハ予想という。4以上2^15以下の整数nが与えられるので和がnとなるような素数の組数を返せ。ただし(p1,p2)という組と(p2,p1)という組を別々に数えてないけない。 やりかた エラトステネス…

SRM 417 Div1 Medium CubeNets

問題 1x1x1のサイズの立方体の展開図が文字列として与えられる。'#'はそこが1x1のサイズの面であることを表し、'.'は面ではないことを表す。 この展開図は正しい展開図であるとは限らない。そこで文字列が与えられた時、正しい展開図となっているかを返せ。 …

POJ 2080 Calendar

POJ

問題 2000年1月1日からの経過日数が与えられる。何年何月何曜日か出力せよ。 やりかた 2000年からはじめて、その年の日数を計上していき与えられた数を超える年が答えとなる年。(コードでは数から日数を引いていき0以下になるとこで止めている) で、与えら…

SRM 414 Div1 Medium InfiniteSequence2

問題 i i >= 1 の場合、 で定義される数列がある。はxの床関数である。 を返せ。 やりかた 単純なメモ化再帰で通る。ただしすべてメモするとMLEなので100万くらいまでメモっておいてそれ以上大きい場合は、再帰を繰り返して計算するようにすると通る。以下ソ…

SRM 405 Div1 Medium AllCycleLengths

問題 連結な有向グラフが与えられる。ある頂点から再びその頂点に戻るような長さxのパスが存在するときxはvacation friendlyであるという。途中で頂点に一度戻るようなパスも可とする。 xを1から無限まで調査し、vacation friendlyなら1、そうでないなら0と…

SRM 398 Div1 Medium CountPaths

問題 高さr、幅cの長方形の盤面がある。(1,1)のコマから右隣か上に移動を繰り返してゴールの(r,c)まで行きたい。盤面には特別なコマがいくつかありそれらの位置はfieldrow、fieldcolで与えられる。ゴールに行くまでに特別なコマをx個通る手順数を1000007で割…

SRM 396 Div1 Medium FixImage

問題 #か.で描かれた絵がある。#と#が上下左右で隣り合っているとき、それらは接しているといい、接している#の集合を一つの連結成分ということにする。同じ連結成分に属している2つの#には道のりが定義でき、一方の#からもう一方の#までたどり着くまでに経…

SRM 392 Div1 Medium RoundAboutCircle

問題 円周上にノードが配置してあり、時計回りに1からNまでの番号が振られている。数字iのノードからはiの各桁の数字の和だけ時計回りに進むことができる。あるノードからスタートして移動中にすでに訪れたノードについたら終わりとする。任意のノードからス…

SRM 386 Div1 Medium PolygonCover

問題 XY座標上で点が与えられる。全ての点が少なくとも1つ以上の多角形に属するように多角形を配置する。それらの面積の和が最小となるように配置し、その和を返せ。多角形の頂点は常に与えられた点の上にしか置くことはできない。与えられた点は多角形の辺…

SRM 383 Div1 Medium FloorBoards

問題 1x1のタイル、もしくは1x1の障害物で構成されたサイズが10x10以下の部屋が与えられる。この部屋を1xNの棒で敷き詰めたい(Nは任意の正整数)。棒は部屋の幅もしくは奥行きに対して平行にしか置くことができず、一つのタイルに対して重複して置くことは…

SRM 377 Div1 Medium GameOnAGraph

問題 無向グラフが与えられる。各頂点は白か黒の色で塗られており、辺は異なる色の頂点間でのみ張られている。このグラフ上で次の手順でゲームを行う。 白と黒が交互に行い、初手は白である。 白のターンでは各黒の頂点にその頂点と隣接する白の頂点の点数を…

SRM 368 Div1 Medium PolylineUnion

問題 折れ線グラフが以下の形式で1つ以上与えられる。互いに交差している折れ線グラフを1つの集合と数えると、いくつの集合になるか。1つの折れ線は1つ以上の線分からなり、点同士は'-'で区切られ、点は','で区切られる2つの非負整数で表現される。' 'で区切…

SRM 365 Div1 Medium ArithmaticProgressions

問題 やりかた 以下ソース。 class ArithmeticProgressions { public: ll N, m, M; vector<ll> s; ll floor(ll a, ll b){ ll m = a % b; if(m < 0) m += b; return (a - m) / b; } ll ceil(ll a, ll b){ ll m = a % b; if(m < 0) m += b; if(m > 0) m = b - m; r</ll>…

SRM 356 Div1 Medium MarriageProblemRevised

SRM

問題 複数の男女がいる。かれらのお互いの友好度がpreferencesとして与えられる。preferences[i][j]が'1'のとき男iと女jは結婚に適しており、'0'のときは適していない。一夫多妻型か多夫一妻型の結婚が認められている(多夫多妻制は不可)ときにすべての男女…

SRM 354 Div1 Medium RemissiveSwaps

問題 整数Nが与えられる。好きな桁を2つ選んで、それらの数字を1つずつ減らしてそれらを交換するというゲームを行う。このゲームでとりうる最も大きい数字を求めよ。なおLeading Zeroができてはいけない。 やりかた ゲーム中に桁が増えるようなことはなく、…

SRM 353 Div1 Medium PlatformJumper

問題 足場をジャンプして渡り、コインを集めるゲームがある。足場の位置とそこにおいてあるコインの枚数が与えられる。 ゲームでは今いる足場からy座標上で下にある足場にしか移動はできない。足場は点として考えて良い。ジャンプには物理法則があり、ジャン…

SRM 399 Div1 Medium BinarySum

問題 3つの自然数a,b,cが与えられる。これらを2進数表記にした際に、最も大きい桁数を持つ数字と桁数が同じになるように残りの2つにleading zeroを足す。これらの数字について2進数上で1と0の順番を好きに入れ替えることで新たな数字a',b',c'を作る。なおlea…

SRM 395 Div1 Medium Skyscrapers

問題 1からNまでの高さを持つ、N棟の建物が一直線上に並んでいる。これらを左端から眺めた時に、i番目の建物が見えるというのは、0〜i-1番目の建物がi番目の建物より低い時である。右端から眺めた時に見える場合はi+1〜N-1番目の建物がi番目の建物より低い時…

SRM 384 Div1 Medium SchoolTrip

問題 何人かが円状に位置しており、一つのボールを互いに当て合うゲームをする。プレイヤーはボールを持っている時、自分以外の人を狙うものとし、i番目のプレイヤーがボールをもっている時に、このプレーヤーが狙った相手に当てることのできる確率はprobabi…

SRM375 DateFieldCorrection

問題 QWERTYキーボードにおいてキーとキーの距離とは隣接するキーをいくつ隔てて到達できるかによる。ただしスペースキーと隣接するキーとの距離は3と数える。(詳細は問題文中の図)"month day"という形式で日付が与えられる。この日付はミスタイプされてい…

SRM 371 Div1 Medium ChessMatchUp

問題 チェスの団体戦を行う。自チームと相手チームの各人の強さが数値で与えられる。勝てば2ポイント、引き分けで1ポイント得点が入るとする。相手チームとの組み合わせを好きにできるとき、自チームの最大の得点を求めよ。 やりかた 強さでソートした上でDP…

SRM 350 Div1 Medium StarsInGraphs

問題 やりかた 問題では頂点から出ている辺が3本以上の時を星として数えているが、2本の時、1本の時、0本の時もそれらを星と認めると、出次数がnの頂点で構成される星の総数はになる。このうち2本の星と1本の星と0本の星の総数はになるので2^nからこれらの数…

SRM 326 Div1 Medium InscribedTriangles

SRM

問題 半径5の円に内接する三角形の面積の最大値を求めよ。ただし、頂点は角度angleFrom[i]からangleTo[i]の間になければならない。角度は1000分の1度で与えられる。 やりかた 頂点の位置に関して4つのケースが有る。 すべての頂点が、角度範囲の境界にあると…

SRM 323 Div1 Medium Survived

SRM

問題 あなたは川の中にいて、2次元座標上の原点から目的地(x,y)に向かって速さVで泳ぎだす。川はx軸正方向に速さUで流れている。目的地に着くための最小の時間を求めよ。 やりかた t秒後に着くとすると、ある方向に距離Vt進んでいった時にちょうどゴールにつ…

SRM 325 Div1 Medium ModularInequality

問題 数列Aと整数Pが与えられる。を満たす整数Xの個数を求めよ。 やりかた 数列の中央値に近い部分をXとすると題意の和は最も小さくなり、中央値から離れると和は大きくなっていく。式を満たすXは中央値付近でひとつづきに現れるので、これらの内の最大値と…

SRM 307 Div1 Medium TrainRobber

SRM

問題 電車がx軸正方向に速さtrainSpeedで動いている。電車は車両数がnCarriagesで車両の長さはいずれもlengthである。時刻0の時点では電車の左端が座標0に位置している。この左端に強盗が立っており、時刻0になると電車の屋根の上を速さrobberSpeedで右端に…

SRM 303 Div1 Medium Knights

問題 NxNのチェスボード上にいくつかのナイトが置かれておりそれらの位置がposで与えられる。(表記の仕方は問題文参照) 任意のナイトを一回だけ移動した時に、移動先に別のナイトがいないようにしたい。取り除かねばならない最小のナイトの数を求めよ。 や…

SRM 347 Div1 Medium FlightScheduler

問題 飛行機を使ってdistanceの距離を移動したい。xリットル給油するとの距離を航行できる。それとは別に離陸して高度を得るまでにtakeoffFuelリットル燃料を消費する。着陸した地点で必ず給油できるものとしたとき、distanceの距離を航行するのに必要な燃料…

SRM 330 Div1 Medium PrefixFreeSubsets

問題 どの要素も互いの接頭辞にならないような文字列の集合をprefixfreeな集合と言う。与えられた文字列の集合のうちprefixfreeとなるような部分集合の数を求めよ。空集合も含める。 やりかた メモ化再帰による。 文字列をソートするとprefixfreeとならない…

SRM 329 Div1 Medium LogCutter

問題 長さLの丸太がある。この丸太はK箇所で切断でき、位置はであたえられる。この丸太を最大C箇所で切断できるとした時に、もっとも長い丸太を最小化せよ。返す値は最小化した値と最初に切断する位置とせよ。最初の切断位置が複数取れる場合は最も小さい値…

SRM 308 Div1 Medium CornersGame

問題 6x6のチェス盤があり、セルには石と旗の2種類の障害物がある。右下の4セルにコインが置かれており、これらのコインは隣接する空白のセルに移動できる。また、隣接するセルに別のコインが置いてある、もしくは石が置いてある場合で、更に隣のセルが開い…

SRM 304 Div1 Medium Conditional

問題 面数がmaxSideのサイコロをnDice個ふる。少なくとも1つがvの目を出す条件のもと、出た目の和がtheSum以上になる確率を求めよ。 やりかた 条件付き確率を求める問題。まずvの目が一回は出つつ、合計がtheSum以上になる同時確率をdpで求める。 dp[k][i][j…

SRM 346 Div1 Medium HeightRound

SRM

問題 N人の人がいて、それぞれの身長がheights[]で与えられる。これらを車座に配置した時に隣り合う身長差の最大値が最小化するような配置パターンを求めよ。複数あるときには身長差順で辞書式最小なものを返せ。 やりかた 単純に身長差順で配置すると最後の…

SRM 348 Div1 Medium RailwayTickets

問題 (意訳)数直線上に線分が幾つか与えられる。任意の地点で重複する線分はseats以下にしたい。取り除かねばならない線分の最小の数を求めよ。ただし線分の端点は重複と数えない。 問題 線分の右端でソートして貪欲。 ソートした上で数直線上を最初から見…

SRM 349 Div1 Medium DiceGames

問題 目の数が異なるサイコロが複数与えられる。各サイコロの目の数はsides[]である。サイコロを一斉に降った時に、サイコロを区別しないとして出る目のパターン数を求めよ。 やりかた サイコロを目の数でソートしてDP。 dp[i][j]:=(サイコロを目の数の小さ…

SRM 344 Div1 Medium QuantumAlchemy

問題 'A'から'Z'までの26種類の物質が存在しており、あなたが持っている物質は文字列initialで表されている。また、いくつかの物質を1つずつ組合わせて別の物質を1つ錬金することができ、これらの組合せがreactionsに記述されている。持ち合わせている物質か…

SRM 340 Div1 Medium CsCourses

問題 CSの授業がいくつか用意されており、i番目の授業にはtheoreticalValue[i]とpracticalValue[i]とexpire[i]という3つの数値が与えられている。各授業の履修期間は一ヶ月で、あなたはひと月に授業を一つだけ取ることができる。そしてあなたは理論スキルと…

SRM 338 Div1 Medium RandomSwaps

問題 長さarrayLengthの配列がある。ここから無作為に2つの要素を取り出し、交換する動作をswapCount回行う。この後に当初a番目にあった要素がb番目に移動している確率を求めよ。 やりかた 典型的なDP。 dp[0][i]:=(i回スワップした後にbに移動している確率…

SRM 331 Div1 Medium Shopping

問題 コインが複数種類あり、それらの金額が与えられる。各金額のコインは無尽蔵にあるとする。1~Xまでのすべての金額を支払えるようにコインを選ぶとき、このコインの枚数を最小化せよ。 やりかた 公式解説を参考にしました。 ある時点で選んだコインの総…

SRM 328 Div1 Medium BlockEnemy

問題 都市がいくつかあり、都市間の道の情報とその道を壊すコストが与えられる。任意の都市間で往来ができるように道路が敷かれており、そのパスは必ず1つだけである(要は閉路がない)。敵に征圧された街の番号が与えられるので、道路をいくつか壊して、征…

SRM 325 Div1 Medium TournamentPlan

SRM

問題 グリッド上の町にN人の競技者がいて、i番目の競技者が(street[i], avenue[i])にいる。競技者は道路の交差した位置で出会うと競技を行って勝敗を決める。この競技で総当り戦を行うとき、全競技者の総移動量を最小化せよ。 やりかた どこかの交差点に全員…

SRM 322 Div1 Medium ExtendedDominoes

問題 2x1セルのドミノが複数あり、各セルには0~9の数字が書かれている。ドミノの右側の数字とその隣のドミノの左側の数字が同じになるようにドミノをつなげていき、ドミノがループをなるようにする(最左のドミノの左セルと最右のドミノの右セルの数字がおな…

SRM 320 Div1 Medium ContestSchedule

問題 プログラミングコンテストがいくつか開かれ、それらの開始時間、終了時間、勝率が空白で区切られた1つの文字列"s t p"の形式で与えられる。あるコンテストに出場している間は他のコンテストには出場できない。最適な出場の仕方をした時に、勝てるコン…

SRM 316 Div1 Medium PlacingPieces

問題 直線の棒がいくつか与えられ、それらの長さはpieces[]である。この棒からいくつか選んで長さL上の板の上に、はみ出ないように、かつ区間が互いに重ならないように置いていく。棒を置いていない区間に残りの棒が1つも置けないようになったら終了とする…

SRM 315 Div1 Medium SillySudoku

問題 4x4の数独があり、ところどころは数字で埋められている。この状態での正解パターン数を求めよ。 やりかた 深さ優先探索で通る。1~4の順列を生成して各行を試していき、マスが全部埋まったところで正解かどうか調べればいい。マスが小さいので枝刈りは…

SRM 314 Div1 Medium GrasslandFencer

問題 フェンスが複数あり、それらの長さが与えられる。フェンスを使って三角形をいくつか作るとき、できた三角形の面積の総和を最大化せよ。ただし、複数のフェンスを使って1辺とすることや、1つのフェンスを複数に分割することはできない。 やりかた bitDP…

しょげないでよBaby 眠れば治る