応募最終日では1位と同スコア同実行時間で2位でした。 ・方針 ある時間帯に配達する荷物を決めたときの最小コストは明らかに巡回セールスマン問題(TSP)の応用で解ける。 それぞれの荷物をどの時間帯に割り当てるかは愚直に探索するとO(4^n)で間に合わないが(…

http://codeforces.com/contest/545 A-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/abc017 A - プロコン 3つの課題の配点と得点割合が与えられて合計もとめるだけ B - choku語 choku語は空文字列またはchoku語の末尾に"ch","o","k","u"を連結し…

コンテストページ http://code-festival-2014-qualb.contest.atcoder.jp/ 解説 http://www.slideshare.net/chokudai/codefestival2014qual-b Cが全然わからず38位。Dの方が明らかに簡単だった。 A - あるピアニスト maxとるだけ puts gets.split(' ').map(&:…

解説がどこにあるのかわからないことが少なくないので 過去のコンテストの解説 - 秋田大学ICPC対策室@wiki - アットウィキ TopCoder https://community.topcoder.com/tc?module=Static&d1=match_editorials&d2=archive Codeforces 問題ページ右の「Tutorial…

典型アルゴリズムそのままの問題はここOnline Programming Lesson ・エラトステネスの篩 アジア地区2002A ・連立合同式(ライツアウト系) PCK2006 アジア地区2010D 解説 夏合宿2008day2J(mod7,ジャッジ未対応) ・2点を通る半径rの円 国内予選2004D ・円と円の…

※自分用メモなので人に見せる体裁にはしてないです。あまり確認してないので間違ったこと書いてるかも 平衡二分木 備考 節点に部分木のサイズを持たせるなどすればrank_less_thanやkth_elementなどの追加の機能も可。 動的な列を扱うことも可能で要素の挿入…

F問題が良問だったので解説記事を書くことにしました。 The 2013 ACM-ICPC Asia Aizu Regional Contest :: Domestic contest problem set 解法は window.twttr = (function(d, s, id) { var js, fjs = d.getElementsByTagName(s)[0], t = window.twttr || {}…

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;</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>…

気が向いたら更新していきます。