IBM Quantum Challenge 2020 参加記

はじめに 2020/11/8 から3週間開催された IBM Quantum Challenge に参加しました.せっかくなので記事に残しておきます.今後参加する人も増えそうなので,参考になればと思います.www.ibm.com 各問題についてのコメント 第1週 問題a 基本的な量子ゲートの…

ICPC2020 国内予選 参加記

はじめに 2020/11/7 に行われた ICPC 国内予選に suibaka, nakano, otera1999 の3人で参加しました. 結果は 29位 と力及ばず,ここ3年で最も低い順位をとってしまいました. この結果,僕と nakano は今回で引退となります.せっかくなので記録を残しておき…

AOJ 1629 正三角形の柵 (Equilateral Triangular Fence)

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1629&lang=ja 解法 底辺の y 座標を決めうったとする.これを \(y_l\) とおく. \(y \geq y_l\) をみたすある点 \((x, y)\) が正三角形の内部にあるための条件は,底辺の左端と右端の x 座…

AOJ 1623 等積変形 (Equivalent Deformation)

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1623&lang=jp 解法 点を合わせる順番と対応を全部試して探索するだけで解ける. 点を合わせるときは,直接合わせられる場合は直接合わせればよいし,そうでない場合は残りの2点のどちらか…

AOJ 2559 Minimum Spanning Tree

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2559 解法 マージテクだけで解ける. 最初に MST を構成しておく.MST に含まれない辺は自明. 以下MSTに含まれる辺についてコストを求める. MST 上を DFS で探索し,各部分木から外に生…

AOJ 2907 Prefix Suffix Search

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2907 解法 \(w_i\) をそれぞれ逆にした文字列集合を \(\{rw_i\}\) とする. 最初にそれぞれをもともとのインデックスが分かるようにソートしておく. 以降は \(w_i, rw_i\) はソート済みで…

LuaTeX で源ノ角フォントを使う

TeX

概要 LuaTeX で Google + Adobe の源ノ角フォントを使う備忘録. TexLive を使用していることを前提としている. フォントのダウンロード https://github.com/adobe-fonts/source-han-sans/tree/release https://github.com/adobe-fonts/source-han-serif/tr…

ICPC Asia Yokohama Regional 2019 参加記

はじめに 参加記です。はてなブログが乗っ取られていて書くのが遅れました…。 Day1 朝から横浜に出発します。早速乗るはずだった新幹線を逃しました。ちなみに偶然 TigerSone*1と同じ新幹線だったのですが、 etonagosa が予定の新幹線に乗り遅れそうになる …

動的計画法入門 1

はじめに 大学内の KCPC という競プロ同好会において、初心者向けに動的計画法のスライドを書いたので公開しておきます。 スライド ちなみに(スライド内容とは関係ないです) とある先輩に「知見は共有して欲しい」と言われたのが公開の動機だったりします。…

ABC 137 F - Polynomial Construction

問題文 https://atcoder.jp/contests/abc137/tasks/abc137_f 解法 想定解はかなり頭がいいが、今回は汎用的なラグランジュ補間で解く。 今 \(n\) 次の多項式 \(P(x)\) が \(P(x_i) = y_i ~(i = 0, \ldots, n)\) を満たすとする。このとき、$$P(x) = \sum_{i …

ICPC 2019 国内予選 参加記

はじめに 7/12 に行われた国内予選に SleepingDragon で出ました。 チームメイトはいつもの kazuma, nakano です。 コンテスト内容 問題を読む前に bashrc に alias の設定だけする A を読むとはいなので書く 入力形式を見間違えていてサンプルが合わなかっ…

AOJ 1387 - String Puzzle

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1387 解法 各分割区間と一致する場所が、「より左にある」という制約が重要で、これにちゃんと気がつけば解ける。 これによって 文字列のある位置の文字と別の位置の文字が、与えられた条…

ゼッケンドルフの定理と全探索

はじめに 友人と会話してて得られた知見で、共有したいと思います。 ゼッケンドルフの定理 ゼッケンドルフの定理は 任意の正の整数が、連続するフィボナッチ数を含まないような形で、相異なる1つ以上のフィボナッチ数の和として一意に表現できる というもの…

AOJ 1191 - Rotate and Rewrite

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1191&lang=jp 解法 こういう問題に対する典型的な発想として、一文字ずつ構成していく、というものがある。 つまり、A の先頭位置と B の先頭位置を決めうった後、一文字ずつ作っていって…

