buyoh.hateblo.jp

残念な競技プログラミング参加者による学習記録

Alchemy Recipes に関連するアルゴリズム設計

錬金特化プレイはやったことないなぁ. 目的 The Elder Scrolls 5 Skyrim の Alchemy(錬金術システム) の素材データを使ってあれこれ問題を解く. 錬金術システムとは? 薬の調合です. 各錬金素材は4つの効能を持つ. 素材となる異なる種類のアイテムを2個…

stick xor 余談

作文に関する余談など.有用な解説についてはyukicoderの解説ページを参照してください.

マラソンマッチ問題メモ(国内)

日本語のマラソンマッチ問題集です 英語の問題集は探せばあると思います.

最小頂点被覆問題(minimum Vertex Cover)の近似アルゴリズムの実装(draft)

1年前に同様のタイトルで記事を書きましたが,書き直します. 最小頂点被覆問題? 辺集合E,頂点集合Vから成るグラフGが与えられる. 頂点集合S⊆Vを考える. 全ての辺e∈Eが,Sに含まれる頂点に接続している時,SはグラフGの頂点被覆と呼ぶ. 集合Sの大きさが…

変更履歴を保存するデータ構造に関するメモ(定義とか)

永続データ構造とは 永続データ構造 - Wikipedia 変更履歴(バージョン)を記録するデータ構造. 本記事について 永続データ構造の性質について取り上げたい.

AtCoder Petrozavodsk Contest 001 - D Forest

嘘解法かもしれないので程々に. 2つのコーナーケースを記事に載せたのでぜひ. 問題文 https://beta.atcoder.jp/contests/apc001/tasks/apc001_d 公式想定解法 考察すると次が分かる 各連結成分のうち,必ず使わなければならない頂点は 1 個 全て合わせて2(…

yukicoder No.629 グラフの中に眠る門松列

2018/02/24 表現を修正 writerしました 問題 https://yukicoder.me/problems/no/629 ざっくり説明:グラフと頂点に割り当てる数字が与えられる.門松パスは存在するか? 本記事の目的 グラフに含まれる,門松パスの個数を O(M) で求める. cielさんの提出コ…

最小頂点被覆の指数時間アルゴリズムの実装(その2,分岐限定法)

その2. 2018/05/19 : note : 後日アルゴリズム含め全て書き直す可能性があります. 最終目標 これをACする. code-thanks-festival-2017-open.contest.atcoder.jp 知識 最小頂点被覆問題? グラフG=(V,E)が与えられる. 頂点集合S⊆Vを考える. 全ての辺e∈E…

最小頂点被覆の指数時間アルゴリズムの実装(その1,半分全列挙)

2018/02/22 軽く更新. その1. 最終目標 これをACする. CODE THANKS FESTIVAL 2017 - G Mixture Drug code-thanks-festival-2017-open.contest.atcoder.jp 知識 最小頂点被覆問題ってなんぞ? グラフG=(V,E)が与えられる. 頂点集合S⊆Vを考える. 全ての辺…

AtCoder Grand Contest 002 - D Stamp Rally

勉強になるとTLで見かけたので 問題 agc002.contest.atcoder.jp キーワード 並列二分探索

平面 traveling salesman problem の厳密解を求める.

平面tspの分岐限定法のコードをなんとなく書いてみたけれども,全然早くならなかった. Traveling Salesman Problem (TSP) N個の都市と都市間の距離が与えられる.全ての都市をちょうど一度ずつ巡って始点に戻る順回路の中で移動距離が最小のものを出力する…

Kの重複を許す区間スケジューリング問題

2018/02/22 更新 文章を修正 区間スケジューリング問題 http://www.prefield.com/algorithm/misc/interval_scheduling.html から引用. 区間スケジューリングは次の問題である.仕事が n 個与えられる.各仕事 j には開始時刻 s[j] と終了時刻 f[j] が設定さ…

Kuin で 競技プログラミング(yukicoder No.4 おもりと天秤) の問題を解く

※解き方の解説はしません. Kuinとは? プログラミング言語「Kuin」 - Kuina-chan 「Kuin」は、簡単で高速な実用プログラミング言語です。 オブジェクト指向言語. 2D,3D描画を標準でサポート. 2017/9/17に完成版としてリリース. 割と前から存在している言…

AtCoder Regular Contest 028 - B 特別賞

別解法シリーズ.別解で通すのは楽しいよ. 問題 arc028.contest.atcoder.jp

AtCoder Regular Contest 044 - C ビーム

少しだけヒントを見てしまったが,面白かったので解説を書く. arc044.contest.atcoder.jp 概要 レーザを避けるために必要な最小移動距離を求めよ.

