ゆらのふなびと

競プロ, Python, C++

競プロ

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

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.345 最小チワワ問題(★1) 解説

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

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

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

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に戻ってくるような閉路が存在するとき、その最小の重みの和を求めよ。そのような閉路が存在しないとき…

ゆらふなセンパイお誕生日コンテスト 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)は、グラフのある点から各点までの…

ワーシャルフロイド法とその例題

ワーシャルフロイド法のアルゴリズムと例題についてまとめておきます。師匠へのレポートもかねて。 ワーシャルフロイド法とは? ワーシャルフロイド法(Warshall–Floyd Algorithm)とは、グラフの全点間の最短距離を求めるアルゴリズムです。簡単な3重ループを…

Union-Find木の参考になるサイトと例題

Union-Find木を勉強するために使ったサイトと例題をまとめておきます。 「Union-Find木って何?」「とりあえずUnion-Find木を使えるようになりたい!」という人向けです。 Union-Find木とは? Union-Find木はグループ分けを管理するデータ構造です。各グルー…

Codeforces Round #338 (Div. 2) B - Longtail Hedgehog

過去問再挑戦キャンペーン実施中。 問題 1からnまでの番号がつけられた点とm個の辺からなるグラフがある。重複辺・自己辺はない。 このグラフのいくつかの辺に色を塗ることでハリネズミを作る。ハリネズミは「尾」と「背骨」からなる。これらは以下のように…

Codeforces Round #341 (Div. 2) C - Wet Shark and Flowers

これはね……数学の問題。 問題 n体のサメが丸い机の周りに座っている。i番目のサメと(i+1)%N番目のサメは隣りあっているものとする。 サメiは数s_iを閉区間[l_i, r_i]に含まれる整数から等確率で選ぶ。任意の隣りあうサメi, jに対し、s_i * s_jがpで割り切れ…

Codeforces Round #341 (Div. 2) B - Wet Shark and Bishops

問題 1000*1000の正方形のチェス盤がある。この上にn個のビショップを置く。 ある2つのビショップについて、それらが同じ対角線上にあるとき、ビショップは「互いを攻撃している」と言う(AとBの間に他のビショップCがあっても、AとBが同じ対角線上にあれば「…

ARC043 B - 難易度 (作成中)

記事書こうと思ったんですけど,やっぱりわかってないということがわかったので記録だけ残しておきます. 問題 個の正の整数 から, を満たすような4つの要素を選ぶ方法は何通りか. で割った余りを求めよ. 制約 解法 ここでは公式の解説とは異なる方法を採…

SRM680 Div2 Med(500) BearChairs

問題 I guess you have never seen a bear eating at a table. The reason is simple: bears don't use tables. However, they may sometimes decide to sit on a chair while eating. Bear Limak is a waiter in a huge restaurant for bears. The restaura…

ARC042 B - 最短路問題

いきなり公式の解説を読んでもわからなかったので,具体例による考え方を書いておく. あとはPythonのpowの使い方. 問題 同じ頂点の間を結ぶ辺が複数存在せず、またすべての辺の2端点の頂点が異なるグラフの頂点を順に1,2,…,Nとして、任意のiに対し、頂点1…

ARC042 A - 掲示板

A問題やけど解けんかった! ということでメモ。 問題 1 から N までの番号がついたスレッドのある掲示板があります。 スレッドは書き込みがあると一番上に来ます。 書き込み前のスレッドは上から順に 1 から N の順に並んでいました。 M 個の書き込みが書き…

AOJ ALDS1_1_D Maximum Profit

効率化していく過程がなるほどなーと思ったのでメモ。 AOJ > コース > Algorithms and Data Structures I > Getting Started > "Maximum Profit" ←イマココ 問題 自然数列Rに対して、R_j - R_i ( j > i ) の最大値を求めよ。 解法 部分点解法 愚直に求めるな…

複素数をつかって三角形の外心を求める

「幾何の問題は複素数を使うと実装が軽くなるよ!」という噂を聞いたのでPythonでやってみた。 今回使うのはこちらの問題↓↓ Circumscribed Circle of a Triangle | Aizu Online Judge 三角形の頂点の座標が与えられるので、外接円の中心と半径を答えよという…

square869120Contest #1 D - square1001の通学経路 (square1001's School Road)

問題 D: square1001の通学経路 (square1001's School Road) - square869120Contest #1 | AtCoder 左下が(1, 1), 右上が(W, H)の格子状の地図がある。 条件「K個のマス(左下が(Xi, Yi))のそれぞれについて、その周囲の4点のうち少なくとも1つを通る」を満たす…

square869120Contest #1 C - お金の街 (The Money Town)

問題 C: お金の街 (The Money Town) - square869120Contest #1 | AtCoder 街i(i = 1..n)にDi円落ちている。同じ街を2度通らないように進むとき、拾えるお金の最大値はいくらか、という問題。 解法 DFS。お金の最大値は逆順に求まる(コード参照)。 def dfs(i)…

square869120Contest #1 A - E869120列車 (E869120 Trains)

AtCoderにて行われた、中1の双子さんによるコンテスト。 Dまで解けたので解答置いておきます(本番はBまでしか解けなかった) 問題 A地点に電車が1回目に通ったのは5時ちょうどで, 最後に通ったのは23時ちょうどだった。 電車はA地点をN回, K分ごとに通過し…

ARC045 B - ドキドキデート大作戦高橋君

いもす法の問題を初めて解いたのでメモ。 問題 B: ドキドキデート大作戦高橋君 - AtCoder Regular Contest 045 | AtCoder 1からNまでの整数列(教室の番号を表す)に対し、M個の閉区間[s,t]が与えられる。 このとき、2つ以上の閉区間に含まれる区間をすべて出…

ABC009 C - 辞書式順序ふたたび

「いつものC問題より難しい」との注釈通り、わかりにくい問題だった。 問題 C: 辞書式順序ふたたび - AtCoder Beginner Contest 009 | AtCoder 長さNの文字列Sが与えられるので、元から位置の変わった文字の個数が K 以下であるような文字列のうち、辞書順最…