東京工業大学でTarjan教授を拝見した

講義に出席した。顔を拝むのが目的。 Tarjan先生 我々が毎日書いているUnion-Findや強連結成分分解(lowlinkのやつ)の証明やらアルゴリズムやら考えたすごい人。 1時間の講義でZip Treeをマスターしよう。 Zip Tree 二分探索木の一つ。詳細な解説は講義に出…

Codechef April Challenge 2017 解法

Chef and Digits Problem Code: DGTCNT 各数字が出現した回数を覚えるような桁DPで攻めると駄目。 数字の集合S subset {0,...,9}を決めたとき、F(S, N):=#{Sに含まれる数字の出現回数が条件に一致するような0超過N以下の数}を求める。このときSに含まれない…

MM 93 CrossStitch

TopCoder Marathon Match 93 CrossStitchに参加した。 問題概要 クロスステッチと呼ばれる刺繍を作る。 入力で模様が与えられる。各色の糸ごとに布の表と裏を交互に移動して一筆書する。 表の糸の長さは入力で固定、裏の糸の長さをなるべく短くせよ。 図1枚…

データ構造のコンストラクタの書き方

c++0x書き始めた。データ構造書くたびに検索するのも効率悪いので覚える。 実態を持つ データが小さいときはあり。しかし特にサイズが大きい配列を持つと良くない、局所変数にしづらい。 template<int SIZE> struct Array { int d[SIZE]; Array() { // primitive型の場</int>…

ACM-ICPC 2016 Asia Tsukuba Regional, 解法目次

ACM-ICPC 2016 Asia Tsukuba Regional Informal Solutions はじめに 2016/10/16にICPC地区予選つくば大会が開催された。出題された問題に興味がある、と言うより部外者なので問題を解くしかやることがないので問題のことだけ書く。1週間経ってオンサイト参加…

ACM-ICPC 2016 Asia Tsukuba Regional, K 解法

K: Black and White Boxes 問題 アリスとボブがゲームをする。 箱が縦に一列に積み上げられており、各箱の色は白か黒である。この一列を山と呼び、山が複数ある。二人で交互に箱を取り除く。 アリスは黒箱を1つ選んで、その箱とその上に積んであるすべての箱…

ACM-ICPC 2016 Asia Tsukuba Regional, J 解法

J: Cover the Polygon with Your Disk 問題 円と凸多角形が与えられる。凸多角形の頂点は10個以下。それぞれ自由に平行移動・回転移動させて、共通部分の面積の最大値を出力せよ。 入力は整数で座標は0~100、円の半径は1~100。

ACM-ICPC 2016 Asia Tsukuba Regional, H 解法

H: Animal Companion in Maze 問題 グラフが与えられる。辺は有向のものと無向(双方向)のものがある。長さは全て1。 無向辺を通ったときにすぐ同じ辺を引き返してはならないとき、最長歩道の長さを出力せよ。 歩道とは頂点・辺の重複を許したパスのこと。 …

ACM-ICPC 2016 Asia Tsukuba Regional, G 解法

G: Placing Medals on a Binary Tree 問題 深さ10^9の完全二分木がある。根の深さは0、葉の深さは10^9。n個のメダルを順番に頂点に置いていく。このとき、部分木にメダルがある頂点には置くことができない。また頂点の深さはメダルに書かれている数と等しく…

ACM-ICPC 2016 Asia Tsukuba Regional, F 解法

F: Three Kingdoms of Bourdelot 問題 複数のドキュメントがある。各ドキュメントには家系図の情報が複数行書かれている。ドキュメントは正と負の2種類あり、各行はペア(x, y)であり、 ドキュメントが正の場合:xはyの祖先である ドキュメントが負の場合:x…

ACM-ICPC 2016 Asia Tsukuba Regional, E 解法

E: Infallibly Crack Perplexing Cryptarithm 問題 虫食い等式が与えられる。数式は2進数で数を表記し、BNFは次のように与えられる。 Q ::= E'='E E ::= T | E'+'T | E'-'T T ::= F | T'*'F F ::= N | '-'F | '('E')' N ::= '0' | '1'B B ::= empty | '0'B |…

ACM-ICPC 2016 Asia Tsukuba Regional, D 解法

D: Hidden Anagrams 問題 2つの同じ長さの文字列が、各アルファベットの出現数が同じであるとき、互いにアナグラムであると言う(多分同じ文字列もアナグラムという)。 2つの文字列が与えられる。それぞれから部分文字列を取り出して、それらがアナグラムで…

ACM-ICPC 2016 Asia Tsukuba Regional, C 解法

C: Distribution Center 問題 n本のコンベアラインが平行に並んでいる。各ラインiの左から製品iが右に向かって流れる。またm台のロボットが配置されてある。ロボットjは左からxjの位置にあり、ラインyj, yj+1の製品をそれぞれ反対のラインに移す事ができる。…

ACM-ICPC 2016 Asia Tsukuba Regional, B 解法

B: Quality of Check Digits 問題 一桁の数同士のX演算の定義テーブルが与えられる。iXi = 0が保証されている(i = 0 .. 9)。ある4桁の数 abcd (leading zerosを許す) に対して、e = (((0Xa)Xb)Xc)XdをCheckDigitとして5桁のabcdeについて、書き間違えを判…

ACM-ICPC 2016 Asia Tsukuba Regional, A 解法

A: Rearranging a Sequence 問題 始めに数列1 … n がある。「数e_iを先頭に移動させる」と言う操作をm回行う(1

van Emde Boas Trees を実装する

はじめに Introduction to Algorithms に載ってる、wikipedia:en:Van_Emde_Boas_tree の記事がある、日本語のslideshare Nazoki がある、のでそこそこ知名度があるvan Emde Boas Trees (vEB)。私の中での解釈はbit vectorを平方分割し、next / prevを付けた…

両端優先度付きキューのInterval-Heap実装

ヒープ / Double-Ended Priority Queue 優先度付きキュー、使い勝手が良くヒープ実装も簡単でデータ構造の入門書に書いて有ることも多いと思う。実装したのは勉強しだした最初の頃の1回だけな気がするので復習のために実装する。 G++のstd::priority_queueは…

ACM-ICPC 2016 Asia Tsukuba Regional 国内予選 参加しなかった記

詩 寝食も忘れて、なけなしの社交性も忘れて、プログラミングコンテストに励んでいた1年前の自分、今ではすっかり更生しプログラミングコンテストに出ることも減ってしまった。しかしICPCは解かずには居られない。 ※ 私は参加者・選手では無い リンク 問題 :…

ACM-ICPC 2016 Asia Tsukuba Regional 国内予選, H 解答

H: プレゼント交換会 問題 無向グラフがある。全ての辺に向きをつけなさい。そのとき、すべての頂点の入次数の最大値と最小値の差が最小に成るようにし、その時の最大値・最小値を出力せよ。 複数ある場合は最小値を最大化せよ。

ACM-ICPC 2016 Asia Tsukuba Regional 国内予選, G 解答

G: ワープ航法 問題 平面上に2つのワープ場を設置したい。ワープ場にたどり着いた航空便は平面の任意の位置に瞬時に移動する事ができる。今、2次元平面上に n箇所の街がある。m本の航空便があり、航空便はある街a_iから他の街b_iへ、速さv_iで直線距離で最短…

ACM-ICPC 2016 Asia Tsukuba Regional 国内予選, F 解答

F: 文字解読 問題 グリッドの2値画像が与えられる。この画像は「文字」として認識することができる。 白マスは4方向に連結する 黒マスは8方向に連結する 画像の外側は無限に白マスとし、背景と呼ぶ また、白マスや黒マスの連結成分について包含の条件がある(…

ACM-ICPC 2016 Asia Tsukuba Regional 国内予選, E 解答

E: 3D プリント 問題 3次元空間に1辺長さsの立方体の設計図が n個ある。全ての立方体は3つの軸に平行で、頂点は整数座標。 ある2つの立方体が共通部分を持つとき連結しているといい、複数の立方体が次々に連結していれば大きな一つの立体になる。 n個の設計…

ACM-ICPC 2016 Asia Tsukuba Regional 国内予選, D 解答

D: ダルマ落とし 問題 長さnの数列aが与えられる。次の操作を好きなだけ繰り返す。 数列の任意の隣り合う2数を一つ選び、その差の絶対値が1以下ならばその2数を数列から取り除き、数列は詰めて長さが2短くする 最大で幾つ取り除くことができるか。

ACM-ICPC 2016 Asia Tsukuba Regional 国内予選, C 解答

C: 竹の花 問題 m以上の整数をn個選ぶ事を考える。「m以上の数の内、選ばれたどの数の倍数でもない数」の最小値をその選び方のスコアとする。任意の選び方のスコアの最大値を出力せよ。

ACM-ICPC 2016 Asia Tsukuba Regional 国内予選, B 解答

B: 当選者を探せ! 問題 選挙の開票を行う。26人の候補者があり、票の総数はnで、1票づつ開けていく。 単独首位で当選確実になった候補者が初めて決まるのは何票目で誰か、出力せよ。 ただし開票して首位が2人以上いるならば"TIE"と出力せよ。

ACM-ICPC 2016 Asia Tsukuba Regional 国内予選, A 解答

A: 被験者の選定 問題 n個の整数が与えられる。任意のペアについて最小の差の絶対値を求め、出力せよ。

ACM-ICPC World FInals 2016 in Phuket, 解答案

ACM-ICPC World FInals 2016 in Phuket, solutions 1年前のWFを期にプログラミングコンテストの参加が激減した私。本戦参加はしていないが問題だけは確認しておく。

ACM-ICPC World Finals 2016 M解法

M: What Really Happened on Mars? 問題 t個のタスクがある。各タスクは命令の列で、命令は3種類 compute : 1クロック消費する。 lock k : リソースkをロックする unlock k : リソースkをアンロックする 各タスクiは開始の時刻t_iと優先度p_iを持ち、時刻に…

ACM-ICPC World Finals 2016 L解法

L: Swap Space 問題 n個のHDDがある。 それぞれは現在 容量a_iで、一つづつ取り替えて容量b_iにしたい。 HDDは全てフルに容量が埋まっており、取り替えるときはデータをn個の中の他のHDD、もしくは追加のHDDに移して、空になってからb_iになる。複数に分けて…

ACM-ICPC World Finals 2016 K解法

K: String Theory 問題 文字列について、先頭と末尾が「'」(シングルクォート) で、間にアルファベットのみが0文字以上あるものを1-quotationと定義する。 k > 1について、先頭と末尾がちょうどk個のシングルクォートで、間には「(k-1)-quotationとシングル…

ACM-ICPC World Finals 2016 J解法

J: Spin Doctor 問題 n人の個人情報が与えられる。i番目の人の情報は a_i : 覚えている円周率の桁数 0 ~ 2000000 b_i : 髪の毛の本数 0 ~ 2000000 c_i : 候補者Xに投票したかどうか 0/1 実数のパラメータS, Tを適切に決めて人々を (a_i * S + b_i * T) の値…

ACM-ICPC World Finals 2016 I解法

I: Road Times 問題 n 頂点 m 辺の有向グラフが与えられる。 各辺は距離[km]が与えられる。 あなたが頂点uからvへ移動するときには、必ず距離が最短に成るように移動する。 各辺は速度が定数で制限されており、それは時速30km以上60km以下の実数の定数で、あ…

ACM-ICPC World Finals 2016 G解法

G: Oil 問題 地面水平方向x軸。垂直方向下向y軸。y=0が地表の2次元座標上の問題。 油井は地中にあり、地表と水平な線分で表される。 n個の油井のいち情報が与えられる。 地表から1本の直線状に任意の角度でドリルで掘って、接するか交差した油井の油を得るこ…

ACM-ICPC World Finals 2016 F解法

F: Longest Rivers 問題 n+m+1頂点、葉がn個の重み付き根付き木が与えられる。 各葉は川の源流で、川は辺にそって根の方向に続く。すべての辺はただ一つの川に属する。 (辺をn個の川に分割する、一つの川はつながって枝分かれしない。合流した川はいずれか一…

ACM-ICPC World Finals 2016 E解法

E: Forever Young 問題 私はY歳です。 適切なBを求めて、「YをB進数で表した時全ての桁は0~9であり、その表示を十進数とみなすとL以上である」ようにしなさい。 その最大のBを出力しなさい。

ACM-ICPC World Finals 2016 D解法

D: Clock Breaking 問題 7セグデジタル時計がある。4桁とコロンの2セルの計30箇所のセグの表示がある。 この時計は壊れている可能性があり、各セグは 正しく動作する 常に0を表示する 常に1を表示する のどれかである。

ACM-ICPC World Finals 2016 C解法

C: Ceiling Function 問題 n個のk頂点-二分探索木が与えられる。 二分探索木は挿入する値とその順番によって与えられる(回転などはしない)。 何種類の形があるか数えよ。

ACM-ICPC World Finals 2016 B解法

B: Branch Assignment 問題 n 頂点 r 辺の重み付き有向グラフがある。頂点はv_1 ... v_nとする。 そのうち、v_1 ... v_bのb個の頂点はbranch (支店)が置いてあり、v_{b+1}にはheadquarter(本店)がある。 支店をs個のグループに分割したい(s 月に一度、各支…

ACM-ICPC World Finals 2016 A解法

A: Balanced Diet 問題 Dannyはm種類の菓子を一つづつ食べる。今までの菓子iを食べた個数をs_iとする。 各菓子iの個数は割合f_iに近い値にしたい。 正確には、今まで食べたお菓子の総数をnとすると、任意のお菓子iは を満たす必要がある。すでに、k個のお菓…

ACPC 2015 Day3 解法

ACPC2015Day3 University of Aizu Competitive Programming Camp 2015 Day 3 http://judge.u-aizu.ac.jp/onlinejudge/contest_problem.jsp?id=ACPC2015Day3 3時間7問 問題・解法アニメセット? 各問題で物語がついていて凝ってる. 問題文にそれぞれライター…

ACPC 2015 Day2 解法

University of Aizu Competitive Programming Camp 2015 Day 2 問題・解法 http://judge.u-aizu.ac.jp/onlinejudge/contest_standing.jsp?id=ACPC2015Day2 5時間 12問1日目は参加してない。公式の解説とか上がるのかな。 問題文は全て意訳。AOJランキングも…

ASC47 問題・解法

2014-2015 Winter Petrozavodsk Camp, Andrew Stankevich Contest 47 (ASC 47) Solutionsサイト http://codeforces.com/gym/100608 問題文 http://codeforces.com/gym/100608/attachments/download/3181/20142015-winter-petrozavodsk-camp-andrew-stankevic…

C++の関数オブジェクトが関数よりどれだけ速いか

C++では関数オブジェクトのほうが関数より速い。呼び出しの時間に差がある様子。 数回呼ぶだけなら誤差だが呼ぶ回数が増えるとその速度は有利。 ソート std::sortの比較関数に関数や関数オブジェクトを与える。 関数 bool cmp(int x, int y) { return x < y;…

Live Archive Root :: Regionals 2011 :: Europe - Central

Live Archive Root :: Regionals 2011 :: Europe - Central https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&category=526良問。スペシャルジャッジに対応していない様子なので、一部AC出ない(単にWAなのかも知れないが)。…

Live Archive 5888 - Stack Machine Executor

問題 Stack Machineというスタックベースのプログラミング言語が定義されている。実装せよ。 解法 スタック言語なので実装は難しくない。 エラー処理がやや面倒。

Live Archive 5887 - Unchanged Picture

問題 線画が2つ与えられる。平行移動拡大縮小回転させて一致するか判定せよ。。 座標は全て整数。 入力は相対ベクトルでsvgのようなフォーマットで与えられ、線分は1000程度。 解法? 幾何で難易度わからなくて手を付けてない。 適当に2頂点一致させて残りを…

Live Archive 5886 - The Grille

問題 NxNのテキストと、マスクが与えられる。 次の操作を4回せよ。 マスクの空きマスの文字を出力し、マスクを90度時計回りに回転させよ。 解法 問題そのまま。 実装するだけ問題。

Live Archive 5885 - Vigenere Cipher Analysis

問題 Vigenere Cipherのルールでエンコードされた文字列C、エンコードに用いたkeyの長さの上限値K、元のテキストに含まれていた文字列W1, W2が与えられる。 len(C) デコードし、結果が1通りならデコードされたテキストを出力せよ。 結果が0通りもしくは2通り…

Live Archive 5884 - Strange Regulations

問題 グラフが与えられる(頂点数N 各辺は会社i(1 グラフは単純グラフで、会社が違ったとしても多重辺は存在しない。 グラフは常に次の制約を満たす。 各会社の辺だけを使う部分グラフは枝分かれが無く、サイクルが無い。 各クエリを順に処理せよ クエリは3…

Live Archive 5883 - Stack Machine Programmer

問題 スペシャルジャッジに対応していない様子なのでジャッジ解提出する以外AC取れない気がする。 先に5888をやるべき。パズル系の問題。 Stack Machineというプログラミング言語が定義されている。 入力V[i]と出力R[i]のペアがN個与えられている。 入力はプ…