AOJ 1158 - ICPC: Intelligent Congruent Partition of Chocolate

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1158 解法 \(_{36}C_{18}\) は流石に間に合わない。 しかし、2つの領域を合同かつ連結になるように選んでいけば、探索空間はそんなに大きくないように思える(実際大きくない)。 なので、…

AOJ 2682 - Polygon Guards

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2682 解法 答えは 9 以下なので全探索で間に合う(えぇ…)。 前処理で、ある点に配置したときにどこが見えるようになるかを bit で管理すると判定が O(1) になる。 視線の線分が多角形内部…

AOJ 2724 - Laser Cutter

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2724 解法 結論を言えば、最小重み二部マッチングに帰着できる。線分の交点と端点が頂点になった有向グラフを考えると、考えるべき問題は「いくつか辺を追加することで、最小重みのオイラ…

ICPC 模擬国内予選 2019

はじめに 2019/Practice/模擬国内予選 - ACM-ICPC Japanese Alumni Group の参加記です。kazuma, nakano と SleepingDragon として出ました。 コンテスト内容 A を読む、やるだけなので投げる、WAになる 2回目のケースで1回目のテストケース結果提出してた(…

AOJ 2691 - Cost Performance Flow

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2691 解法 流量1ずつ流していったときの最小費用流のコストのグラフは、下に凸な折れ線グラフになる。 求める値は、このグラフと点 \((M, 0)\) との距離であり、グラフの形からこの距離も…

AOJ 2202 - Canal: Water Going Up and Down

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2202 解法 全長が小さいので DP する。 reach[i][j] := 船 i が位置 j に到達する最短時刻これはあくまでも「到達」時刻であり、その地点を出発できる時刻ではない(門の上下などで停泊す…

AOJ 2385 - Shelter

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2385 解法 こんなの積分するしかないでしょという気分になるので立式する。 とりあえずボロノイ図を考えると、凸多角形領域 \(D\) とその内部の1点に対する問題に帰着できる。 内部の点を …

AOJ 2569 - Putter

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2569 解法 線分の通り方を n! 通り全探索する。 ある線分を通る時に、その線分で点を鏡写しにしていけば、直線がそれらの線分を貫くかどうか、という問題になる。 この判定は角度(厳密に…

AOJ 2164 - Revenge of the Round Table

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2164 解法 回転して同じものはとりあえず重複して数える。 というのも、もし周期 s の並べ方があったとしたら、回転して同じとみなせるものは s 通りだとわかるからだ。まず、先頭を A に…

AOJ 2343 - Matrix Operation

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2343 解法 操作に必要な情報は、 鏡写しの状態になっているか 何回転しているか どこに何が書き込まれたか (WR, CP) 列 or 行の並びはどうなっているか だけなので、各操作に対し O(1) or …

AOJ 2430 - Longest Increasing Sequence

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2430 解法 やり方は2通りあるんですが、片方はちょっとメモリが厳しかった(通ったけど)。 メモリが厳しいほう dp[i][j] := i 個目までみて最大長さが j であるときの右端の min と定義。…

AOJ 1341 - Longest Chain

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1341 解法 動的2次元セグ木とかで解けそうだけど、ICPC でデータ構造の問題はチームメイトに投げるため違う解き方をする。 とりあえずソートができるので3次元 -> 2次元になる。 1次元のと…

AOJ 2172 - Queen's Case

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2172 解法 ゲームの状態グラフにループがあるので、ただ DFS やるだけだとうまくいかない。 これは後退解析という手法で解けて、ど典型なので知らなかったら覚えてしまってよい(どの問題…

AOJ 2587 - Elevator Hall Number

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2587 解法 桁DPしようと思ったが、遷移がうまく書けないので困った。 そこでオートマトンをイメージする。 結論を言うと、a[i] の値で NFA を作ってから DFA に変換し、その上で DP する。…

AOJ 1317 - Weaker than Planned

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1317 解法 普通のバックトラックで解ける。 バックトラックするときは、どういう順番で探索すると枝刈りが起こりやすいかを考える必要がある。 今回なら、文字の種類数が多い方を先に考え…

AOJ 1307 - Towns along a Highway

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1307 解法 こういうのは確定できるところからさせるもの。 とりあえず一番遠いところは unique に定まるので確定させる。 次は、残ってる d の中で最も大きい値を選ぶ。 こいつは、明らか…