ctyl's problem solving

競技プログラミングが主な話題です。

AGC012 C Tautonym Puzzle

問題 agc012.contest.atcoder.jp 概要 aaはaを2回、bubobuboはbuboを2回繰り返している。このように長さ1以上の文字列を2回繰り返しているものは良い文字列と定義する。入力 が与えられるので、良い文字列である部分列の個数がである長さ200以下の文字列の1…

yukicoder No.441, 442, 443 コメンタリー (解説なし)

初めてyukicoder contestのwriterをやりました。100人ほど参加してくださって、いろいろwriterとして得られるものがあったので書き残しておきます。解説はそれぞれの問題の解説タブに書いてあるので、ここでは解説や提出コードは書きません。 コンテストのリ…

AGC003 D Anticube

概ね解説と方法は同じですが、自分の方法は少しアプローチが違うので書くことにしました。 問題 agc003.contest.atcoder.jp 概要 正の整数列があたえられる。この中から出来る限り多くの整数を選んで、どの2つの要素の積も立方数にならないようにしたい。最…

ICFPC 2016 参加レポート

kenkooooさん,roitiさん、わいんさんとICFPCにチーム"COBOL Lovers"で参加していました。 全員非学生なので金曜は問題を読む日にして、土日に集まって問題を解いていました。会場を提供してくださったkenkooooさん及び同居人の方に感謝します。 問題概要 ICF…

JAG Contest 2016 Domestic 参加記 (C, Eレビュー)

kenkooooさん、roitiさんとチームshinsotsuで参加。会場を提供してくださったroitiさんに感謝いたします。 結果:CとEを担当して総合15位。Eはroitiさんの考えた解法を自分が実装した形になり、チーム戦っぽいことができてよかったです。幾何は基本的なライ…

yukicoder No.348 カゴメカゴメ

★4昇格.Union-find,木DP,DFSなど色々な要素が入っている問題でためになるのだけれど,実装がかなり難関.個人的には今までyukicoderの問題の中で最凶クラスの実装難の問題でした. 方針:輪の包含関係を根付き木で表現する.Union-findなどで各輪の強さを…

yukicoder No.209 Longest Mountain Subsequence

DP★3.3ヶ月位前にも一度挑戦していて,その時は自分の方針のアラが探せず出来ずじまいだったが,今回は一発でACできた. 方針:を満たす最長の上昇部分列の長さを今選んでいる要素のindex,直前に選んだ要素のindexの情報を持った上で求める.下はのときの…

Codeforces AIM Tech Round Div.2 C Graph and String

本番はSCCに固執しすぎて実装が間に合わず.その後冷静に考えたらもっと単純な方法があった. 解法 まず気づきそうなこと:実線は辺,点線はそうでないとする.次のようなグラフの場合,bは一意に決定する. そこで点線を辺とする(完全グラフから与えられる…

プログラミングが苦手な自分が競技プログラミングを始めた話

この記事はCompetitive Programming Advent Calendar 2015 Day22の記事です. www.adventar.org 始めてから4ヶ月間競技プログラミングを無事に続けられているのですが,自分がどういう思いで競技プログラミングに対して取り組んできたのかを振り返っていこう…

yukicoder 100問AC

先ほどyukicoderの解いた問題数が100問になりました.通過点記念に記録しておきます.始めてからおおよそ3ヶ月ですね.もう3ヶ月経ってしまったのか・・ 解いた難易度の内訳: 難易度 AC数 ★ 8 ★★ 22 ★★★ 52 ★★★★ 18 ★★★★★ 0 ★★★★★★ 0 始めた頃はDPや全探索…

yukicoder No.119 旅行のツアーの問題

最小カットを最大フローに言い換えて解くタイプの問題に挑戦してみました.おそらくフローを使った簡単な応用問題だとは思うのですが,初めて触れたので発想が斬新だと感じました.(この記事はフローを学んで2日目の記事です,間違いがあれば遠慮なく指摘し…

yukicoder No.19 ステージの選択

強連結成分は定義しか知りませんが,考えればその界隈のアルゴリズムを知らなくても解ける良い問題でした. 問題: http://yukicoder.me/problems/62 解法: あるステージAがクリアできたらステージBのコスト(難易度)が半分になることをA→Bの有向辺で表現し…

ABC #031D 語呂合わせ

問題: abc031.contest.atcoder.jp 本番中なぜか3進数列(ll.64-67)を作るところでずっと詰まっていて実装が終わらなかった.こういうシンプルな全探索が実はbitDPへの登竜門となっているのは面白いと思いました. C++は文字列の取り扱いがやりにくいなあとい…

SRM #673 Div.2 Hard BearPermutations2

このレベルの問題を1時間で解くにはまだ修行が足りないと感じました. 解法はDP(Editorialを大分参考にしました). 要素数の場合のスコアを]とする.求めるべきは]. 下の図のようなシチュエーションである頂点から左A個のヒープと右B個のヒープに分断される…

