ACM-ICPC 2018 国内予選 参加記

はじめに 7/6 に行われた ACM-ICPC 2018 国内予選の参加記です. 忘れないうちに書こうと思います. 今年は大雨で関西勢は大変でしたね.自分の大学もリモート参加推奨,という形になってしまいかなりバタバタしていました. 結果 チーム Zerokan_Sunshine …

AOJ 2702 Alternate Escape

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2702 解法 後退解析で解く. ゲームの探索なので,最初は始点からDFSしたくなるかもしれないが,普通に状態が自分に戻ってくるような遷移があるので困る. こういうときは確定しているとこ…

AOJ 0324 Downhill Race

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0324 解法 ダイクストラで解く. 与えられるグラフはDAGになっていて,この上で2回違う条件で最短経路を求めたい.しかし依存関係にあるので独立にはできない. こういうときは1回目と2回…

AOJ 0322 Slates

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0322 解法 二分探索で解ける. 左が欠けているやつを考えるときは末尾から比べたいので,各文字を反転した文字列集合も別に持っておく. 与えられた石版に ? がある場合は26文字全通り試す…

AOJ 0321 Investigation of Club Activities

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0321 解法 union find 木を使うと楽? union find の各集合がどのクラブに属するかを別に vector で持っておく. a と b が同じ部活に所属している場合,マージするのだが違うクラブに属し…

AOJ 2693 JAG-channel II

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2693 解法 いかにもな bitDP 感がある. しかしそれでもなんらかの形で順番は保持しないとどうしようもなさそうに見える. うまくやれば状態に順列持てたりしないかな~と制約を読むと N -…

Codeforces Round #491 (Div.2) F. Concise and clear

問題文 http://codeforces.com/contest/991/problem/F 解法 冪乗の形を使っていかに短くできるか,という問題. まず,n * m (n, m はただの自然数)のような表現は完全に不利. 例えば 99 * 99 を考えてみるとわかりやすいが,そのまま出力したほうが短い…

AOJ 2390 AYBABTU

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2390 解法 感覚的には最大全域木的なことを基地が繋がりすぎないようにやると通りそう. そして投げたら通った(終了)…だと困るので厳密じゃないけど一応それっぽいのだけ.木なので基地…

AOJ 1342 Don't Burst the Balloon

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1342 解法 3次元幾何に見せかけた2次元幾何. 球の半径Rを決めた時,上から見て中心をどこにおけるかをイメージする. すると針と球の条件は,ある円があってその外側に中心を置く,という…

AOJ 2558 Medical Inspection

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2558 解法 最小点被覆は多項式時間で解けない. この時点で,グラフにある良い性質を用いるか,頑張って枝刈りしかない. しかし与えられたグラフは単純グラフであるだけで他にいい感じの…

