Comb Viewer v1.0 リリース

制作した背景

去年の文化祭にも出した，3DCG 画像展示用のソフト Comb Viewer を今年も出そうということになったが，ソースコードを紛失したため作ることになった．また，去年のものがバグがいろいろあり，書き直した方が早いと思ったのも制作することになった理由の１つ．

実装したこと

• 作品の表示
• 作品のタイトル・作者の表示
• 作品の拡大・縮小・視点移動機能
• スライドショー機能
• その他諸々

これからやること

• アイコンを変える（RIAN DIGITAL 氏から画像が届き次第）
• 終了時の確認メッセージ

ダウンロードはここから

github.com

AtCoder Regular Contest 035：C - アットコーダー王国の交通事情

問題

C - アットコーダー王国の交通事情

全ての頂点が連結であるグラフがあり，この全頂点間の最短距離の和を S とする．「頂点 X と Y の間にコスト Z の辺を追加」というクエリが K 回与えられるので，K 回それぞれに対して S を求める問題．

解法

全頂点間について，コストが小さくなった辺を通るときの距離でそれぞれの頂点間の距離の min を取る．その後，S を求めればよい．O((N^3) + (K*(N^2)))．

解答

S を min を取るときに同時に求めていてバグらせた．

Submission #3168023 - AtCoder Regular Contest 035

gist.github.com

AtCoder Regular Contest 032：C - 仕事計画

問題

C - 仕事計画

a_i と b_i を始点・終点とする区間が N 個あり，それらからいくつか両端以外で重ならないように選ぶとき，最大でいくつ選べるかを求め，辞書順最小の組み合わせを求める問題．

解法

区間をソートし，時間を後ろから見ていく．今見ている時間から始まる区間は std::lower_bound, std::upper_bound() で求まるので，それらの終点から選べる区間の数の max を取る．このとき，区間の index が出来るだけ小さくなるように max を取る．あとは，今見ている時間から始まる区間を取らない場合は，今見ている時間 + 1 の結果を用いればよい．この２つで最適な方を今見ている時間の結果にすればよい．最後に，これらの結果を用いて，最初から区間を選ぶ経路を復元すればよい．O(MlogN + N)．

解答

Submission #3167751 - AtCoder Regular Contest 032

gist.github.com