問題概要 ノード数V( 解法 まずWFしておく。その後はビットDP。 dp[v][bit] = {これまでに尋ねたノードがbitで今いるのがvであるような最小の時刻} を全部計算して最後にdp[goal][bit]

問題概要 s!をK進数で書いたとき末尾に0がいくつあるか求める問題。s 解法 Kを素因数分解してその素因数がs!にいくつ含まれるか求める。例えばK=8のときなんかは2でs!がいくつ割りきれるか求め、それを3で割ったものが0の個数になる。K=24とかだったらそれと…

結果。 uwiさんとshindanninさんでチーム参加して6位。自分は比較的易しめな問題を3問通したけど、ちょっとWAが多いのと、最後に難しめの問題を通せなかったのが反省点。

問題概要 2次元グリッドの格子点上に点がいくつかある。4点選んで軸に平行な長方形をつくり、内部に点がないようにしたい。面積の最大値を求める問題。 解法 長方形の2点の選び方を全探索する。内部に点があるかどうかは累積和を計算しておけばO(1)で判定で…

問題概要 重み付き無向グラフで2点間の最短路を求める。ただし最短路は4か7の倍数でなければならない。 解法 (ノード、今の時刻%28)を組にしてDijkstraする。

問題概要 重みなし区間スケジューリング問題を解く。ただし2個までは重複を許す。 解法 重み有り重複なしだとDPで重み有り重複有りだと最小費用流、重みなし重複なしだとGreedy、ここまでは知っていたけど重みなし重複ありは意外と知らなかった。制約見たらG…

問題概要 長さN(区間[a,b]にある1の個数はcである、というものである。条件を満たすような列のうち、[1,N]にある1の個数の最小値と最大値を求める問題。全ての制約を満たす列が少なくともひとつ存在することが保証されている。 解法 累積和+差分制約というよ…

問題概要 ノード数N( 解法 JAGの冬コンテストでも同じような問題が出ていた。貪欲にやってよい。分離云々のところはちょっと工夫したunion-findでKruskal風に行ける。

結果。 テスターやってました。開催までにジャッジ解と入力生成器を2撃墜できたので役目は果たせたと思います。 OUPCは初期はアジア地区予選想定ではなかったので簡単な問題しか入れていませんでした。アジア地区予選想定ということになってから難化させる必…

問題概要 整数K( 解法 Kの約数の個数をdとおく。d*Nは大きいのでTLEする。ところで、Kの約数がX[i]で割りきれるかどうかはgcd(K,X[i])で割りきれるかどうかと同じなので、各X[i]はgcd(K,X[i])で置き換えてよい。gcd(K,X[i])はKの約数なのでgcd(K,X[i])の個数…

結果。 4/4完で8位。これだけみれば悪くないけど参加者が正味何人いたのやら。全く同じ問題が出題されていたらしいけど、それを除けば悪い問題ではなかった。 ただ、システムは不満だらけでTLEの設定やら言語補正やらが分かりにくく、部分点制度を採用してる…

問題概要 2次元迷路がある。スタート->中間地点->ゴールの最短路を求める問題。 解法 BFS。

問題概要 長さ50以下の文字列が50個以下ある。適当に並び替えて、先頭から2個以上選んで連結して作れる文字列のうち辞書順最小のものを求める問題。 解法 小さいので全探索。とはいえもちろん3つ以上つなげる意味は無いので2個だけ選ぶようにする。

問題概要 ふたつの日付の間隔を求める問題。 解法 一日ずつincするのが間に合うので愚直にやる。

結果。 こういう形で開催されるコンテストが増えてきているのはとても良いことだと思います。問題は典型的なものが多かったです。

結果。 尊敬する競技コーダーであるところのtomerunさんとuwiさんのチームに混ぜてもらって参戦。残念ながらあまりチームに貢献することはできなかったけど、とても楽しい経験をさせてもらった。やっぱりチーム戦は楽しいのでこれからも増えてほしいところ。…

難易度見積りを完全に読み間違えてご迷惑をおかけしました。問題はAizu Online Judgeの2350~2361に収録されているので解いてもらえると嬉しいです。 ジャッジデータはここでダウンロードできます。不備が見つかった場合は指摘していただけると助かります。 …

日程は未確定(おそらく3月18日)ですが3月18日に、大阪大学プログラミングコンテスト(OUPC)を開催します。 気軽にご参加下さい。 日時 (おそらく)2012年3月18日(日) 13:00 - 18:00 ジャッジ Aizu Online Judge 時間 5時間 問題数 12問程度 問題文 日本語問題…

問題概要 辞書が与えられる。辞書内の文字のうち、辞書内のふたつの言葉が連結されてできたものを全て出力する問題。 解法 文字列の長さが短いので、どこで区切るかを各文字について全探索する。

問題概要 Fibonacci数を出力する。 解法 多倍長使うだけ。コード略。

問題概要 C個の授業がそれぞれT箇所で開催されている。授業の疲労度と教室移動の疲労度が定義されているので、疲労度を最小化する問題。 解法 普通に状態を考えて普通にDPする。

問題概要 ノード数N( 解法 二分探索+二部グラフチェックする。

問題概要 ノード数N( 解法 まず星グラフを考える。その後辺数が余っていたら頂点を一つ選んで既にあるクリークにその頂点を含むクリークになるように辺を追加する。First Acceptだったっぽい。

問題概要 山が3つあって、それぞれの山には石がx, y, z個置いてある。先手と後手の人が交互に以下のいずれかの処理をする。 xの石をひとつyの山に移す。 yの石をひとつzの山に移す。 zの石をひとつ取り除く。 xの石をひとつyの山に移し、zの石をひとつ取り除…

問題概要 ノード数N( 解法 まず、適当な点を根にしてLCAを持ち、オイラーツアーを計算しておく。また、始めて訪ねたタイミングと出て行くときのタイミングを記録しておく。このとき、10種類のBITを用いて入るときに+1、出ていくときに-1を加えるようにすると…

結果。 5/9完で8位。多くの人に解かれていた数学ゲー2問が解けていれば…。

問題概要 2^62以下の整数を素因数分解する。 解法 ポラードローした。

問題概要 カードを交互に引いて和が31をこえるかどうかで勝負したときどちらが勝つか判定する。 解法 典型的なゲーム木探索。

問題概要 文字列をあるルールで置換した後回文になっているかどうか判定する問題。

問題概要 平面上にN( 解法 ICPCの国内予選に似た問題が出てた気がする。幾何の定石に従って2点が円上に動くまで動かす。