結果：A,B,Cの3完．DはずっとN<100のケースを通す方法もお思いつかず1時間が経過し，直前で答えありきで順繰りにできるか確かめる方法と2分探索を思いつき，悔しい思いをしました・・予選Bは後悔のないようにしたい． 下はACした解答． intにするとオーバー…
今回は初めて★4の問題に挑戦してみました．無論解法を確認しながらですが・・・ ほとんど丸1日かけてACまでこぎつけました．本当は★2~3で基本テクニックに慣れてから解く方が効率はいいのでしょうが，一回★4がどのくらいの難易度かみてみたかったので．これ…
今回のABCは4完63分．D問題で時間がかかりかつ1WA出したのがもったいない．実装は時間がかかってしまったがyukicoderでこれより難しい問題をやっていたので安心して取り組めました．次回も全問正答，かつランキング1ページ目を目指したい． 昨日は東工大プロ…
今回は初めてyukicoder主催のリアルタイムでコンテストに参加しました． No.281が本当に問題児だった．始めは★2でしたがコンテスト中に難易度が★3に修正． 問題は門松列に似たような条件を満たすように3本並んだ竹を長さdづつ切っていって，条件が満たすよう…
Codeforces 2回目の参加． まず結果 A,Bの2完．1581 -> 1533 (-48) やはりCで間違いの原因がわからずWA*7を出してしまい，終了2分前に考えのミスに気づいてしまったのが響いてしまった・・・ A: 倍々ゲーム(ただし途中で何度でも1を足すことができる)．指定…
幅優先探索★3．かなり時間かかったけれど自力でACまで持っていけてかなり嬉しかった． 考え方：基本的には前いた場所と今の場所をセットで持っておいて，次行ける座標とキューの座標2つが門松列になっていればqueueにpushする．確認が終わったqueueの中身は…
いつも昼頃に起きる自分がSRMのために早起きしました 結果：1097 -> 1078 (-19) 結果は2完．前回より易しいセットなために前回の1完のときより相対的な出来は悪いという結果． Easy: 文字列を入れ替える問題．特に問題なくできましたが時間がかかってしまっ…
ダイクストラ法(?)★3．この手の問題は初めてだったので，解説を少し読んで，priority_queueの仕様を理解してから実装．正味2時間くらいかかったのでは・・ 解説通りスタートからオアシスまで・オアシスからゴールまで・スタートからゴールまでの3ルートに分…
FFT．多項式乗算にフーリエ変換を使うというのは実際問題として出されると思いつかないですね… 情報系学生なのに今までFFTを手打ちしたことがなかった(爆)ので，今回はFFTの実装がメイン．バタフライとかいう仰々しいアルゴリズムの名前が付いていましたけれ…
いろいろ大会があったので書くネタを溜め込んでしまった．．CFとSRM参加しました．SRMはすごい昔に1回参加したことありますが0完だった気がします．CFは初参加． 結果 CF: (1500) -> 1581(青) 2完． SRM: (1000) -> 1097(緑) 1完... ARC: 1完... CF #319 2B …
幅優先探索★3．初の幅優先探索の実装で，queueを使うことまではうっすら知っていましたがどう書けばいいかわからず・・下のリンクを参考にしました．というか自分のソース見ると結果的にほぼパクリです．なので今回はgistはなし．stack9996さんありがとうご…
全探索★3．自力でなんとか再帰が書けた記念． タグはbfsでしたが，dfsしか書き方知らないので今回はdfsで． ループを作るので逆走する動作を封じるために直前の方向を記憶する再帰を書きました． bfsじゃないと解けない問題とかスタックを使わないとオーバー…
DP★3．検証からデバッグまでに3時間ほどかけてしまった・・ まずiさんとjさんが(順調に勝ち上がれば)何試合目にあたるかを求める関数(digit)を作り，あとはM周分の勝率を積算するDPを書きます・・自分でも何言ってるのかわからなくなってきた．int型のビット…
DP★3．やっと自力でACできた記念． まず通常攻撃が必殺技より強ければ通常攻撃だけしていれば良い． そうでない場合： 敵のHP: hを削るのに必要な最小の手数の期待値をとすると， まずにおいて 次ににおいて それより大きい値に対しては 結構単純なので実質…
★3 DP派生．無駄に3時間くらいかかりました・・ 要約すると9以下でを作る方法の数を答えればいいので， でOKだろうと思ったら実は違っていて111111円を1円玉111111枚でも表現可能なことを忘れていた．ということでDPで求めたfの階差が答えでした． 結局自力…
DP，ネタはわかっていてもどうDP化するのかがかなり難しい．結局これも解説見てタネがわかっている状態で実装しました．． 今回は一発でAC．-1の判定が結構雑だけれどまあ今回は本流とは関係ないということで． yukicoder No.247 自分でもよく理由はわからな…
何度もWAが出て途方に暮れていたがdpをmainの外側に出したらACになった． 追記：dp[20000]とmainの中に書いたらACだったのでマクロ関連の挙動が原因だと思われる． 追々記：マクロが原因ではなく，初期化を忘れていたのが原因だった．イージーミスに気づかず…
DP基礎．ナップサック問題実装危うし．AC出すまでかなり時間かかった． yukicoder No.4
愚直に順列・組み合わせ・重複組み合わせを求める問題．だが簡単ではない ※：PRIME = 1000000007は素数 詰まったところ a modpの逆元を求める部分．a^(p-2) = a^(-1)まではわかったのだが，それをO(PRIME)で書いてしまったところ．指数の偶奇で場合分けして…
深さ優先探索の練習に解きました． 自力でdfs書いたの多分初めてじゃないかな・・ 汚いけどなんとか思い通り動いてくれました． yukicoder No.157
今の時点でのC++用テンプレートを書いておきます．色々とまだまだ工夫の余地があるはず（痒いところに手が届かない） IDEはXcode6.4を使っています． AtCoder C++ MyTemplate 速く解答する価値がかなり高いのでこういうのもできる限りメンテナンスしたいとこ…
今までは興味本位で競技プログラミングに数回出たくらいで，アルゴリズムの知識の蓄積があるわけでもなく長続きしていませんでしたが，この歳になって必要性が見えてきました．とにかく続けることを第一の目標にしたいと思います．記事を書けばモチベーショ…
