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

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

AOJ1320 City Merger

AOJ

問題文 City Merger | Aizu Online Judge n個の文字列が与えられる. 全ての文字を連続部分文字列として持つような文字列のうち,最小の長さを求めよ. 解法 nが14以下なのでbitDPを疑います. まず初めに,どの文字列がどの文字列を完全に含有しているかの…

AOJ2442 ConvexCut

AOJ

間違えてこっちの問題を解いて満足していたけどマヨ子さんのブログを見て違うことに気が付いた 凸多角形の切断 | 計算幾何学 | Aizu Online Judge 問題文 ConvexCut | Aizu Online Judge 解法 点Pが多角形に存在するとします. 多角形を点Pを通る2つの直線で…

AOJ2157 Dial Lock

AOJ

計算量の解析がよくできないシリーズ 問題文 Dial Lock | Aizu Online Judgek桁10進のダイヤル錠がある. 最初の状態と最終状態が与えられたとき,ダイヤルを回す必要のある最小の操作回数を求めよという問題です. ただし,1回の操作では,連続した桁を同…

AOJ2176 For the Peace

AOJ

多分英文を読解するのに一番時間を費やしたと思います(真顔) 問題概要 問題文:For the Peace | Aizu Online Judge個の国がある. 各国はそれぞれ威力の異なるミサイルを順に作る予定である. 世界の均衡を保つため,いかなる瞬間においても各国がもつミサ…

AOJ2383 Rabbit Game Playing

AOJ

とある勉強会に参加したので,そこで解いた問題の解説を暫くやっていこうと思います. 問題概要 問題文:Rabbit Game Playing | Aizu Online JudgeN個のゲームがあります.各ゲームには以上以下の難易度がつけられている. N個のゲームを順に全てプレイしたい…

ICPC2016 国内予選参加記

3度目のICPC国内予選に参加してきました. 問題文はこちらhttp://icpcsec.storage.googleapis.com/icpc2016-domestic/problems/all_ja.htmlです.チームの詳細は http://icpc.logic.cs.tsukuba.ac.jp/team/279567に色々書いてあります. チーム名は「lovable…

凸関数(単峰関数)の極値の探索について

単峰関数の極値の探索についてです.あんまり数学的な記述はしたくない(プロに殺されかねない)ので,単峰関数の説明は省きます. 凸関数のような極値を一つだけもつお山の形をした関数です.競技プログラミングにおいて,こういった問題を解くときに使われ…

競技プログラミングにおけるstd::unordered_***

はい. タイトルの通り,unordered_set,unordered_mapについてです. これらはset,mapを平衡二分探索木ではなく,ハッシュと連結リストによって実装することにより平均アクセス速度を定数に抑えています.ただし,悪意のある入力を除いて,です.一部のプロ…

JAG夏合宿2015 2日目 ツインリバース

@sugim48さんがwriterの問題です. 未だに公式の解説が無いのですが,転倒数についての面白い知見が得られた問題だったので備忘録として解説を書こうと思います. 問題概要 要素数Nで,1,...,Nの順列が与えられる 整数)を選び,の区間をそれぞれ反転する と…

yukicoder 「No409 ダイエット」

作問しました.解説を書きます. 実はなんですけど4/9が誕生日なので問題番号が409でちょっと嬉しかったです. 問題文 http://yukicoder.me/no/409 解説 動的計画法をします. TLE解法その1(ストレス値をパラメータに組み込む) 愚直にのDPをしようとする…

Chokudai Contest01に参加した

マヨ子プロ(@mayoko_)とチームで参加しました. 実装のほとんどを任せてしまったので詳しくは以下のリンクへmayokoex.hatenablog.com 感想 貪欲法は最高だぜ. チームでMMするのは超楽しいので次回も数の暴力で殴りたい

DDPC2016 本選 参加記

2016年2月20日に行われたDISCO presents ディスカバリーチャンネル プログラミングコンテスト2016に参加してきました. 0日目 0日目というか前日. 準備をしようと考える.日帰りなのでそこまで準備がないことに気づきイカをして士気を高めるなどする. 起床-会…

定数倍を高速化するお話し

ただの経験則でベンチマークをしたわけではないが 結構重要だと思うのでメモ mapを使った座圧とsortを使った座圧 mapを使ったほうが実装は百倍楽です. しかし二分平衡探索木の挿入のlogが重いのか,結構遅い. 面倒だけど配列にぶち込んでstd::sortしてごにょ…

二分探索について

競技プログラミングにおいて,二分探索を使う機会はたくさんあると思います. そして二分探索の書き方には宗教,流派があって人それぞれ意見が異なるかと思います.整数範囲での二分探索ではwhileを使うやり方とforを使うやり方の二種類があると思います.ちなみ…

Code Thanks Festival 2015 Open Contest 参加記

こどふぇすは本選出場したので感謝祭はオープンコンテスト Welcome to CODE THANKS FESTIVAL 2015 オープンコンテスト - CODE THANKS FESTIVAL 2015 オープンコンテスト | AtCoder のはずだったのですがバイトのあとの昼寝で寝過ごしたので終了1時間後からコ…

ARC008 メモ

ARC

ただのメモです A: 10袋をいくつ買うかで全探索 AC B: 各アルファベットについて必要な個数,1キットで手に入る個数をカウントしておく. 必要なアルファベットがキットになければ-1,あるならば必要個数/キットの個数の切り上げの値の最大値が答え. AC C: 投げ…

yukicoder 「No265 数学のテスト」

http://yukicoder.me/problems/605ICPCの構文解析対策用に作ってみたもの. 先に注意点を述べておきます. 文字列の長さが以下なので以下でなければ許されない.(制約が甘くてでも通るらしい) 出力する整数は32bitで収まらない可能性がある. ある項において定数…

ACM-ICPC 2015 国内予選参加記

6/26に参加してきました.今年で2回目の出場です. 結果は4完,全体20位で大学内1位なので地区予選進出だと思います. 去年はチームメンバー違いますが0完だったのでとても嬉しい.以下チームメンバー略 自分:B3 N: B3 T: B4 本番前打ち合わせ A問題を自分が担当,…

ICPC2015 模擬国内予選 D問題 「アリスハウス」

実装&デバッグが間に合わなかったシリーズpart1 本番中は私が実装してました。 なお効率の悪い書き方をしていたため半分も書けずタイムオーバー。ゲーム理論が国内予選で出るとは思ってなかった。 問題内容としては後退解析をするだけの典型ともいえる(後退…

マス目を使う問題でのちょっとした実装テク

実装テク?H行W行のマス目があって 座標(i,j)から上下左右4方向に移動が可能な問題とかそういうやつに対応します。二次元配列で書いてもいいんですけど添え字演算子とか書く量増える上に 方向に対して番号付けできなかったりすると面倒なときがあるので便利な…