CODE FESTIVAL 2015 参加レポート

CODE FESTIVAL 2015 参加レポート

Codeforces #331 Div.2 C Wilbur and Points

が与えられた点集合に含まれているならばを満たす全てのもその集合に含まれるという条件を読み落とし,問題を難しく解釈し結局時間内に解けなかった.注意力不足を感じた回でした. 解法は貪欲+2分探索.計算量は. Codeforces #331 Div.2 C

yukicoder No.226 0-1パズル

数学★4.というよりは実装★3.5くらい・・?の問題. 問題:No.226 0-1パズル - yukicoder 解法:解説ページにもあるように,仮に第1行目が0または1が一回でも連続したら第2行め以降はuniqueに決定する.uniqueに決定しない場合は0101...か1010...と交互に並…

ARC028D 注文の多い高橋商店

戻すDPというのをyukicoderで知ったので,理解を深めるために類題をやってみました. arc028.contest.atcoder.jp yukicoderの該当問題へのリンク: No.155 生放送とBGM - yukicoder 時系列順だとyukicoderよりもARCが先のようですね. クエリの入力が1000000…

yukicoder No.259 セグメントフィッシング+

BIT★4.BITを学んだ後に解く問題でBITやるだけ,では物足りない方にはオススメかもしれません. 右向きに場所で泳ぐマスと左向きに場所で泳ぐマスを連結させ長さのBITを用意する.LコマンドやRコマンドに相当する挿入はのときどこにいるかを計算する.Cコマ…

競技プログラミングを始めて2ヶ月が経ちました

唐突ですが,直前のエントリーで話題にしたCODE FESTIVAL予選B,通過していました.久しぶりにこの種類の嬉しさを噛み締めています.というのも,大学に入ってからは評価というものは公正でないものも多く(これは考え方の問題ですが),評価の仕方も教官によ…

CODE FESTIVAL 2015 予選B

結果:3完 + 40点. 順位:110位 A通過を除くとどうやらギリギリ80位以内に入っているみたいですが・・結果を待つのみ. code-festival-2015-qualb.contest.atcoder.jp 区間を管理する解法ですが,STL不慣れが原因で時間がかかってしまった.コンテスト中の4…

CODE FESTIVAL 予選突破練習会 参加レポート

一度競技プログラミング系のオフラインイベントには行きたいと思っていたので,思ったら即実行という感じでなんだか自分が参加しても大丈夫そうなイベントがあったので参加しました! atnd.org 若さオーラを感じながら(人通りは少なかったが)久々に駒場に.K…

Codeforces #325 Div.2

結果:A,Bの2完.Cは普通の実装がTLEだと思い込み,Dは問題の意味を読み違えていた.非常に悔しい思いをした回でした. レート変動:1630 -> 1619 (-11) Cがかなり注意力の必要な実装だったらしく,かなりの人がsystestで落ちていて奇跡的に青維持という結果…

yukicoder No.287 場合の数

組み合わせ★3. 問題ページ: No.287 場合の数 - yukicoder 貪欲にaからhまで順番にそれまでの総和としてあり得る数字を作る組み合わせをそれぞれ調べる. のDPで解きました. あまりにもすんなり通ってしまったのでひょっとしたら★2相当かもしれませんね. …

Codeforces #323 Div.2

