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


SRM

SRM 417 Div1 Medium CubeNets

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

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 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[]で与えられる。これらを車座に配置した時に隣り合う身長差の最大値が最小化するような配置パターンを求めよ。複数あるときには身長差順で辞書式最小なものを返せ。 やりかた 単純に身長差順で配置すると最後の…

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