https://codeforces.com/contest/1285/problem/E問題 区間を1つ選んで削除した後に残った重なる区間をunionする。 unionした後に残る区間の数を最大化せよ。解法 全区間をunionした後に残る区間の数は、区間を始点ソートして昇順ループまたは降順ループを回…
https://atcoder.jp/contests/dp A Frog 1 dp[i] = 足場iに着くまでの最小コスト とすると 足場i-1か足場i-2から飛んでくる場合の2通りなので dp[0] = 0 dp[i] = min(dp[i-1] + , dp[i-2] + ) となり。iの昇順にdp[i]を計算する。 B Frog 2 同上 C Vacation …
https://codeforces.com/contest/1110 A. Parity 多倍長偶奇判定 B. Tape テープの長さは全体の長さからテープのない区間の長さを引いたものなのでソートしてb[i]-b[i-1]から貪欲 C. Meaningless Operations gcd(x, 0) = x なので2冪-1 でないならビットを全…
https://beta.atcoder.jp/contests/agc027/tasks/agc027_b まずゴミを捨てる回数mを決めた時の最適な捨て方を考えます。 考えやすいようにm台のロボットを並列に動かして、行きのエネルギー（位置０からそれぞれのロボットが拾う一番遠いゴミまでの移動）を…
応募最終日では1位と同スコア同実行時間で2位でした。・方針ある時間帯に配達する荷物を決めたときの最小コストは明らかに巡回セールスマン問題(TSP)の応用で解ける。それぞれの荷物をどの時間帯に割り当てるかは愚直に探索するとO(4^n)で間に合わないが(時…
http://codeforces.com/contest/545A-Toy Cars塗りつぶすだけB-Equidistant String概要長さnの0,1からなる文字列s,tが与えられる。s,tと編集距離が等しい文字列を出力、存在しないなら"impossible"と出力せよ。解法ある位置のsとtの数字が異なる場合だけ変化…
コンテストページ http://abc017.contest.atcoder.jp/解説 http://www.slideshare.net/chokudai/abc017A - プロコン3つの課題の配点と得点割合が与えられて合計もとめるだけB - choku語choku語は空文字列またはchoku語の末尾に"ch","o","k","u"を連結した文…
コンテストページ http://code-festival-2014-qualb.contest.atcoder.jp/解説 http://www.slideshare.net/chokudai/codefestival2014qual-bCが全然わからず38位。Dの方が明らかに簡単だった。A - あるピアニストmaxとるだけ puts gets.split(' ').map(&:to_i…
解説がどこにあるのかわからないことが少なくないのでno titleTopCoder https://community.topcoder.com/tc?module=Static&d1=match_editorials&d2=archiveCodeforces 問題ページ右の「Tutorial」 CodeChef EditorialsGCJ analysisFHC 「facebook hacker cup…
典型アルゴリズムそのままの問題はここOnline Programming Lesson・エラトステネスの篩アジア地区2002A・連立合同式(ライツアウト系)PCK2006アジア地区2010D 解説夏合宿2008day2J(mod7,ジャッジ未対応)・2点を通る半径rの円国内予選2004D ・円と円の交点国内…
※自分用メモなので人に見せる体裁にはしてないです。あまり確認してないので間違ったこと書いてるかも平衡二分木備考節点に部分木のサイズを持たせるなどすればrank_less_thanやkth_elementなどの追加の機能も可。動的な列を扱うことも可能で要素の挿入削除…
F問題が良問だったので解説記事を書くことにしました。no title解法は F の「ある区間をある文字にできるか」っていう DP はコンテストやってない人でも大学で習う有名 DP だよ（別に知らなくても普通の区間 DP だけど） URL法 2013-07-12 19:51:47 via Hoot…
TCO2013 Round1B250ソートして両端から取るだけ500縦の選び方を決めると横の選び方はgreedyに求まるのでビット全探索 int getMoves(vector <string> board, int R, int C) { int h=board.size(),w=board[0].size(); int ans=INF; vector<int> b(h); rep(i,h){ int m=0; re</int></string>…
元のデータに対して十分小さいサイズでありながら各種操作を高速に処理でき、文字列のみならず2次元データやグラフデータまで表現できるというウェーブレット行列を実装してみた。「高速文字列解析の世界」とかブログとか読んでやっとのことで実装した。ウェ…
ハル研究所プログラミングコンテスト2012の参加記結果は学生部門5位、総合6位でした。工夫したこととか書いていきます。・乱数の種を変えたりして実験したら最適解はトゲを踏んだり待機しないっぽいのでdist[x][y][トゲの周期][アイテム]で探索・最初BFSして…
Beautiful stringsやるだけ void lower(string &s){ REP(i,s.size()){ if('A'<=s[i]&&s[i]<='Z')s[i] += 'a'-'A'; } } int main(){ int m; cin>>m; cin.ignore(); REP(i,m){ string s; getline(cin,s); lower(s); map<char,int> c; map<char,int>::reverse_iterator it; REP(j,s.</char,int></char,int>…
気が向いたら更新していきます。