AOJ 2541 Magical Bridges

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2541 解法 特別な辺のコストを定めた時,それぞれの最短経路長がすぐに求まってくれないと困る. そこで特別な辺は100個しか無いことを利用し,とりあえず以下のダイクストラをやる.d[i][…

AOJ 2434 Audition

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2434 解法 他のそれぞれのアイドルの得点の期待値は,3種類の要素の得点の確率変数をX, Y, Z とすると E[X + Y + Z] だが,これは期待値の線形性から E[X] + E[Y] + E[Z] と等しい. した…

AOJ 1324 Round Trip

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1324 解法 最短経路(それはそう). 同じ高さの街が高々10しかないので,どの街に行ったか 2 ^ 10 で表現したい. どの街に行ったかを保存しつつ最短経路をやりたいね,となる. それには…

計算機科学実験及演習3ハードウェア(CPU製作)記

概要 この記事は,計算機科学実験及演習3ハードウェアという,京都大学情報学科3回前期に行われている実験の製作記録です. 去年は以下の方が書いていますが,これに感化されて僕も記録を残そうと考えました.主に後輩向けに書いています. joisino.hatenabl…

Codeforces Round #176 (Div.1) E. Ladies' Shop

問題文 http://codeforces.com/problemset/problem/286/E 解法 FFT. まず,答えの集合から生成できる任意の重さは,ある2個以下のカバンを使って(同じカバンを2つでもいい)作ることができる. なぜなら,もしある重さを p1 + p2 + p3 で生成したとする.…

AOJ 2703 Dice Stamp

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2703 解法 明らかに全てのサイコロを使うのが最適. あとは,後ろから見るbitDPで解く. これは,最後に使うサイコロから決めていくと,その直前に使うサイコロによる得点が,今まで使った…

AOJ 2572 Venn Diagram

問題文 Venn Diagram | Aizu Online Judge 解法 頑張って実装するだけ. 円の半径は入力からすぐわかる. 2つの円の距離を二分探索で求めたら,でかい方を左下隅に配置. 小さいほうは [0, pi/2] でどの角度に置くとよいかを判定.計算したくないので二分探…

AOJ 1252 Confusing Login Names

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1252 解法 以下の4パターン全部試すだけ. swap しない(単に編集距離の問題) 1回swapしたあと編集距離 2回swap 消した後 swap 最悪 200(200-1)/2 * 16 * (16 * 16) なので,まあ適当にや…

Helvetic Coding Contest 2018 E2. Guard Duty (medium)

問題文 http://codeforces.com/contest/958/problem/E2 解説 わからなかったので上位陣のコードから解法を得た. とりあえずソートして隣接項の差を作ると,以下の問題になる.n - 1 要素からなる数列から,k 個えらんでその和を最小化せよ.ただし,隣接2要…

AOJ 1371 Infallibly Crack Perplexing Cryptarithm

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1371 解法 現れうる文字は高々8種類しかない. なので各文字に対して何を割り当てるか全探索して構文解析するだけ. ソースコード #include <bits/stdc++.h> using namespace std; using ret_type = doubl</bits/stdc++.h>…

AOJ 1351 Flipping Parentheses

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1351 解法 StarrySkyTree + 二分探索で通した.( を +1, ) を -1 として累積和をStarrySkyTree上で管理する. 文字列が balanced であることと,累積和上の最小値が 0 以上であり,かつ末…

AOJ 1333 Beautiful Spacing

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1333 解法 二分探索+しゃくとり法. 二分探索は,普通に「スペースの隙間を X にして条件をクリアできるか」でやる.次にしゃくとり部分.二分探索の過程で与えられた,空けていい間隔を …

2014 Yandex.Algorithm Elimination Stage, Round 3 E - Tetrahedron

問題文 http://codeforces.com/gym/100459 解法 Standing -> 重心をおろした位置が底面の内部 Unstable -> 重心をおろした位置が底面の周上にある Falling -> 重心をおろした位置が底面の外部重心の座標は (a + b + c + d) / 4 なので,あとは底面の三角形と…

2014 Yandex.Algorithm Elimination Stage, Round 3 C - Intervals

問題文 http://codeforces.com/gym/100459 解法 しゃくとり法で解いた. 条件を満たさないようなペアの数を数えて,全体から引くことで求める. しゃくとりの過程で,今現在の区間が overlap しうるので,その分は足すことで重複して引かないようにしている…

2014 Yandex.Algorithm Elimination Stage, Round 3 B - Science

問題文 http://codeforces.com/gym/100459 解法1 行列累乗で解く. 左から順番に見ていった時,状態としては k + 3 種類ある. 最初の second type が来た状態,途中の first type (k個の状態がある),最後の second type が来た状態(受理状態),それ以…

2014 Yandex.Algorithm Elimination Stage, Round 2 F - Permutation Cube

問題文 http://codeforces.com/gym/100453 解法 X, Y, Z のそれぞれについて,巡回するいくつかのグループに分けることができる. 周期 a で巡回する列と,周期 b で巡回する列と,周期 c で巡回する列を考える.これらはそれぞれ X, Y, Z から持ってくると…

2014 Yandex.Algorithm Elimination Stage, Round 2 D - Inversions

問題文 http://codeforces.com/gym/100453 解法 長さを最小化するので,N * (N - 1) / 2 >= K && (N - 1) * (N - 2) / 2 あとは,上から順に,その位置の値を変えなければならないところまで順番に 1 から埋めていく. その場所まで来たら,変えないと行けな…

2014 Yandex.Algorithm Elimination Stage, Round 2 B - Remainders

問題文 http://codeforces.com/gym/100453 解法 ある数 a_i からスタートした時に,それ以上の値で余りをとっても変化はない. したがって,数列をまずソートし,最初にする数字を何にするか全部試すのが良さそうである. これは dp で計算できて, dp[i] :=…

2014 Yandex.Algorithm Elimination Stage, Round 2 A - Cycles with Common Vertex

問題文 http://codeforces.com/gym/100453 問題概要 n 個の鎖が与えられ,それぞれのサイズは c_i である. 鎖とは,連結グラフであり,かつ両端点以外の頂点の次数が2であるものである. これらの鎖を,鎖とは別に用意した1つの頂点 X に,その両端をつなげ…

2014 Yandex.Algorithm Elimination Stage, Round1 F - Data Mining

問題文 http://codeforces.com/gym/100448 問題概要 n 個の要素からなる数列 a が与えられる.あなたは以下の操作を k 回行える. ある要素の値を隣接する(どちらかの1方の)要素に加える. k 回の操作の後の,数列に含まれる値の最小値を最大化せよ. また…