競技プログラミングをするんだよ

ICPC国内予選突破を目標に一日一問題以上解いていきます。

segment_tree

#include<bits/stdc++.h> using namespace std; typedef long long LL; const LL INF=1e16; typedef LL A; typedef LL B; typedef LL C; struct node{ A a; int flag; B b; C c; }; #define isB (1<<0) #define isC (1<<1) A mg(node& v,int l,int r){ if(v.flag&isB)return</bits/stdc++.h>…

AOJ2594 Reverse a Road Ⅱ

AOJ

この問題好き 問題文 Reverse a Road II | Aizu Online Judge久々に訳書きます 有向辺グラフとスタート,ゴールが与えられる. スタートからゴールまで,道が一つも被らないルートが最大でいくつあるか求めたい(頂点は被ってもよい) ただし,一つの辺だけ…

JAG夏合宿 2016 day4

夏合宿の4日目のアレです. この日はKlab様に会場提供していただき,六本木ヒルズの中でコンテストに参加するという貴重な体験をさせていただきました.六本木ヒルズで綺麗な恰好のOLやキチっとしたサラリーマンの集団の中に大人数の競技プログラマーが突っ…

JAG夏合宿 2016 day3

夏合宿の3日目のコンテストの時のアレです. この日は模擬予選も兼ねていて,LINE様に提供していただいた会場でコンテストを行いました. 色々オフィスがすごかった.(こなみかん)まよバタ+紺青さん(@konjo_p)の即席チームで参加しました. 実は紺青さんと…

JAG夏合宿 2016 day2

