ゆらのふなびと

競プロ, Python, C++

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である。これらの球の間に必要であれば橋を架けることで、すべての球の間を連結にしたい。ただし最初から共有点を持つ球どうしや、片方がもう片方を内包するような球どうしは既に連結であるとみなす。…

ABC040 D - 道路の老朽化対策について

問題 N個の都市がM本の道路でつながれている。i本目の道路は都市a_iとb_iを結び、y_i年に造られたものである。 Q人の国民がいる。国民jは都市v_jに住んでおり、作られた都市がw_jより大きな道路しか使わない。 各国民について、自身が住んでいる都市から条件…

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

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

ABC038 D - プレゼント

問題 i 個の数の組 (w_i, h_i) が与えられる。これらから自由に選んで並べてw, hともに狭義単調増加な列を作るとき、その最大の長さは? 制約 1 <= N <= 105 1 <= w_i <= 105 1 <= h_i <= 105 解法1: LIS まず、入力をwの昇順にソートします。すると、以下の…

Codeforces Round #353 (Div. 2) A~D

結果 1完でひどい。 Aが落ちてたり、他にもデバッグ出力を消し忘れてWAしたりTLE解を気づかずに出してたりと非常に頭が悪い。 大反省。。。 ただ、問題は面白かったです。 A. Infinite Sequence 問題 Problem - A - Codeforces 初項a, 公差cの等差数列にbが…

ARC031 C - 積み木

BITの使い方を勉強しなおした。 問題 1, 2, ..., Nの順列がある。この順列の隣り合う2つの要素を並び替えるという操作により数字を山型に並び替えるには最小何回の操作が必要か。 制約 1 <= N <= 105 解法 Nをどこに持ってくるかの全通りに対して、左側の反…

square869120Contest #2 H - Counting 1's

問題 H: Counting 1's - square869120Contest #2 | AtCoder N個の0が並んでいる。 以下のクエリを処理せよ。 クエリ1: 区間[l, r)のビットを反転させる。 クエリ2: 区間[l, r)内の1の数を答える。 解法 遅延セグメント木。区間の問題なのでセグ木という発想…

Codeforces Round #350 (Div. 2) A ~ E

結果 pretest通したやつは全部通ってた。 今回は初めてCオープンしてみましたが、いい感じ。A, Bは落とさないように気を付けても結局落ちたりして費用対効果が薄いので…だったら高い得点を取れるうちにCを解いてしまった方がよさそうという考え。 レーティン…

yukicoder No.365~368 コメンタリー

Twitterに流したものをこちらにも残しておきます。 【No.365 ジェンガソート】 最初の2問はコンテストが決まってから「★1, 2がない!」ということで作った問題です。「ちょっと考える★1」を狙って作りました(が、結局★2になってしまいすみません。)テスタ…

SRM538 Div.1 Med(450) TurtleSpy

Div.1 Medium 初AC! 問題 TopCoder Statistics - Problem Statement ロボットに以下の命令を送ることができる。 その場で左(右)に向きをx度変える(xは1以上359以下の整数) 前(後ろ)に距離xだけ進む 使える命令文(「左に50度曲がる」など)が与えられるので…

SRM538 Div.1 Easy(250) EvenRoute

気づけばとても簡単な問題。 問題 TopCoder Statistics - Problem Statement いくつかの格子点が与えられる。原点からスタートし、与えられたすべての格子点を1度以上通り、与えられた格子点のどこかで終了するパスを考える。このようなパスのうち、長さの偶…

AOJ-ICPC 250 Fastest Route

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

Codeforces Round #331 (Div. 2) A~C

virtual。 結果 2完。Aは場合分けをややこしく考えていてバグらせた。Bの方が簡単。Cはひたすら実装がしんどかったが考え方から違った感じ。 A. Wilbur and Swimming Pool 座礁軸に平行な辺を持つ長方形の頂点の4つのうち、いくつかが失われた。もとの長方形…

yukicoder no.349/350/351/352 参加した

