ゆらのふなびと

競プロ, Python, C++

ICPC

AOJ-ICPC 400 インビジブル

問題 インビジブル | Aizu Online Judge D: インビジブル - JAG Contest 2016 Domestic | AtCoder 解法 先手はスコアの最大化、後手は最小化を目指すのでミニマックス法で解ける。 先手, 後手のデッキでスタックにつまれている区間をそれぞれ[l0, r0), [l1, …

AOJ-ICPC 300 Line Gimmick

問題 Line Gimmick | Aizu Online Judge 解法 実装しんどいなーと思いながら書いたら一発で通って最高↑↑な気持ちで解説を見たらすごい簡単で悲しくなったので書きます。 ある'>'(=R0)からスタートすると、向きが変わるのはR1より右側にある1つ目の'<'(=L1), …

AOJ-ICPC 300 ABC Gene(☆)

問題 ABC Gene | Aizu Online Judge 解法 操作を逆順に考える。ある文字列 t を1段階前の文字列sに戻すことを考えると、t の中にある任意の"ABC"は、sにおいては直前の置換で選んだ文字Xだったはずである。仮にsに"ABC"が含まれていれば、必ずXが"ABC"に置換…

AOJ-ICPC 450 Encryption System

問題 Encryption System | Aizu Online Judge 解法 入力の文字列を s, 暗号化前の文字列をtとする 任意のiについて、t_i = s_i or s_i + 1 の2通りしかないので 220 の全探索が間に合う 左から見ていくと、t_i = s_i としてよいのは i の前に少なくとも1つ s…

AOJ-ICPC 400 Restrictive Filesystem

問題 Restrictive Filesystem | Aizu Online Judge 解法 setで頑張る。 計算量がやばそうだったけど意外とそうでもないらしい 最初は区間の(左端, 番号)だけでやろうとしていたけどそれだと隣り合う空の区間をマージしないといけない場合がでてきてつらかっ…

AOJ-ICPC 300 Mirror Cave

問題 Mirror Cave | Aizu Online Judge 解法 脳筋BFS DFSで書いたらREしたのでスタックオーバーフロー? 縁を'#'で埋めると楽 「片方だけが先にゴールについたらダメ」を忘れて死んでいた gist.github.com

AOJ-ICPC 400 お姫様の暗号解読

問題 Princess, a Cryptanalyst | Aizu Online Judge N個の文字列が与えられる。これらすべてを部分文字列として含む最小長さの文字列を求めよ。ただし、最小長さの文字列が複数ある場合はそのうち辞書順最小のものを答えよ。 制約 1 <= N <= 10 各文字列 s_…

AOJ-ICPC 400 Eleven Lover

問題 Eleven Lover | Aizu Online Judge 10進数表記の数sが与えられる sの部分文字列のうち、11の倍数であるものの個数を答えよ ただし、部分文字列のうち先頭が0でないもののみをカウントする 制約 |s| <= 80000 解法 「11の倍数 ⇔ D = (奇数桁目の和) - (…

AOJ-ICPC 350 Railroad Conflict

メモ:直線の交点のパラメータの求め方について。 問題 黒い線分と赤い線分が合わせて n 本フィールドに散らばっている。フィールドには地上・地下の2つのレイヤーがあり、どの線分も地上または地下にある。今から青い線分を与えられた点A, B間に1本引く。青…

AOJ-ICPC 350 Slim Span

問題 グラフの全域木の中で、辺の重みの最大値 と最小値 の差 が最小となるようなものの を求めよ。また、全域木が構築できないならばその旨を答えよ。 Slim Span | Aizu Online Judge 制約 頂点数: 辺の本数: 辺 の重み: グラフは無向単純連結グラフ 解法 …

AOJ-ICPC 300 Building a Space Station

問題 n個の球がある。球iは中心(x_i, y_i, z_i), 半径r_iである。これらの球の間に必要であれば橋を架けることで、すべての球の間を連結にしたい。ただし最初から共有点を持つ球どうしや、片方がもう片方を内包するような球どうしは既に連結であるとみなす。…

JAG模擬国内予選2016B (A-D)

チームMusyoku(ソロ)で参加し,4完で全チーム中24位でした. 模擬国内Aのときは自力では2完だったので,少しは解けるようになったかな. A. カレー作り 式変形して,実行可能な最小の解xをループで求める. (コードについて)本当はyの符号だけわかればよいの…

AOJ-ICPC 250 Fastest Route

ICPCを埋め始めましたよっと。 問題 このゲームには1番から N 番までの N 個のステージがあり,任意の順に攻略することができる. また,1から N まで番号付けられた装備があり,それらの装備を使用することでステージの攻略時間を短縮することができる. ゲ…

AOJ-ICPC 450 Substring

ロリハの練習問題として。 問題 Substring | Aizu Online Judge 制約 解法 ローリングハッシュ。となることを利用すると、各クエリに対してでハッシュが求まる。 前のハッシュに足したり引いたりで事足りるのでは?という考えも浮かぶが、ロリハは普通には割…