夏合宿2日目のコンテストのときの日記的なアレですJapan Alumni Group Summer Camp 2016 Day 2 - Japan Alumni Group Summer Camp 2016 Day 2 | AtCoder解説のときに聞いた話なのですが,このセットは欧州の結構やばい地区の過去問らしいです.まよバター(@b…

JAG夏合宿2016 参加記

JAGの夏合宿に参加してきました!今回は何故かICPCのチームメイトが参加できずぼっち参加になってしまったので,マヨ子プロにコンテスト一緒に参加する約束をして寄生する. 1日目 所用があって自己紹介フェーズには参加できなかったので懇親会から参加する…

memo

(custom-set-variables ;; custom-set-variables was added by Custom. ;; If you edit it by hand, you could mess it up, so be careful. ;; Your init file should contain only one such instance. ;; If there is more than one, they won't work right…

AOJ2638 Hyperrectangle

AOJ

考察に3時間ぐらいかかった気がするのでコンテスト中に解けなさそう... 問題文 Hyperrectangle | Aizu Online Judge 解法 まず,全てのについての場合について考えると,2次元なら長さsの正三角形,3次元なら正三角錐,,,d次元の正三角錐(三角錐かどう…

AOJ2312 魔法少女さやかちゃん

AOJ

多分勉強会の問題の中で開いてから解くまでが最速だった.(これは罠で,日本語の問題だからという説がある 問題文 Magical Girl Sayaka-chan | Aizu Online Judge 解法 輪というのが考えにくいのでなんとか区間というか数を一列に並べる問題にならないか考…

AOJ2538 Stack Maze

AOJ

勉強会の問題がICPCっぽく(悪い意味で)なってまいりました. 問題文 Stack Maze | Aizu Online Judge 日本語訳が欲しい方は「mayoko stack maze」とかで検索するとよいです. 解法 最初に思いつくのはdp(r,c,今持っている宝石のスタック)というDPだと思い…

AOJ2296 Quest of Merchant

AOJ

頑張るだけ 問題文 Quest of Merchant | Aizu Online Judge 解法 色々眺めていくとナップサック以外考えられなくなると思うのでナップサックで考える. まず初めの考察として,原点から出発して再び原点に返ってくる操作を1セットとできそう.では1セットに…

AOJ2224 Save your cats

AOJ

薔薇園の魔女に比べたら11454倍楽 問題文 Save your cats | Aizu Online Judge 解法 閉路を含まなくするためにできるだけ少ない長さの辺を削りたい. すなわち,できるだけ辺の総和が長くなるように閉路を含まないグラフを作りたい よって最大全域森を作れば…

AOJ2310 薔薇園の魔女

AOJ

二度と解きたくない 問題文 Rose Garden Witch | Aizu Online Judge 解法 全探索をします. といっても直線を引く候補が無限個あるので,少し考察をします.最適解の直線があったとして,分割する数を減らさないように少しずつ直線の角度をずらしていくと,…

AOJ2168 Luigi's Tavern

AOJ

マッチングかー,フローっぽいなあ,どう見てもフローじゃん みたいな感じだった 問題文 Luigi's Tavern | Aizu Online Judge 解法 パーティーを沢山作りたいので,各パーティーに役職はそれぞれ高々一人でいいことが分かります. それで,人を頂点,友好関…

AOJ2305 Beautiful Currency

AOJ

Beautifulのスペルが覚えられないのは私だけじゃないはず. 問題文 Beautiful Currency | Aizu Online Judge訳は載せませんが,美しい通貨群にするために必要な各々の変動レートの"最大値"を求める問題です. 総和と勘違いしてサンプルが合わず丸一日悩みま…

AOJ2326 Number Sorting

AOJ

問題文 Number Sorting | Aizu Online Judge 解法 制約を見ると, という怪しい制約があるので,とします. まずこの時点で想定解法はかとかその辺を疑います.(桁DPの可能性もありますがこの制約である必要があまりなさそうなので切り捨てました.)小さい…

AOJ1302 Twenty Questions

AOJ

SRM694Div1Med「Distinguishable」に似ていたので誤読をした(というより同じ問題だと思ってしまった.) 問題文 Twenty Questions | Aizu Online Judge 例によって日本語訳はないです. 解法 どんなオブジェクトも与えられた質問によって一つに特定できるこ…

AOJ1330 Never Wait for Weights

AOJ

問題文 Never Wait for Weights | Aizu Online Judge 日本語訳は他の方のブログ見てください 解法 !を頂点の連結クエリ,?を連結成分内のrankの差を取得するクエリとしてみてみましょう. Union-Findしたい気持ちになってくると思います. Union-Findについ…

AOJ2333 僕の友達は小さい

AOJ

問題文がなかなかキチってて好き 問題文 My friends are small | Aizu Online Judge 解法 ナップサックで解けそうな気がしてくるので,DPで考えてみます. すると,(選んだ友人の高さの合計)が選んでない人の高さの最小値未満なら条件を満たすことが分かると…

AOJ2222 Alien's Counting

AOJ

最近出次数1のグラフ問題やりすぎて慣れてしまった 問題文 Alien's Counting | Aizu Online Judge 解法 出次数が高々1という制約があるので TopCoderのSunny Graphと同じように考えると,一つの連結成分は1つの単純閉路といくつかのパスを繋げたような形にな…

AOJ2200 Mr. Rito Post Office

AOJ

ICPC国内予選の過去問ですね 実は去年解いた記憶があります(まあ去年は青コーダーでしたし激遅だったのでいい復習になりました 10分で解きたい問題 問題文 Mr. Rito Post Office | Aizu Online Judge 解法 あらかじめ,陸路のみ,海路のみの全頂点間最短路…

AOJ2306 Rabbit Party

AOJ

問題文 Rabbit Party | Aizu Online Judge 解法 全然関係ない話をすると,グループに含まれる頂点集合からなる完全グラフのMSTのスコアがそのままそのグループのスコアになる(本当に関係ない)グループが既にあったとして,そのグループに一人追加すること…

AOJ1132 Circle and Points

AOJ

問題文 Circle and Points | Aizu Online Judge 解法 ある点群を囲っている単位円について考えると,円から点がはみださないように円を動かしたとき,やがて円と2点がぶつかる. このことから,いずれか2点がギリギリ円に含まれている全状態を考えれば漏れな…

AOJ2425 全探索お姉さんの休日

AOJ

問題文 A Holiday of Miss Brute Force | Aizu Online Judge 解法 (x,y,t)の3状態からコスト0とコスト1の辺をもってダイクストラするだけ ただし,tは[tex:mod 6}で考えないと色々計算量が大変なことになるので注意注意点としては,x座標の偶奇で座標の遷移…

AOJ2441 FizzBuzz

AOJ

問題文 FizzBuzz | Aizu Online Judge 解法 コードを見ながら必死に解法を思い出しているのですが, まあ制約的に二分探索だとおもいます. 下の桁から丁寧に数え上げてやるとある数までにいくつ文字を出力したかがで求められるので,境界を求めてやってあと…

AOJ2382 King Slime

AOJ

問題文 King Slime | Aizu Online Judge 日本語訳は略 解法 個の頂点があったときに,それを1点に集合させるまでに必要な移動回数の下界は回でとなる. これは,各頂点からの移動を辺で表せば木となることから明らかである.というわけで,木を構成する方法…

AOJ2170 Marked Ancestor

AOJ

問題文 Marked Ancestor | Aizu Online Judge 日本語訳は他に書いてる人が沢山いるのでそちらをご参照ください 解法 便宜上,祖先を取得するクエリをQ,頂点をマークするクエリをMと略します.頂点に対するクエリQが飛んできたとき,何を求められればいいかを…

ローカル環境(win+msys)でのスタック拡張のおまじない

メモです再帰関数の呼び出しがかなり深いとこにいくときなど @btk15049 ulimit -s 20480とかはどうですか— nyashiki (@sizensuN) 2016年7月8日埋め込み機能便利

AOJ2182 Eleven Lover

AOJ

2進数における3の倍数の求め方と同じですよねこれ 問題文 Eleven Lover | Aizu Online Judge 80000文字以下の数字のみからなる文字列が与えられる. 連続した部分文字列について,10進の数字として先頭が0でないかつ11の倍数であるようなものの個数を求めよ…

AOJ2317 Class Representative Witch

AOJ

問題文,闇に包まれすぎ 問題文 Class Representative Witch | Aizu Online Judge 英語よりも辛いと思いますが問題文についての説明はしません() 解法 が成り立つとき,区間をとすると,値の小さいほうが使い魔の持つ端点として統一でき,魔女の座標は0に…