今回はコンテスタントとして参加。 結果 初の全完。イェイ。 今回は☆3までだったのでなんとかなったという部分もある。 No.349 干支の置き物 12種類の干支の置物がある。それぞれの個数が与えられたとき、同じ種類の置物が隣り合わないように横1列に並べるこ…

Codeforces Round #332 (Div. 2) A~C

virtualで参加。 結果 時間内にACできたのはAだけ。1:30くらいで降参してEditorialを見ました。 A~CはすべてPythonで解けるくらい実装は軽かったので、しっかり解きたかったところ。 A. Patrick and Shopping Problem - A - Codeforces 通り方はすべてで4通…

AOJ-ICPC 450 Substring

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

SRM684 Div.1 Easy(250) CliqueParty

問題 TopCoder Statistics - Problem Statement 集合aは異なる正の整数からなる。aの部分集合に含まれる任意の要素の組(A, B)に対し、|A-B|を要素とする集合をDとする。Dがk-smoothとなるようなaの部分集合の最大の要素数を答えよ。ただしk-smoothとは、集合…

ABC009 D - 漸化式

行列累乗は半環なら普通の演算以外でも使えるよ!という問題。 問題 数列 A はすべての要素が 32 ビットの符号なし整数で表現でき、その値は次のようにして決まる。 はじめの K 項 A1, A2, …, AK は入力で与えられる。 A とは別に K 項の数列 C1, C2, …, CK …

RUPC2016に参加しました

立命館大学競技プログラミング合宿(RUPC)2016に参加したので、参加記を書くアレします。 参加した理由 直接のきっかけは、@DarseinさんがRUPCのツイートをRTしていたのを見たことです。オンサイト楽しそうというのはDDPC等への参加者を見ていてずっと思って…

ABC027 D - ロボット

想定解賢いなあ…という感じ。 問題 D: ロボット - AtCoder Beginner Contest 027 | AtCoder 数直線の原点にロボットが置かれている。 はじめ、ロボットの幸福度は 0 である。 このロボットに命令列が与えられる。 命令列は次の 3 文字のみからなり、先頭から…

Codeforces Round #345 (Div. 2) A. Joysticks

ひっかかったので書いとく。 問題 Problem - A - Codeforces 解法。 問題をよく読む。終了条件は「チャージが0になったとき」だけではない。 Game continues while both joysticks have a positive charge. Hence, if at the beginning of minute some joyst…

RUPC2016 Day1 C : AddMul

本番ではkenkooooさんにお任せしていた問題。 問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day1&pid=C 解法 次の例を考える。 a+b+b+b+c+c+c+d+d+d = 1*a+3*b+3*c+3*d (15文字) 左辺が入力、右辺が掛け算のみを用いた短縮形…

RUPC2016 Day1 D : Scanner

