読者です 読者をやめる 読者になる 読者になる

(o_o)

ブログ。

再帰を使わない Segment Tree

蟻本には再帰で書かれた Segment Tree が載っているが,うまく書けば再帰を使わず書くこともできる.再帰あり gist9219b197f2a177931e54627003b51c6f再帰なし gistfe04fcefcc5581d60da6150a621d549e それぞれの方法で長さ 200000 でランダムな 1000000 クエ…

KUPC2015 K SOULBLOCK

問題: K: SOULBLOCK - 京都大学プログラミングコンテスト2015 | AtCoder

AOJ2705 くるくるドア

特に考察は必要なく,そこそこライブラリを貼って実装するだけで解ける.http://mars.kmc.gr.jp/~asi1024/kurukuru_door/

ICPC WF 2017 の大学選抜について

運営が翌年のWFの選抜方法を明らかにしたみたい.たぶんこんな感じ・([順位] - 1) / [大会に割り当てられているスコア] が小さい順にKチーム選ぶ例えば,Asia PP subregion の今年のスコア (Daejeon:1.9, Hanoi:1.3, Jakarta:1.3, Phuket:0.9, Singapore:1, …

ICPC WF 2016 に選抜された

台湾大会でスロットを取れたみたい.やったぜ.

AOJ2154 海岸線の浸食

線分アレンジメントして列挙するだけ. O(N^4 * T) (Tはテストケース数) だが,幾何なので間に合う. ジャッジケースをビジュアライザに入れた結果はこんな感じ http://mars.kmc.gr.jp/~asi1024/shore_erosion/

AOJ2258 全自動円形掃除機™

全自動円形掃除機™ をACしたのはもう1年近く前だけど,いまさら解説記事を書きます. いろんな実装方法はあるけど,自分の実装はこんな感じ.多角形の各線分からR内側に平行移動した線分を列挙する 各頂点からの半径 R の円周を列挙する これらの線分や円周…

AOJ2450 Do use segment tree

LCAと遅延伝播SegmentTreeと重軽分解のライブラリを貼った

AOJ2352 Divisor

異なる a, b について,a が b の倍数になるときに a から b に辺を張るような N 頂点のグラフを考える.このグラフは推移的グラフであるので,最大独立集合 = 最小パス被覆 である (Dilworth の定理).DAG の最小パス被覆は二部グラフの最大マッチングで解…

AOJ2674 異常検知

[l, r) 区間に a_l ... a_r-1 のソート列を持つ Segment Tree を持つ. 各クエリについて O(logN) 回二分探索をすればいい.O(Q log^2 N) くらい.

KUPC2015

原案に関わったやつだけ

AOJ ALDS1_13-C 15 Puzzle

A*の問題,他にないのかね

AOJ1164 Tighten Up!

問題概要 略解法 DPっぽいやりかたで解いた.計算量が危うい気がしたけど何故か通った.幾何やからな

AOJ2588 Golf

問題概要 略解法 N字以内で書けるものをvectorでもってDPする.のだが,10までやるとTLEする(MLEもしてそう).ここで,N

AOJ2647 The Capital

なんかよく理解しないまま解けてしまった

AOJ2574 Magical Switches

問題概要 3行3N+1列のマップがあり,同じアルファベットについて,大文字と小文字の一方は全て壁であり,もう一方は通れる床である.左から右まで通れるようにしたいとき,壁にする大文字を全て出力せよ.解が複数あればどれか1つを出力せよ.解がない場合は…

AOJ2603 TiMe Table

問題概要 略解法 O(N^3)のDPは容易に思いつく. 実はmonge性を満たすため,monge-dp にできる. https://gist.github.com/asi1024/5751b073d3f422206e5a/revisions な感じで高速化.

AOJ1353 Sweet War

問題概要 1つのチョコボールのスタックを使って2人ゲームを行う. それぞれのチョコボールに栄養価r_iと美味しさs_iが定められており, 2人は食べたチョコボールの美味しさを最大化したいと考えている.2人にはそれぞれ体力値が定められており,それぞれ初期…

AOJ2539 Counting 1's

問題概要 略解法 とにかく入力ケース数が多い.呑気に二分探索なんてしてたらTLEする・・・ k_1 を見ると B-A が3通りに絞れる.B-A が決まれば,k_n から順に見ていけば,(A,B) の組み合わせは高々1通りに絞れることがわかる.

AOJ2455 Sun and Moon

問題概要 sum_i (P_i * x^O_i) = 0 かつ sum_i (P_i * O_i * x^(O_i - 1) = 0 となるような最小の正整数 x を求めよ解法 最小次数の係数の約数が解の候補となるので,それで全部試す.O(√(NP)) だけど,AOJ鯖は速いので間に合う. これって f(x) = f'(x) = 0…

AOJ2557 Iyasugigappa

問題概要 カエルとカッパとイタチがカードゲームをしているこのゲームでは,ギロチンカード1枚,貴族カード12枚,アクションカード6枚を使う.貴族カードとアクションカードの表には,それぞれ整数値が書かれている.まず,ゲームを始める前に,プレイヤーは…

AOJ2617 Air Pollution

問題概要 略解法 循環操作は全体の和を変えないみたいなので,なんとなく累積和をとってみる. すると,循環操作は値のswapに相当することがわかる.後はノリで解ける.

AOJ2290 Attack the Moles

問題概要 問題文から明らかな最小費用流を感じる何か解法 右手が左手より右側になければならない,という条件は無視できる. 最小費用流で解くにしても,如何せんグラフのサイズが大きい. きっちり辺を張ると辺の数は O(N^2) くらいになってしまう. ここで…

AOJ2393 Dungeon Creation

問題概要 2次元マップが与えられる.マスとマスの間にいい感じに壁を配置することで平路がないようにしたい.早い話が特徴的なグラフが与えられるからその全域木を作りたいということ.作り方は何通りあるか.解法 行列木定理を使って求めようにも,ナイーブ…

AOJ1293 Common Polynomial

無事院試にも受かって生活に余裕が出てきたので,そろそろAOJ-ICPCでも埋めていくことにした. 今日から毎日1問ずつ解いた問題をブログに書いていこうと思う.単純に計算すると夏休みのうちに40問くらい解くことになりそう. まずは今日は簡単な問題から.問…

AOJ2404 ドッグフード

結構実装が大変と言われているこの問題。想定解法は指数オーダーの探索だが、これにも割と良さげな解法がある。例えばこういうケースを例に考えてみる。ロープの上側がロープが結ばれている杭、左下側がスタート地点、右下の緑色の点がゴール地点である。 ST…

AOJ1177 番犬派遣会社

高難度の場合分けゲーとして名高いこの問題だが、最近割と良さげな解法を思いついたので実装してみた。STEP 1 原点から引数で与えられる点Pまでの建物の内部を通らない最短の道のりを求めるような関数を作る 原点とその点を結ぶ線分が建物の内部を通らないと…

ICPCアジア地区大会

東京大会は17位でした. 台湾大会は14位でした.

ICPC2014 国内予選

全体で5位,大学別順位で4位でした.

そろそろそろ

最近はすっかり競技プログラミングをやらなくなってしまい,レートも大学入学時から伸びてないので,ちょっとは練習しようかなあと思う.大学の単位も揃えて時間に余裕ができたし.

KUPC2014予定

KUPC2014は7/5に開催します. ウッヒョオオオオオオオオォォォォ

KUPC2013

Cの原案とEとHを担当していました. C 基本的に左上の頂点と右上の頂点が0flip,左辺と上辺と右辺が1flip,その他が2flipで,各行につき好きなマスをさらに+1flipできる.O(NM). #include <iostream> #include <vector> #include <algorithm> using namespace std; int a[128][128]; int </algorithm></vector></iostream>…

KUPC2013予定

KUPC2013は7/6に開催します.京都大学プログラミングコンテスト(KUPC)は,アルゴリズムの問題を決められた時間内に解く能力を競うコンテストです. 問題は入門者向けの易しいものから上級者向けの難しいものまで幅広く用意される予定です.京都大学の関係者…

AtCoder#13

writerやってました. いままで原案だけ投げつけて問題文とかテストケースとか全部AtCoderの中の人に任せてきたけど,今回の反省を踏まえてテストケースも問題文も自分で作ろうと思った.A. 過去のA問題のなかで最も難しい.6通りの置き方について詰められる…

ARC#008 問題C

「問題Cの解説をもっと詳しく書いてほしい」という要望が多かったので、詳しめに書きます。問題文: http://arc008.contest.atcoder.jp/tasks/arc008_3STEP 1 まず、それぞれの参加者について、自分が食べるたこ焼きが投げられてからそれを受け取るまでにか…

ARC#008

今回のAtCoderのwriterやってました。A まず10個ずつ纏めて全部パックで買う。そして、残りのたこ焼きを1パックで買った場合とバラで買った場合でかかる費用の小さい方を選ぶ。たこ焼きn個のときの最小費用は、100[n/10]+min{15(n%10),100}円となる。C言語 #…

AtCoder #007 のtesterやってました

テスターやってました。この時間帯はバイトだから参加できないのよね。 Dのテストケースをつくるときのわくわく感がやばかった。実際のテストケースファイルを作ったのはほとんどちょくだいさんだったけど。 A 前から順にやるだけ。resを用意せず順次出力し…

ARC004のwriterやってました

「Cは long long と見せかけて実はそれでもオーバーフローするから多倍長を使いました。」と言われた。 でもwriter解では多倍長を使ってない。 Problem C. #include <iostream> #include <cstdio> #include <algorithm> #include <cstdlib> #include <cmath> #include <vector> #include <string> using namespace std; typ</string></vector></cmath></cstdlib></algorithm></cstdio></iostream>…