ゆらのふなびと

競プロ, Python, C++

ICFPC2016に参加しました

だいたいのことは@shora_kujira16さんが↓に書いてくれたので、この記事では時系列に沿ってやったことを振り返ってみたいと思います。 kujira16.hateblo.jp 主にソルバー担当でした。 ~0日目 @Yazaten さんが声をかけてくれたのでノった。ICFPCのことはあまり…

Codeforces Round #364 div2D. As Fast As Possible

二分探索の良い練習問題っぽい。 問題 $n$ 人の生徒と1台のバスが、時刻0において位置0にいる。生徒たちは位置 $L$ にある目的地にたどり着きたい。生徒たちは速度 $v_1$, バスは速度 $v_2$ で移動する。バスは1度に $k$ 人まで同時に乗ることができるが、同…

二重辺連結成分分解 ライブラリ

二重辺連結成分分解のライブラリと、アルゴリズムの概説です。 この記事ではimos法を使った方法でやっています(恐らくこっちの方が初学者にはわかりやすい)。

天下一2015予選A D - ハシポン

1週間かけてAC。 問題 D: ハシポン - 天下一プログラマーコンテスト2015予選A | AtCoder 連結な単純無向グラフ が与えられる。 にいくつかの辺を加えた が橋をちょうど1つ持つ連結な単純無向グラフとなるには、最小何本の辺を追加すればよいか? 不可能な場…

yukicoder No.197 手品