昨日解けなかったDP。 問題 AIZU ONLINE JUDGE 解法 DP。本番は貪欲法(Tを昇順にソートして、今までにかかっている時間が最小のスキャナーに順番に入れていく)で挑んだが、これは「1,2,3,4,5,6,7,8,9」というケースでWAする。(正解は15, 15, 15だが、この貪…

RUPC2016 Day2 G : Max Pig Noodle

本番でctylさんが解法を編み出し、自分が実装した問題。 問題 http://judge.u-aizu.ac.jp/onlinejudge/cdescription.jsp?cid=RitsCamp16Day2&pid=G 解法 DP。int dp[xの残量][yの残量] = このx, yで実現できる最大のブタメソの最大個数とすればよい。交換人…

SRM 679 Easy(250) FiringEmployees

「制約の有効活用」 問題 企業内の上司・部下の関係が木構造で与えられる。各従業員は自分よりも番号の若いいずれかの従業員の部下である。従業員ごとに利益の額が設定されている(これは正にも負にもなりうる)。さて、何人かの従業員を解雇することで企業の…

ABC014 D - 閉路

どこからLCAなんて発想が出てくるの!?と思った人用。 問題 木に辺を追加したときの閉路長を各クエリに対して求めよ。 制約 頂点数: クエリ数: 解法 辺 を追加したときの閉路長は、もとのグラフにおける点 と点 との最短距離を とすると、 (追加する辺の長…

SRM 680 Div.1 Easy BearFair

Div.1 Easy 4題目。 問題 https://community.topcoder.com/stat?c=problem_statement&pm=14129 以下の条件を満たす集合が存在するか判定せよ。 要素は互いに異なる正の整数 要素数 は偶数 集合は 個の偶数と 個の奇数からなる 要素はすべて 以上 以下 以上 ]…

CODE FESTIVAL 2015 予選A D - 壊れた電車

kenkooooさんのブログにSRM681 Div.1 Easy FleetFunding - ゆらのふなびとの類題として載っていたので。 問題 N両編成の電車をM人の整備士で点検する。i人の整備士は最初X_i両目の車両にいる。車両の点検には時間はかからないが、隣の車両に移動するには1分…

SRM681 Div.1 Easy FleetFunding

Div.1 Easy 3題目。 問題 https://community.topcoder.com/stat?c=problem_statement&pm=14104&rd=16651 1からmまでの番号がつけられたm種類のパーツがある。宇宙船を1隻造るにはm種類のパーツすべてが1個ずつ必要である。また、パーツを生産するn個の工場が…

SRM232 Div2 Hard StockHistory

ちょくだいさんの本(↓)に載っていたので解いた。 最強最速アルゴリズマー養成講座 プログラミングコンテストTopCoder攻略ガイド作者: 高橋直大出版社/メーカー: ソフトバンククリエイティブ発売日: 2012/09/29メディア: 大型本購入: 9人 クリック: 319回こ…

SRM682 Div.1 Easy SmilesTheFriendshipUnicorn

問題 https://community.topcoder.com/stat?c=problem_statement&pm=14104 グラフ上にfriendship chainが存在するか判定せよ。ただしfriendship chainとは、異なる点A, B, C, D, Eに対し、AとB, BとC, CとD, DとEがそれぞれ隣接するようなグラフのことである…

SRM683 Div.1 Easy MoveStones

前回のするめでめでたくDiv.1に上がれたので、今日からDiv.1Easyの問題を解いています。 次回何とか1完できることを目指して。 問題 https://community.topcoder.com/stat?c=problem_statement&pm=14174 石が縦に積まれたn個の山が、円状に隣り合って並んで…

yukicoder No.346 チワワ数え上げ問題(★2) 解説

yukicoderで出題していただいた問題の解説です。 問題 No.346 チワワ数え上げ問題 - yukicoder 与えられる文字列 の部分列(連続でなくともかまわない)のうち、"cww" となるものの総数を求めてください。 制約 解説 計算量を落とす過程に沿って説明していきま…

yukicoder No.345 最小チワワ問題(★1) 解説

yukicoderで初めて作問させていただいたので、その問題の解説です。 解説にはC++, Pythonのサンプルコードをつけてあります。 質問等あればコメント欄か @yurahuna まで。 問題 No.345 最小チワワ問題 - yukicoder 与えられる文字列の連続した部分文字列のう…

ABC016 D - 一刀両断

他のブログを見て「なんで交差判定"2回"してるの??」と思った人用の記事。 問題 abc016.contest.atcoder.jp 多角形と、線分が与えられる。線分により、多角形はいくつの領域に分断されるか。 解法 公式の解答を見ると、(求める数) = (線分と交差する辺の数…

ABC025 C - 双子と○×ゲーム

解くのに3時間かかりました(弱い) 問題 abc025.contest.atcoder.jp 3*3マスの盤に、先手と後手が順に○と×を埋めていく。盤面が埋まったら次のように得点を配分する。横に隣り合うマス、縦に隣り合うマスの計12組のペアにそれぞれ得点が設定されている。各ペ…

ABC022 C - Blue Bird

想定解と違うっぽかったので書いておきます。(ダイクストラで解いた) 問題 abc022.contest.atcoder.jp グラフが与えられるので、地点1から出発し地点1に戻ってくるような閉路が存在するとき、その最小の重みの和を求めよ。そのような閉路が存在しないとき…

ゆらふなセンパイお誕生日コンテスト C - パスカルの三角形

「やられた!」と思った問題。こんなんがCODE FESTIVALの決勝でも出るんだなあ…。 問題 yurahuna2016.contest.atcoder.jp 元問題はこちら code-festival-2014-final-open.contest.atcoder.jp 与えられる整数Aがパスカルの三角形に含まれるなら、その段数・行…

ゆらふなセンパイお誕生日コンテスト B - 儀式

さてB問題。これが一番時間かかった。 問題 yurahuna2016.contest.atcoder.jp 元問題はこちら code-thanks-festival-2014-a-open.contest.atcoder.jp 石像が南北方向にR行, 東西方向にC列並んでいる。最初はすべて南を向いている。左上を(1, 1)とする。 儀式…

ゆらふなセンパイお誕生日コンテスト A - 埋め立て

2月14日――世間では「バレンタインデー」と呼ばれ、恋に焦がれる者たちがチョコを渡しあう今日この日――私は22歳の誕生日を迎えながら実家で一人卒論を書いていました。 バレンタインらしいことも誕生日らしいことも特になく、しかも誕生日翌日が卒論提出日と…

ARC009 B - おとぎの国の高橋君

「なるほど!」と思った問題。わかってしまえば簡単かも。 問題 arc009.contest.atcoder.jp 0~9の数字の、新しい大小関係が与えられる。この大小関係に沿って、与えられるN個の数を昇順にソートせよ。 解法 初めてこの問題を見たときは「比較関数を作って、…

ARC025 B - チョコレート

バレンタインということで(?) 問題 arc025.contest.atcoder.jp 縦Hマス、横Wマスのチョコレートがある。各マスはブラックチョコかホワイトチョコであり、これらは市松模様に並んでいる。 各マスについて、チョコの濃度が与えられている。このチョコレート…

【競プロのための正規表現】のためのメモ

この記事は「競プロのための正規表現」と題し、競プロに頻出の文字列の問題を正規表現でさくっと解けるようになろう!という目的のために書かれた記事、を、いつか書くためのメモです。 実際のコードも載せているので、「正規表現ってなんですか><」「競プ…

【競プロ整数ライブラリ】蟻本 2-6章 まとめ

蟻本2-6章を読んで素数・約数系のライブラリ的なものができたのでまとめておきます。説明は全部蟻本にあるぞい。 【なかみ】 gcd(a, b): aとbの最大公約数 lcm(a, b): aとbの最小公倍数 extgcd(a, b, &x, &y): ax + by = gcd(a,b) の解(x,y)を得る(拡張ユー…

【グラフアルゴリズムとその例題】蟻本 2-5章 まとめ

蟻本 2-5章 のまとめです。各グラフアルゴリズムの概要と例題について。例題は一応ソースコードもつけておきます。 アルゴリズム 最短路問題 ベルマンフォード法 単一始点から他の各点への最短路を求める。負の長さの辺があってもOK。負閉路を持たない場合は…

Codeforces Round #342 (Div. 2) に参加しました

結果 A問題 無限に落ちて 悲しいな (575) 3完が目標だったので残念。というか今回A問題が一番難しかった!(手をつけた問題の中では) Bも無駄にimos法使ってpretest通ったと思いきやsystem testで落とされたのでご愁傷さま。 レーティングは1469 -> 1431(-38)…

AtCoder Begineer Contest 032 C - 列

問題 C: 列 - AtCoder Beginner Contest 032 | AtCoder 長さ N の非負整数列 S=s1,s2,…,sN と整数 K があります。 あなたの仕事は、以下の条件を満たす S の 連続する 部分列のうち、最も長いものの長さを求めることです。部分列の長さは 1 以上の列でないと…

ダイクストラ法とその例題

ダイクストラ法とその例題についてまとめておきます。 例題はワーシャルフロイドのやつ使いまわしです(ダイクストラ向きのは二分探索とか絡んで難しいので……) ダイクストラ法とは? ダイクストラ法(Dijkstra's algorithm)は、グラフのある点から各点までの…