読者です 読者をやめる 読者になる 読者になる

ゆらのふなびと

競プロ, Python, C++

PyCPXで最短経路問題,最大流問題を解く

PyCPX Introduction — PyCpx -- Python Wrapper for CPlex Optimization Suite 0.01 documentation PyCPX は,整数計画問題のソルバーである CPLEX の,Python によるラッパー. 研究で使うことになったので練習. グラフの問題に使いたいので,最短経路問題…

RUPC2017 参加記

RUPC2017(立命館大学競技プログラミング合宿2017)の参加記です. atnd.org 昨年に引き続き 2 度目の参加.チーム戦ができる数少ないオンサイトということで楽しみにしていました. Day 1: 立命館&阪大セット この日は作問チームに参加していました. http:…

2017年の目標

今年が始まってもう13日目になりますが、2017年の目標を書いておきます。 レーティング AtCoder: 1996 -> オレンジ(2400) Codeforces: 1912 -> master(2200) TopCoder: 1331(highest) -> 黄色安定(1600) やること AOJ-ICPCを黄色まで埋める(国内予選までに) …

AOJ1330 Never Wait for Weights

とても面白いと思ったけど、帰着によってはそうでもないらしい? 問題 Never Wait for Weights | Aizu Online Judge N個のアイテムがある。M個のクエリが与えられる。クエリは次の2種類である。 ! a b w アイテムa, bの重さの差はwである(w_b - w_a = w) ? a…

DDCC2016に参加しました

「DISCO presents ディスカバリーチャンネル コードコンテスト 2016」参加記です。 japan.discovery.com 今回は割と注釈芸をしています*1 予選は3完75位で、18卒枠で通過しました。 会場まで 始発でぎりぎり間に合ってしまうことがわかったので、5:10に奈良…

競技プログラミングを始めて1年間でやったこと

この記事は Competitive Programming Advent Calendar 2016 3日目の記事として書かれました。 競技プログラミングを始めてちょうど1年くらいになるので、今までやってきたことをまとめてみようと思います。 これから競技プログラミングを始める人の参考や、…

CODE FESTIVAL 2016 に参加しました

予選 A 焼肉を食べていたので出なかった。 B 4完したが108分かかり落ちた。冷えた。 C 3完+部分点で通過! 夏合宿や会津合宿で「こどふぇすで会いましょう!」と言いまくっていたのが嘘にならなくてよかった。 1日目 集落を6時半に出発した。なんだかテンシ…

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 = (奇数桁目の和) - (…

KUPC2016京都オンサイトに参加しました

終了15分前にこの記事を書いています。 kupc2016.contest.atcoder.jp A - バリケード / A Barricade 区間に含まれないものがいくつあるかカウントする。 gist.github.com B - 作問委員会 / Problem Committee たくさんあるやつから使えばいいのかなーと思い…

会津合宿2016Day2 会津セット A~L 解いた

振り返り。(2016/9/22 とりあえずA-Gだけup。Lまでは解く予定) 問題: http://judge.u-aizu.ac.jp/onlinejudge/contest_problem.jsp?id=ACPC2016Day2 解説: (リンクに飛ぶと右側にばーっと出てくる) 0: 全体の講評 from Takumi Yamashita www.slideshare.net …

会津合宿2016Day1 立命セット A~E 解いた

振り返ります。(F, Gは解ける気がしないので勘弁……) 問題: http://judge.u-aizu.ac.jp/onlinejudge/contest_problem.jsp?id=ACPC2016Day1 解説: https://drive.google.com/drive/folders/0B5BaKBeHPaOoV0NWdEE0QXJfa28 A: キャベツ / Cabbage 数列上をポイン…

会津合宿2016Day3 北大セット 解いた

一通り解いたので、各問題を振り返ってみたいと思います。 オンサイトで自分が解いたのはBだけ。(あとはみんなでGを考えていた) 問題: http://judge.u-aizu.ac.jp/onlinejudge/contest_problem.jsp?id=ACPC2016Day3 解説: (コンテスト翌日に上がっていて仕事…

会津大学競技プログラミング合宿2016 参加記

経緯 もともと行く予定ではなかったが、JAG夏合宿に参加したら会津にも行きたくなってしまった。なので行った。 0日目 マヨマヨと巡る東京ツアーに参加してきました pic.twitter.com/X0EfIYzq9h— ゆらふな (@yurahuna) September 16, 2016 ここのラーメンが…

【メモ】Ford-Fulkerson法、Dinic法について

フローのアルゴリズム2種類を勉強したので、メモです。 ろくに問題を解かず蟻本を写経しただけの段階で書いているので、記述が無辺世界にふっとんでいる可能性があります。 Ford-Fulkerson法 残余ネットワーク上の増加路をDFSで検出し、そこに流せるだけ流す…

JAG夏合宿Day4 F. Find the Length

本番マヨバタが話していたことを思い出しつつAC。 問題 $n$ 頂点の連結な重み付き無向グラフが与えられる。各頂点 $v$ について、$v$ を含む単純閉路長の最小値を求めよ。 制約 $1 \leq n \leq 300$ 各辺の重みは隣接行列形式で与えられる 辺の重み: $1 \leq…

JAG夏合宿2016 参加記

JAG夏合宿2016に参加してきました。 僕は今年はICPCに出ていませんでしたが、来年出たいということで合宿に参加させてもらいました。 1日目 来たぜ pic.twitter.com/6tPRzGJqYl— ゆらふな (@yurahuna) September 1, 2016 夜行バスで6時に現地入り。15時の集…

ARC060 D - 桁和 / Digit Sum

最高のコード(当社比)を作った。 gist.github.com

ブログに「上に戻る」ボタンをつけた

以下のものを参考にした。 jQueryで作る先頭へのジャンプ機能 (全4回) - プログラミングならドットインストール はてなブログにTOPに戻るボタンを追加する方法 - TASK NOTES Font Awesomeを使うと画像をサーバー上に保存する必要がなくて便利。

D3.jsのチュートリアルをやった

↓これ。 ja.d3js.info versionが異なっていたので一部書き換えないと動かなかった。 以下は4.2.1に対応させた散布図のコード。 gist.github.com

JavaScriptの練習に○×ゲーム的なものを作った

↓こういうものを作りました。 ○× Time Attack ベースは○×ゲームで、10秒間で何回AI*1に勝てるかを競うゲームです。 JavaScriptを始めて4日ですが一応動くものを作ることができたので、制作の記録をまとめておきたいと思います。 背景 プログラミングというと…

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番目の人に戻る。 最後のマスを埋めた人の負けである。 それぞれの人が自分が負けないように行動…