オンサイトで未確認

ukuku09の活動記録。

ACM-ICPC 2018 Asia Yokohama Regional Problem E - Eulerian Flight Tour

問題概要 連結とは限らない $n$ 頂点 $m$ 辺のグラフ $G$ が与えられる。$G$ にいくつか辺を付け足して連結なオイラーグラフにしなさい。多重辺・自己ループは許されない。 制約 $3 \le n \le 100$ $0 \le m \le \frac{n(n-1)}{2}$ コンテスト中にした考察 …

UVALive 7724 - Regular Number

思いつけばそれほど難しくないと思う。 問題概要 長さ $N$ の数字列にマッチする正規表現と長さ $5*10^6$ 以下の数字列が与えられる。正規表現にマッチする数字列の部分列を左から順に答えよ。 考察 $N+1$ 個の状態を一列に並べたオートマトンを考える。$i$…

UVALive 6070 - Conquer a New Region

簡単な問題しか解けない。マスコットだからね。 問題概要 頂点数 $N$ の木が与えられる。木の各辺には容量が設定されており、頂点 $u$ から頂点 $v$ へのスコアは $u-v$ パス上の辺の容量の最小値で定義される。 頂点 $w$ を一つ選んで、他の頂点から $w$ へ…

ACPC2018参加記

ククク…、私は大悪魔ウクニキア! 9月19〜21日に実質私主催(大嘘)の競プロ合宿、ACPC2018に参加したわ! 参加してくれた人間ども、遠方からはるばるご苦労だったわね! 作問の話 今年はあんまり参加しなかった。 というか気づいたら問題の枠も埋まってたし、…

JAG夏合宿2018参加記

私は†胡桃沢=ウクニキア=マクドウェル†…。 9月15〜17日に行われたJAG夏合宿に、この私も顔を出してやったわ! 我が忠実なるシモベの頼み事とはいえ聞き入れてやるなんて、私の心はなんて広いのかしら? 合宿前 私の愛すべき後輩であるアズリムが、16日のRAGE…

AOJ 2691: Cost Performance Flow

久々にフローの問題を解いたうくー! ……とは言っても本質であろう「解析的に解く」という考察はbeetくんに聞いたのでまぁはい。 問題概要 https://onlinejudge.u-aizu.ac.jp/#/problems/2691 辺に向きとコストと容量のついたグラフがあります。からへフロー…

RUPC2018参加記

〜♪(あのBGM) ぬぁ〜はっはっは〜!!私は「そういえばガ◯リール・ドロップアウト見たんですけど、赤い子の名前ずっとウクニキアだと思ってました!」ってn回言われる大悪魔ァ…†胡桃沢=ウクニキア=マクドウェル†!! 今年もシモベどもの忠義を確認し彼ら…

ARC093 E - Bichrome Spanning Tree

これ好き。 RUPC2018へ向かう新幹線の中で、うしさん(@ei1333)に確認しながら考えた。 問題 E - Bichrome Spanning Tree 解法 「辺を含む全域木のうち、最小の重みが未満」を満たす辺の本数と、「辺を含む全域木のうち、最小の重みが」を満たす辺の本数を…

† The 2017 ACM-ICPC Asia Tsukuba Regional Contest 参加記 †

くっくっく、なぁーはっはっはぁー!私はいずれ世界を統べる大悪魔、胡桃沢=ウクニキア=マクドウェル!! 12月16〜17日に開催された、ICPCつくば大会2017を掌握してきたわ! ……微妙じゃないし!! フン、確かに†優勝†は逃したけど、当然今回も下等生物どもに…

† The 2017 ACM-ICPC Asia Daejeon Regional Conetst 参戦記 †

Abstract くっくっく、なぁ〜はっはっはっはぁ〜!!!人間どもよ、己が支配者の前にひれ伏しなさい!そう!この私こそが、いずれ世界を掌握する唯一無二にして絶対の王、胡桃沢=ウクニキア=マクドウェルよ! 今宵この私が自ら筆をとったのは他でもない………

† ACM-ICPC 2017 国内予選 参加記 †

前置き 私は大悪魔、胡桃沢=ウクニキア=マクドウェル…。今日は我が力を世界に知らしめるための第一歩として、ICPC2017国内予選に参加してきたわ! ちなみに結果はこんな感じよ!↓ …ふっふっふ、なぁーはっはっはぁー!6完で8位!どう?!これが我がチーム…

AOJ 2370: RabbitWalking

久しぶりにブログを書くわ!自分用メモだけど。 問題概要 RabbitWalking | Aizu Online Judge 解法 まず"-1"の判定ですが、グラフが奇閉路を含まないことと二部グラフであることは必要十分条件なので、与えられたグラフの各連結成分が二部グラフであるかどう…

RUPC2017参加記

前置き Day 0: 移動フェーズ Day 1: 立命館セット Day 1.5: 懇親会 & 準備 Day 2: 会津セット Day 2.5: 懇親会 Day 3: 北大セット 感想 ※お詫び

AtCoder Beginner Contest 007 D: 禁止された数字

問題文 abc007.contest.atcoder.jp 解法 桁DPしてくださいという問題。桁DPがわからない人は pekempey さんの記事がとてつもなくわかりやすいのでそちらを見てください。 pekempey.hatenablog.com

AtCoder Beginner Contest 008 D: 金塊ゲーム

問題文 abc008.contest.atcoder.jp 解法 問題文が無駄に長くてわかりづらいが、よくあるやつだと思った。 ある装置を起動させると、その装置を基準に領域が最大4つ(左上・左下・右上・右下)に分割されるので、そのそれぞれについて再帰的に調べていけば良…

