TCO15 Round 1Aに参加しました。 結果はmedだけ通ってまぁそこそこといった感じです。レーティングhighest更新出来たので嬉しいです。できれば黄色まで伸びてほしいなぁ…問題:TopCoder Statistics - Problem Statement解法:まず前提知識として,グラフの遷移…

汚いコード。問題:TopCoder Statistics - Problem Statement解法:dp[keta][x1][x2][x3][x4][x5]=(keta目で1つ目の質問に対する答え(つまり9で割ったあまり)がx1で,2つ目の質問に対する答えがx2で… であるような場合の数)とする。 すると,非常に汚い漸化式が…

データ構造の良い練習。問題:C: 山登り(Mountain Climbing) - KyurideKagamizProgrammingContest(Remixed by ryunosuKe & Kensuke) | AtCoder解法:各頂点ごとに,その頂点がグラフの葉であるなら山の頂点(頂点0)までの距離を格納しておき,セグメント木を使っ…

最近流行りの最小カット…じゃなくて,最小費用流でした。問題:TopCoder Statistics - Problem Statement解法:写真を参考に。 以下ソースコード class minimumCostFlow { public: minimumCostFlow(int V) : V(V) { G.resize(V); h.resize(V); dist.resize(V); …

これは簡単。問題:TopCoder Statistics - Problem Statement解法:t分後にバスが来る確率を動的計画法で求める。s分前にバスが来た場合はまだジョセフさんが待つ時間が確定していないので動的計画法を続ける必要があるが,s分以降バスが来てからはジョセフさん…

SRM655に参加しました。自信なさげにeasyを提出して見事に撃墜され,多少レートが落ちました。 easyは典型問題らしいですね。問題:TopCoder Statistics - Problem Statement 解法:元の状態からどうやって目的のボードを作るか考えるのではなく,目的のボードか…

やっとわかった…多分3日くらい考えてた。問題:N人がK回戦のトーナメントをする。1回の試合は2人以上なら何人参加しても良いが,勝者は1人のみである。K回勝ち抜く人は何人いても良い。このようなトーナメントの作り方は何通りあるか。解法:状態として,「i回戦…

動的計画法で解きたかった。問題:TopCoder Statistics - Problem Statement解法:動的計画法を使う。dp[l][r][k]を, k=0:区間[l,r)の上半分をHにするのに必要な最小回数 k=1:区間[l,r)の下半分をHにするのに必要な最小回数 k=2:区間[l,r)の全体をHにするのに…

yukicoderに途中まで参加していました。2問目に日本語の問題で引っかかって1問目と3問目の2完でした。問題:No.181 A↑↑N mod M - yukicoder解法:Mの値が小さいのでなんとなくMの周期について考えられそうな気がします。ただし正直にa^NをMで割ったあまりをそ…

だらだら日々を過ごしても仕方ないと思ったので一応目標決めておきます。月単位で目標作ったことないのでちょっとピント外れてるかも… 競プロ ・そこそこ難しい問題(div1easyくらい)を合計10問くらい ・結構難しい問題(div2hard,div1medくらい)を合計10問く…

学校始まってだんだん解けなくなってきてますね…とりあえず1日2問目標にします。問題:D: 偶数メートル - AtCoder Regular Contest 036 | AtCoder解法:各頂点1つごとに2つずつ頂点を用意し,それぞれ赤色と青色とする。で,頂点aと頂点bの間に道を作る時, ・道…

解けなかったの悔しい。問題:C: 偶然ジェネレータ - AtCoder Regular Contest 036 | AtCoder解法:dp[pos][diff0][diff1]=(posの文字を見ている時点で(0の数-1の数)の最大値がdiff0,(1の数-0の数)の最大値がdiff1であるような場合の数)とすると,次の数が0か1…

星3つはありそう。問題:No.176 2種類の切手 - yukicoder解法:uwiさんのコードを参考にさせていただきました。 Bが1000より大きい時は,T/Bは10^6以下に抑えられるので,p*A+q*Bのqの値を全探索して最適な値を調べれば良い。 Bが1000より小さい時に同じやり方で…

あっ！この問題,進研ゼミで見たことある！問題:No.177 制作進行の宮森あおいです！ - yukicoder解法:最近(自分の中で)流行りの最大フロー問題。 以下ソースコード const int dx[] = {1, 0, -1, 0}; const int dy[] = {0, 1, 0, -1}; using namespace std; ty…

最小カットの練習その2。問題:Dashboard - World Finals 2008 - Google Code Jam解法:最小カットを使って「燃やす埋める問題」を解くの54ページあたりから。引っかかったので一応実装について注意すると,'?'と'?'を結ぶ辺は1回しか結んではいけない。 一応ソ…

最小カットの練習がしたくなったので。問題:TopCoder Statistics - Problem Statement解法:最小カットを使って「燃やす埋める問題」を解くの40ページあたりから。 // max_flow const int MAX_V = 3000; const int INF = 1e6; class FordFulkerson { public: …

典型っぽい(解けるとは言っていない)。問題:木のグラフが与えられる。グラフの頂点のいくつかには数字が書いてあって,以下の条件を満たすように木を辺の切断によってグループ分けしたい。 ・数字の書いてある頂点が同じグループになってはいけない。 ・各グ…

お好み焼き食べたい・・・問題:お好み焼きをM人の友達で食べる。お好み焼きにはサイズという整数値があって,M人の間でサイズの差がK以下になるようにお好み焼きを選びたい。このような選び方は何通りあるか。解法:まずソートする。そして,それぞれの整数iに…

先ほどの記事(SRM 653 div1 med:Singing - mayoko’s diary)で ① ・頂点がたくさんある。それを赤と青に塗り分ける。全部の頂点を必ず赤か青に塗らなくてはいけない ・必ず赤色に塗らなくてはいけない頂点(Sとする)と青色に塗らなくてはいけない頂点(Tとする)…

答えみて書いただけでまだあんまり納得できてない・・・問題:TopCoder Statistics - Problem Statement解法:yosupoさんのページを参考にしました。最小カットについて - よすぽの日記 このページでは, ・頂点がたくさんある。それを赤と青に塗り分ける。全部…

途中までは思いついたけど,そこまでだった。問題:TopCoder Statistics - Problem Statement解法:まず1次元の場合で問題にあるような対称移動をすることを考える。点xにいるときにAiに対して対称移動してからAjに対して対称移動した時の座標は となる。すなわ…

たまによく見る。問題:E: Line up! - Indeedなう（オープンコンテストB） | AtCoder解法:目的の形にするためにはとにかく小さい数から順に左に詰めていかなければならない。それをBITとか使ってシミュレーションすれば良いだけ。 以下ソースコード const int…

本番何もわからずに通したけど,しっかりプリム法書いてて面白かった。問題:D: Game on a Grid - Indeedなう（オープンコンテストB） | AtCoder解法:すべてのマスが非負なので,点数を最大化するならとりあえずすべてのマスを通るのが良い。これで盤面に書いて…

回文判定はなんか浮いたことしちゃったのかも。問題:C: Palindrome Concatenation - Indeedなう（オープンコンテストB） | AtCoder解法:dp[n]=(n文字目までの最小コスト)とすると,dp[n]=min(dp[k]+(n-k文字の回文のコスト))という感じになる。これを高速で実…