結果:A,Bの2完.C解けるべきでした・・結果的に大きい方から貪欲にとるだけの解法で,実装も軽くそりゃそうかという感じ.multiset使うのが短くて済むのですが,ポインタ使わずにできないものか(集合の中身の値を見るのにポインタしか手段がないのか?).D…

yukicoder No.225 文字列変更(medium)

DP★3.レーベンシュタイン距離の実装問題.スペルチェッカーなどに使うのだそう. 参考: レーベンシュタイン距離 - Wikipedia No.225 文字列変更(medium) - yukicoder 解答:愚直に実装しました.DP用マトリクスを作って順に埋めていく感じがわかりやすくて…

yukicoder No.238 Mr. K's Another Gift

文字列★3.実装力が鍛えられる自分的良問でした.vector<char>なんて配列,使う必要なかったかもしれない. 方針:先頭と末端両方から文字列を比べる.イテレータを両端においてスタートし,同じ文字であればその文字を別の配列(C)に格納.もし同じ文字でなければ</char>…

Codeforces #322 Div.2

4回目の参加.直後にSRMがあったのですが.精神的疲弊を予想して参加登録を断念.ブッキングやめてー 今回の結果:A,B,C,Dの4完.どれも特にトリッキーなアルゴリズムを要求する問題ではなかったが,確実に実装する力を試された回でした.Dを時間ギリギリで…

CODE FESTIVAL 2015 予選A

結果:A,B,Cの3完.DはずっとN<100のケースを通す方法もお思いつかず1時間が経過し,直前で答えありきで順繰りにできるか確かめる方法と2分探索を思いつき,悔しい思いをしました・・予選Bは後悔のないようにしたい. 下はACした解答. intにするとオーバー…

yukicoder No.96

今回は初めて★4の問題に挑戦してみました.無論解法を確認しながらですが・・・ ほとんど丸1日かけてACまでこぎつけました.本当は★2~3で基本テクニックに慣れてから解く方が効率はいいのでしょうが,一回★4がどのくらいの難易度かみてみたかったので.これ…

ABC029, TTPC2015

今回のABCは4完63分.D問題で時間がかかりかつ1WA出したのがもったいない.実装は時間がかかってしまったがyukicoderでこれより難しい問題をやっていたので安心して取り組めました.次回も全問正答,かつランキング1ページ目を目指したい. 昨日は東工大プロ…

yukicoder No.281

今回は初めてyukicoder主催のリアルタイムでコンテストに参加しました. No.281が本当に問題児だった.始めは★2でしたがコンテスト中に難易度が★3に修正. 問題は門松列に似たような条件を満たすように3本並んだ竹を長さdづつ切っていって,条件が満たすよう…

Codeforces #320 div2

Codeforces 2回目の参加. まず結果 A,Bの2完.1581 -> 1533 (-48) やはりCで間違いの原因がわからずWA*7を出してしまい,終了2分前に考えのミスに気づいてしまったのが響いてしまった・・・ A: 倍々ゲーム(ただし途中で何度でも1を足すことができる).指定…

yukicoder No.124

幅優先探索★3.かなり時間かかったけれど自力でACまで持っていけてかなり嬉しかった. 考え方:基本的には前いた場所と今の場所をセットで持っておいて,次行ける座標とキューの座標2つが門松列になっていればqueueにpushする.確認が終わったqueueの中身は…

SRM 668 Div2

いつも昼頃に起きる自分がSRMのために早起きしました 結果:1097 -> 1078 (-19) 結果は2完.前回より易しいセットなために前回の1完のときより相対的な出来は悪いという結果. Easy: 文字列を入れ替える問題.特に問題なくできましたが時間がかかってしまっ…

yukicoder No.20

ダイクストラ法(?)★3.この手の問題は初めてだったので,解説を少し読んで,priority_queueの仕様を理解してから実装.正味2時間くらいかかったのでは・・ 解説通りスタートからオアシスまで・オアシスからゴールまで・スタートからゴールまでの3ルートに分…

yukicoder No.206