yukicoder No.550 夏休みの思い出(1)

想定解とは違うけれども大丈夫そうなので解説を書いてしまった. 問題概要 No.550 夏休みの思い出(1) - yukicoder 三次方程式を解け. 解は整数であることが分かっている. submission #192857 No.550 夏休みの思い出(1) - yukicoder

yukicoder No.545 ママの大事な二人の子供

問題はこちら. - No.545 ママの大事な二人の子供 - yukicoder コンテスト中に半分全列挙のアルゴリズムを調べ,書きなぐってAccept通したので,その考え方を書きます. 問題文 個のアイテムがある. 番目のアイテムをA君に渡すとA君はポイント喜ぶ. 番目の…

scheme / commonLispで解く競技プログラミング (1)

lispをもう少しだけ詳しくなりたかった. Lispってなに? とても古い言語 C言語と比べてとてもシンプルな言語. emacsLispとかで息してる言語. Lisp言語を選ぶメリット ないと思います. オレオレ言語を作りたいとき,Lispライクな言語設計にすると,とても…

yukicoder No.533 Mysterious Stairs

前日にtesterしました. 問題概要 基本解法 改良1 改良2 問題概要 No.533 Mysterious Stairs - yukicoder N段の階段がある. 1回の飛躍で1step,2step,3stepずつ登れる. 同じstep数を連続して使えない N段目に到達するパターン数を出力せよ. 基本解法 4つの…

多項式時間で計算できる最小頂点被覆問題(最小点カバー)について

※ 2017/12/11更新:指数時間アルゴリズムについて記述 ※ 2018/02/21更新:全体的に書き直し 最小頂点被覆問題ってなんぞ? 辺集合E,頂点集合Vから成るグラフGが与えられる. 頂点集合S⊆Vを考える. 全ての辺e∈Eが,Sに含まれる頂点に接続している時,Sはグ…

7か月GitHubのContributions埋めをしました

GitHubのプロフィールページの下の方にあるやつ 他の方がやっているのをブログで見て,自分もノリで始めていました.

Python3の勉強をyukicoderでやる

pythonは正直あまり好きな言語ではなかったのですが,numpyが魅力的すぎるため,競技プログラミングで少し勉強してみました. 大学の講義内容がさっと手元で動かせないんですよね.octaveは重すぎるし. 記事を書いている人の前提知識度 昔に少しだけ書いた…

4ACした(21ACする:その2)

次の未だ解いていない問題をターゲットに13AC(21-8)する. yukicoder☆2(コンテスト中を除く) yukicoder☆3,4 AtCoder ARC C(コンテスト中に解けなかったものだけカウント) AtCoder ARC D,E,F AtCoder AGC B,C,D codeforces 不問(A問題でもカウント.英語…

8ACしました(21ACする:その1)

次の未だ解いていない問題をターゲットに21ACする. yukicoder☆2(コンテスト中を除く) yukicoder☆3,4 AtCoder ARC C(コンテスト中を除く) AtCoder ARC D,E AtCoder AGC B,C,D codeforces 不問(A問題でもカウント.英語補正) codeIQ ☆3以上 問題名はリ…

yukicoder No.7 プライムナンバーゲーム / No.11 カードマッチ / No.43 野球の試合

yukicoder No.7 プライムナンバーゲーム / No.11 カードマッチ / No.43 野球の試合 の感想と,復習を兼ねて簡単な解説記事.

yukicoder No.476 No.477 No.478 No.479

No.476 No.478 No.479のwriter,No.477のtesterをしました. 人との繋がりがないのでtester集まりませんでした yukicoder contest 155 - yukicoder 解説はyukicoderの方を参照してください.本記事では問題に絡むネタを紹介します. もちろん,ネタバレを含…

No.459 C-VS for yukicoder

Advent Calendar Contest 2016の10日目の問題のwriterをしました. No.459 C-VS for yukicoder - yukicoder 問題文・想定解法はリンク先の通りです. 本記事ではフローを用いた別解について書きます.結局年明けになってしまった.

yukicoder ☆1埋め

8つほど埋めていなかったので,今日埋めました. http://yukicoder.me/problems/no/89 http://yukicoder.me/problems/no/146 http://yukicoder.me/problems/no/172 http://yukicoder.me/problems/no/188 http://yukicoder.me/problems/no/191 http://yukicod…

このブログについて

競技プログラミングsubmit記録としてブログ記事を上げていこうと思います. 既に多くの競プロer勢が分かりやすい解説記事をうpされているので・・・何書こう?