2018-07-25から1日間の記事一覧

JOI'09 本選3問目 あみだくじ

問題概要 あみだくじの横棒を一本消して,左本がゴールで獲得する点数の総和を最小化せよ. 解法 注意:本来この解法はTLEするように制約は設定されているはずですが,出題された2009年と比較して計算速度が向上してるため現在のジャッジでは120ms程度でACし…

JOI'09 本選5問目 認証レベル

問題概要 事務所の入り口から,持ってる身分証のレベル以下の部屋にだけ入れる. 2つの事務所それぞれに入って合計部屋以上巡ることができるように身分証を2つ渡すとき,レベルの和の最小値はいくつか. 解法 1つの身分証で2つの事務所とも回れると誤読した…

JOI'07本選 5問目 最軽量のモビール

問題概要 モビールが釣り合うようにおもりを設定するとき,重さの合計の最小値を求めなさい. 解法 モビールの根を探し,再帰的に計算していく. 左右ともに錘のとき が最小 左右ともにモビールのとき 左のモビールの最小を,右のモビールの最小をと置くと,…

JOI'08春2-1 Nile.com

JOI難易度6 問題概要 日間,個の店から1つ選んで商品を買う.2日連続だと1割引,3日以上連続だと3割引になる. 出費の最小値を求めよ. 解法 DP. とするとよい.連続しない場合の遷移がかかってしまうので前計算して高速化.MLE対策に日数をにすると通る. …

SRM610 Div1 Easy TheMatrix

問題概要 盤面上の市松模様の面積の最大値 解法 横向きに累積和を取って縦の範囲決めて 制約読み違えてて辛かった. ソースコード #include<bits/stdc++.h> using namespace std; #define ll long long #define FOR(i,n,m) for(int i=(n);i<(m);i++) #define REP(i,n) FOR(i</bits/stdc++.h>…

SRM609 Div1 Easy MagicalStringDiv1

問題概要 >と<からなる文字列の部分列のうち個の>の後に個の<が来るようなものうち最大の長さ 解法 境界を決めて左の>の個数と右の<の個数のうち小さい方を二倍したものを更新していく. ソースコード #include<bits/stdc++.h> using namespace std; #define ll long long #</bits/stdc++.h>…