MARVELの映画でディズニーデラックスで公開されてるものを見終わった。アントマン＆ワプスやインフィニティウォーまで。 話が面白いのは当然なので映像とか演出について。 登場するロシア人はロシア語を話すこともあるし、ノルウェー人はノルウェー語を話す…

英語のリスニングを向上させるという邪な理由でDisney deluxeを見始めた。31日間無料、以降756円/月。まずはMarvelを古い順に観る。 音声・字幕それぞれ英語・日本語が好きな組み合わせで利用できる。ビデオプレーヤーはシークバー、30秒進める・戻る、フル…

CODE FESTIVAL 2016 Grand Final(Parallel) J - 123 Pairs 解法 https://atcoder.jp/contests/cf16-exhibition-final-open/tasks/cf16_exhibition_final_j 問題 1から2NをN個のペアに分割したい。このとき、差が1のペアA個、差が2のペアB個、差が3のペアC個…

CODE FESTIVAL 2016 Grand Final H - AB=C Problem https://atcoder.jp/contests/cf16-exhibition-final-open/tasks/cf16_exhibition_final_h 問題 正方行列Cが与えられる。C=ABを満たすような正方行列のペア(A, B)はいくつあるか求めよ。 行列の要素の演算…

実用的に高速 コード SubsetSumNewton.cpp \( O(n + t\log t) \) と SubsetSumRecursive.cpp \(O(n + t \log^2 t)\) SubsetSumNewton.cpp · GitHub 概要と意訳 Ce JinさんとHongxun WuさんのA Simple Near-Linear Pseudopolynomial Time Randomized Algorith…

概要 Longest increasing subsequence 問題はFenwick treeを用いてO(n log m)で解ける（nは列の長さ、mは要素の最大値） 実行時間としては二分探索を用いる方法と大きな差はない 動機 今朝のCodeforces Round #468の他人のコードを見るとLISをFenwick treeで…

問題 二次平面上に軸に平行な長方形がn個与えられる。 入力として与えられる長方形について、どの二つの長方形も、 共通部分を持たない 一つの長方形がもう一つの長方形の真に内側にある のどちらかを満たすことを保証する。これらの長方形の包含関係から根…

less<>を使えばよい。 問題 (名, 姓)のpairがたくさんあってset >に格納されている。 (Alice, Acer) (Anna, Cork) (Bella, Bread) (Bella, Field) (Cherry, Card)名が一つ与えられたときに姓が辞書順最小の人を見つけたい。 例えばBellaが2人いるが、Bellaの…

SnackDown 2017 Online Elimination Round Cleaning the Space (SPCLN)https://www.codechef.com/SNCKEL17/problems/SPCLNこの問題は https://www.codechef.com/problems/RINと同値。問題設定や変数名を変えただけ。Editorialもある。 解法 最小カット問題と…

SnackDown 2017 Online Elimination Round Prefix XOR (PREFIXOR)https://www.codechef.com/SNCKEL17/problems/PREFIXOR https://www.codechef.com/viewsolution/14319736 問題 非負整数列A[1]..A[n]が与えられる。次のオンラインクエリに答えよ (l, r)：次…

SnackDown 2017 Online Elimination Round 解法案 Black Nodes in Subgraphs (BLACKCOM)https://www.codechef.com/problems/BLACKCOM/ https://www.codechef.com/viewsolution/14319524 問題 入力でN頂点の木が与えられる。各頂点は白か黒のどちらかの色が塗…

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

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

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

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

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

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

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

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

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

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

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 |…

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

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

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

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

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

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

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

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