AtCoder Beginner Contest 006 D: トランプ挿入ソート

問題文 abc006.contest.atcoder.jp 解法 抜き取らないトランプに注目すると、それらは増加数列になっているはずなので、最長増加部分列を求めて全体から引いた数が答え。

AtCoder Beginner Contest 010 D: 浮気予防

問題文 abc010.contest.atcoder.jp 解法 サンプルのグラフを見ると「あー最小カット」という気分になるので最小カット。最大流-最小カット定理より、最大流のアルゴリズムそのままで最小カットの問題も解ける。

AtCoder Beginner Contest 038 D: プレゼント

問題文 abc038.contest.atcoder.jp 解法 dp[i] := i 番目の箱を最も外側に使う時の最大の入れ子の数 でDPする。しかし、普通にやると、その箱に入る箱を探すのを含めて $O(N^2)$ になってしまう。 DPの遷移は、dp[i] = max{dp[j] | wj < wi かつ hj < hi}+1 …

AtCoder Beginner Contest 004 D: マーブル

問題文 abc004.contest.atcoder.jp 解法 箱の番号とマーブルの残り個数を状態として適当な位置からDPする。 各色を独立に考えようとすると、状態数が 2000 * 300 * 300 * 300 になってしまう。しかし、無駄な移動をしないなら、すべてのマーブルの移動後は赤…

AOJ 0293: Algorithm Exam

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?lang=jp&id=0293 解法 割り当てとか言われたらフローを流したくなるわけだけど、やっぱり最小費用流。 会場の使い方は最悪でも 2^5 通りなので、全部試す。 次に考えるべきは、バスの距離 $D$…

AOJ 0274: Arts and Crafts

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?lang=jp&id=0274 解法 bitDP + 最小費用流。 むかし見たときは全然わからなかったけど、昨日やったら解けたのでわーい!すっごーい!(は? まず bitDP パートから。問題文に、 それぞれの課…

AtCoder Beginner Contest 003 D: AtCoder社の冬

問題文 abc003.contest.atcoder.jp 解法 いきなり X*Y の区画の上下左右すべてに、デスクまたはサーバーラックが接した配置の場合の数を数えるのは難しいので、とりあえず D 個のデスクと L 個のサーバーラックを自由に配置する場合の数を考える。これは X*Y…

AtCoder Beginner Contest 041 D: 徒競走

問題文 abc041.contest.atcoder.jp 解法 制約を見ると解法が察せる部類の問題。bitDPでやった。 各うさぎごとに、自分よりも先にゴールするうさぎのリストを持っておき、すでにゴールしたうさぎのリストと比較しながら、ゴールできるならゴールさせていく。…

AtCoder Beginner Contest 042 D: いろはちゃんとマス目

引き続きABC埋め。 問題文 abc042.contest.atcoder.jp 解法 お絵描きするとわかる。 左上を $(0, 0)$、右下を $(H-1, W-1)$ とする。障害物がなければ、グリッド内を左上から右下へ、右移動・下移動のみで移動する経路数は、全移動(H-1+W-1 回)のなかのど…

AtCoder Beginner Contest 040 D: 道路の老朽化対策について

一昨日のABC埋め。 問題文 abc040.contest.atcoder.jp 解法 $y_i$ の降順に全域木を作っていくと、i 本目の道路を使う直前の状態というのは、 $y_i$ 年以前の道路を含まない部分グラフとなっている。結局、初めて $w_j$ 以下となる $y_i$ の道路を使う直前の…

AtCoder Beginner Contest 034 D: 食塩水

ABC埋め続き。 問題文 abc034.contest.atcoder.jp 解法 貪欲に混ぜるとダメ。 水:食塩の比率が同じ2つの食塩があるときは、水が少ないほうを優先的に入れたほうが、全体の濃度を薄める効果が小さい(=最終的な濃度を大きくできる)。みたいに考えていると…

AtCoder Beginner Contest 023 D: 射撃王

ABC埋め。 問題文 abc023.contest.atcoder.jp 解法 制約的に $O(NlogN)$ くらいかなぁってなるので、二分探索をする。 風船のペナルティの最大値を x とすると、各風船がそこに到達するまでの時間は、 $$T_i = (x - H_i) / S_i$$ で求められる。あとは、この…

AtCoder Beginner Contest 051 D: Candidates of No Shortest Paths

ABC埋め中。 問題文 abc051.contest.atcoder.jp 解法 Warshall-Floyd で全頂点間の最短経路を求めて、与えられたエッジの端点間の最短経路重みがエッジの重みより小さくなっているかどうかを判定するだけで、そのエッジがグラフ上のいずれかの最短経路上に含…

AtCoder Beginner Contest 054 D: Mixing Experiment

2月なのでABC埋め。記事は自分用なのであんまりタメにならなそう。 問題文 abc054.contest.atcoder.jp 解法 制約がそんなに大きくないので01ナップザックっぽく解いた。 dp[i][j][k]:=薬品 i-1 まででタイプAが j グラム、タイプBが k グラムの溶液を作る最…

ごどく部活動記録【海外遠征編】ACM-ICPC 2016 バンコク大会 参加記

初海外!初海外ですよ!!(ひきこもり並感 ということで、ごどく部の遠征も兼ねて、ICPCバンコク大会に参加してきました。 「バンコクの黒板w」 「なんかそれすごく惜しい感じがする」 「はい。」 www.acm-icpc.eng.chula.ac.th