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

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

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方向に移動が可能な問題とかそういうやつに対応します。二次元配列で書いてもいいんですけど添え字演算子とか書く量増える上に 方向に対して番号付けできなかったりすると面倒なときがあるので便利な…

yukicoder 215 メモ 高速きたまさ法

間違ってるかもしれないけど解法の方針が分かった気がした。 実装している時間がないのでとりあえずメモまずM項間漸化式をで作成する。 これはEASY,MEDを解いてる人ならできてると思うので省略。 きたまさ法の説明は省略。 剰余環での畳み込み和をフーリエ変…

ARC #039

ARC

あまり更新をしている暇はないけれどB問題のもやもやが晴れたのでメモ。 D問題はまだ解いてないです。 コンテスト本番はCの実装が間に合わず200点 - A問題「A - B Probrem」 (http://arc039.contest.atcoder.jp/tasks/arc039_a)問題概要: 3桁(100以上999以下…

yukicoder 24/25/26

- 24 数当てゲーム 問題概要 0から9までの数字に一つだけあたりの数字があります。 4つの数字が与えられ,その中に当たりの数字が含まれていないならNO,含まれているならYESが与えられます。 これが複数回与えられ、答えが特定できるような入力が与えられるの…

yukicoder 21/22/23

- 21 平均の差 問題概要 N個の数字をK個のグループ(要素数が1以上)に分けます。 グループ内の数字の平均値が最大のものと最小のものの差が最大になるようにグループ分けをしたときの差を答えよという問題です。 解説 タイトル詐欺です。 平均を最大にする組…

yukicoder 18/19/20

- 18 うーさー暗号 問題概要 文字列の復号をします。 文字列の暗号方法がi文字目の文字をi回右にずらす(Aを2回ずらすとC,Zを1回ずらすとA)という変換をします。 暗号が与えられるので復号した文字列を出力してください。 解説 逆の操作をするだけです。 i回…

yukicoder 15/16/17

- 15 カタログショッピング 問題概要 合計金額と、各商品の金額が与えられます。 何を買ったのか答えてくださいという問題です。 解説 商品の金額が小さければDPの典型です。 DPで解きたいのですが商品の金額が大きすぎるためTLEになってしまいます。 商品数…

yukicoder 12/13/14

- 12 限定された素数 問題概要 ある整数の区間[L,R]を選んだとき、その区間に含まれる全ての素数の各桁に使われる数字(0~9)を調べる。 0~10の整数が与えられ、区間に含まれる全ての素数の桁にちょうどのみが使われる[L,R]のうち、最大のR-Lを求めよという問…

yukicoder 9/10/11

- 9 モンスターのレベル上げ 問題概要 モンスターのレベル上げをする。 手持ちのモンスターの一番弱いもの(レベルが一番低い、複数いるなら一番戦闘回数が少ない)を戦闘に参加させます。 敵モンスターが円上に並んでいて、どこから戦闘を始めてもいいとき、…

yukicoder 6/7/8

なんか素数扱う問題がやけに多い気がします。 - 6 使い物にならないハッシュ 問題概要 ある素数pの各桁の和をp'とします。p'が二桁以上ある場合はもう一度各桁の和をとりそれをp'とします。 p'が一桁になったとき,それをp'のハッシュ値とします。 K,Nを素数…

yukicoder 3/4/5

GWのうちに問題数を稼ぐ - 3 ビットすごろく 問題概要 10進数kを2進数に変換したとき,ビットが1になっている部分の個数をbit(k)とする。 頂点kからはk-bit(k),k+bit(k)に移動することができる。 1からNに移動するときの最短距離を求めてくださいという問題で…