落ちてたので再挑戦。 問題 No.197 手品 - yukicoder 解法 慎重に場合分けをしていきます。ただし、nは操作回数、s, t はそれぞれ操作前、操作後の文字列とします。 s, tでoの個数が異なればありえない (以下、s, tのoの個数は等しい。もしoがxより多ければ…

(メモ) 木の中心と直径について

証明を書いていたら迷子になってしまった— ゆらふな (@yurahuna) 2016年7月18日 なのでツイートだけ貼り付けておきます。ごめんね。 参考にしたpdf: http://www.cs.columbia.edu/~cs4203/files/GT-Lec4.pdf 【中心がただ1つ or 隣接する2頂点 になることの略…

AGC001 C - Shorten Diameter

現時点で正しいと思う理解の仕方を書いたので、間違いや気になるところがあればぜひ教えてください。 問題 C: Shorten Diameter - AtCoder Grand Contest 001 | AtCoder 頂点の木がある。この木の直径を 以下にするために削除する必要のある最小の頂点数を求…

強連結成分分解 ライブラリ

強連結成分分解のライブラリ。 今のところsame(2つの頂点が同じ強連結成分に属するか)しかつけてないけど、いろいろ拡張すると便利そう。 gist.github.com

AGC001 B - Mysterious Light

問題タイトルが英語で、世界を感じた。 問題 B: Mysterious Light - AtCoder Grand Contest 001 | AtCoder (問題文の図を参照) ざっくり言うと、正三角形の中で光を反射させたとき、最初の点に戻ってくるまでの軌跡の長さを求めよ、という問題。ただし光は正…

yukicoder No.399 動的な領主

"木上のimos法"というテク。 問題 No.399 動的な領主 - yukicoder N頂点の無向木がある。Q人の人が u_i から v_i へ最短経路で移動する。人が頂点を通過するとき、(自分より前にその頂点を通った人の人数) + 1 のコストがかかる。Q人の移動コストの総和を求…

yukicoder No.398 ハーフパイプ(2)

なんとか時間内に通せてよかった。 問題 No.398 ハーフパイプ(2) - yukicoder 6人の審査員がいる。審査員は1人ごとに、0点以上から100点以下の整数の得点を提示する。提示された6つの得点のうち、最大値と最小値を除いた4人分の平均はXであった。このような6…

NAIST受験記(情報科学研究科 2016年度 秋入学第2回)

受験記です。 僕が受験したのは秋入学の回ですが、特に秋入学だからと言って変わるところはないようです。 以下の受験記もオススメです。 kujira16.hateblo.jp 準備編 小論文 研究室見学に伺った際に聞いたお話が面白かったので、テーマはそれを元に考えまし…

ARC057 B - 高橋君ゲーム

難しかった。 問題 B: 高橋君ゲーム - AtCoder Regular Contest 057 | AtCoder 高橋君はN日間ゲームを行う。i日目にはa_i回のゲームをする。ゲームの結果は勝つか負けるかのどちらかである。 高橋君のi日目の機嫌は勝率によって決まる。i-1日目までの勝率よ…

yukicoder No.393 2本の竹

学び。 問題 竹が2本ある。長さはそれぞれ である。 人の客がいる。 番目の客は長さがちょうど の竹が欲しいと言っている。 あなたは2本の竹のいずれかから一部を切り出すことで客の注文に応えることができる。ただし異なる竹から切り出した部分どうしをつな…

yukicoder No.391 CODING WAR

問題 人の人と 個の問題がある。次の制約をすべて満たす、人→問題の割り当て方の数を で求めよ。 1人はただ1つの問題に取り組む すべての問題について、取り組む人が1人以上いる 制約 解法 前提として、人は区別されるということに注意(これをわかっていなく…

yukicoder No.390 最長の数列

問題 N個の正の整数からなる集合 S = {x_1, x_2, ..., x_N} がある。 SからM個の要素を選んで適切に並び替えた数列を (a_1, a_2, ..., a_M) とするとき、aが単調増加かつ隣り合うすべての要素に対してa_iがa_i+1の約数となるような数列を「良い」数列と呼ぶ…

yukicoder No.389 ロジックパズルの組み合わせ

問題 M個のマスが1直線状に並んでいる。K個のヒントがあり、k番目のヒントは連続するH_k個のマスを塗れというものである。ただし異なるヒントによって塗られるマスどうしは隣接してはならない。このような塗り方は何通りあるか。mod 109 + 7 で答えよ。ただ…

ARC056 B - 駐車場

問題 N 人の人が 1 番目から順に駐車場にやってくる。駐車場は N 個の駐車スペースが無向辺で結ばれたグラフで表され、入り口は頂点 S である。i 番目の人は i 番目の駐車スペースに車を停めるか、停められないならば停めずに帰る。 駐車できる人の番号をす…

ABC041 D - 徒競走

問題 N匹のうさぎ(1..N)が徒競走をした。 M人の観客から、x_iはy_iより先にゴールしたという情報がわかっている。 同着はいないとするとき、着順は何通り考えられるか? 制約 2 <= N <= 16 1 <= M <= N(N - 1) / 2 解法 着順は最大で N! 通りある。いくら制…

LCA ライブラリ

クラスにしたのでとりあえず。 日本語コメント保存用 Verify: Lowest Common Ancestor | Aizu Online Judge #include <bits/stdc++.h> using namespace std; #define int long long // <-----!!!!!!!!!!!!!!!!!!! #define rep(i,n) for (int i=0;i<(n);i++) #define rep2(i,</bits/stdc++.h>…

yukicoder No.386 貪欲な領主

問題 N頂点の無向木で表される国がある。各頂点を通るには1人当たり税金Uiがかかる。 今からQ個のクエリが与えられる。i番目のクエリは頂点Aiから頂点BiにCi人が移動することを表す。 この国で支払われる税金の合計額を求めよ。 制約 2 <= N <= 100000 0 < U…

yukicoder No.385 カップ麺生活

問題 M円の所持金がある。 N種類のカップ麺がある。i番目のカップ麺はCi円である。カップ麺は好きなものを好きなだけ購入できる。 カップ麺を購入したとき、もし残り所持金が素数となれば所持金をM円に戻すことができる(これを"金欠チャンス"と呼ぶ)。ただし…

yukicoder No.384 マス埋めゲーム2

問題 H行W列のマス目がある。 1番目からN番目までの人が順番に、空いているマスのある1行or1列を選び、その行or列のすべてのマスを埋める。N番目まで回ったら1番目の人に戻る。 最後のマスを埋めた人の負けである。 それぞれの人が自分が負けないように行動…

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