FFT.多項式乗算にフーリエ変換を使うというのは実際問題として出されると思いつかないですね… 情報系学生なのに今までFFTを手打ちしたことがなかった(爆)ので,今回はFFTの実装がメイン.バタフライとかいう仰々しいアルゴリズムの名前が付いていましたけれ…

CodeForces #319 div2, TopCoder SRM667 div2, ARC 044

いろいろ大会があったので書くネタを溜め込んでしまった..CFとSRM参加しました.SRMはすごい昔に1回参加したことありますが0完だった気がします.CFは初参加. 結果 CF: (1500) -> 1581(青) 2完. SRM: (1000) -> 1097(緑) 1完... ARC: 1完... CF #319 2B …

yukicoder No.277

幅優先探索★3.初の幅優先探索の実装で,queueを使うことまではうっすら知っていましたがどう書けばいいかわからず・・下のリンクを参考にしました.というか自分のソース見ると結果的にほぼパクリです.なので今回はgistはなし.stack9996さんありがとうご…

yukicoder No.13

全探索★3.自力でなんとか再帰が書けた記念. タグはbfsでしたが,dfsしか書き方知らないので今回はdfsで. ループを作るので逆走する動作を封じるために直前の方向を記憶する再帰を書きました. bfsじゃないと解けない問題とかスタックを使わないとオーバー…

yukicoder No.66

DP★3.検証からデバッグまでに3時間ほどかけてしまった・・ まずiさんとjさんが(順調に勝ち上がれば)何試合目にあたるかを求める関数(digit)を作り,あとはM周分の勝率を積算するDPを書きます・・自分でも何言ってるのかわからなくなってきた.int型のビット…

yukicoder No.23

DP★3.やっと自力でACできた記念. まず通常攻撃が必殺技より強ければ通常攻撃だけしていれば良い. そうでない場合: 敵のHP: hを削るのに必要な最小の手数の期待値をとすると, まずにおいて 次ににおいて それより大きい値に対しては 結構単純なので実質…

yukicoder No.41

★3 DP派生.無駄に3時間くらいかかりました・・ 要約すると9以下でを作る方法の数を答えればいいので, でOKだろうと思ったら実は違っていて111111円を1円玉111111枚でも表現可能なことを忘れていた.ということでDPで求めたfの階差が答えでした. 結局自力…

yukicoder No.247

DP,ネタはわかっていてもどうDP化するのかがかなり難しい.結局これも解説見てタネがわかっている状態で実装しました.. 今回は一発でAC.-1の判定が結構雑だけれどまあ今回は本流とは関係ないということで. yukicoder No.247 自分でもよく理由はわからな…

yukicoder No.37

何度もWAが出て途方に暮れていたがdpをmainの外側に出したらACになった. 追記:dp[20000]とmainの中に書いたらACだったのでマクロ関連の挙動が原因だと思われる. 追々記:マクロが原因ではなく,初期化を忘れていたのが原因だった.イージーミスに気づかず…

yukicoder No.4

DP基礎.ナップサック問題実装危うし.AC出すまでかなり時間かかった. yukicoder No.4

yukicoder No.117

愚直に順列・組み合わせ・重複組み合わせを求める問題.だが簡単ではない ※:PRIME = 1000000007は素数 詰まったところ a modpの逆元を求める部分.a^(p-2) = a^(-1)まではわかったのだが,それをO(PRIME)で書いてしまったところ.指数の偶奇で場合分けして…

yukicoder No.157

深さ優先探索の練習に解きました. 自力でdfs書いたの多分初めてじゃないかな・・ 汚いけどなんとか思い通り動いてくれました. yukicoder No.157

AtCoder用 C++テンプレート

今の時点でのC++用テンプレートを書いておきます.色々とまだまだ工夫の余地があるはず(痒いところに手が届かない) IDEはXcode6.4を使っています. AtCoder C++ MyTemplate 速く解答する価値がかなり高いのでこういうのもできる限りメンテナンスしたいとこ…

ABC028

今までは興味本位で競技プログラミングに数回出たくらいで,アルゴリズムの知識の蓄積があるわけでもなく長続きしていませんでしたが,この歳になって必要性が見えてきました.とにかく続けることを第一の目標にしたいと思います.記事を書けばモチベーショ…