yukicoder
初めてyukicoder contestのwriterをやりました。100人ほど参加してくださって、いろいろwriterとして得られるものがあったので書き残しておきます。解説はそれぞれの問題の解説タブに書いてあるので、ここでは解説や提出コードは書きません。 コンテストのリ…
★4昇格．Union-find，木DP，DFSなど色々な要素が入っている問題でためになるのだけれど，実装がかなり難関．個人的には今までyukicoderの問題の中で最凶クラスの実装難の問題でした． 方針：輪の包含関係を根付き木で表現する．Union-findなどで各輪の強さを…
DP★3．3ヶ月位前にも一度挑戦していて，その時は自分の方針のアラが探せず出来ずじまいだったが，今回は一発でACできた． 方針：を満たす最長の上昇部分列の長さを今選んでいる要素のindex，直前に選んだ要素のindexの情報を持った上で求める．下はのときの…
先ほどyukicoderの解いた問題数が100問になりました．通過点記念に記録しておきます．始めてからおおよそ3ヶ月ですね．もう3ヶ月経ってしまったのか・・ 解いた難易度の内訳： 難易度 AC数 ★ 8 ★★ 22 ★★★ 52 ★★★★ 18 ★★★★★ 0 ★★★★★★ 0 始めた頃はDPや全探索…
最小カットを最大フローに言い換えて解くタイプの問題に挑戦してみました．おそらくフローを使った簡単な応用問題だとは思うのですが，初めて触れたので発想が斬新だと感じました．(この記事はフローを学んで2日目の記事です，間違いがあれば遠慮なく指摘し…
数学★4．というよりは実装★3.5くらい・・？の問題． 問題：No.226 0-1パズル - yukicoder 解法：解説ページにもあるように，仮に第1行目が0または1が一回でも連続したら第2行め以降はuniqueに決定する．uniqueに決定しない場合は0101...か1010...と交互に並…
BIT★4．BITを学んだ後に解く問題でBITやるだけ，では物足りない方にはオススメかもしれません． 右向きに場所で泳ぐマスと左向きに場所で泳ぐマスを連結させ長さのBITを用意する．LコマンドやRコマンドに相当する挿入はのときどこにいるかを計算する．Cコマ…
DP★3．レーベンシュタイン距離の実装問題．スペルチェッカーなどに使うのだそう． 参考： レーベンシュタイン距離 - Wikipedia No.225 文字列変更(medium) - yukicoder 解答：愚直に実装しました．DP用マトリクスを作って順に埋めていく感じがわかりやすくて…
文字列★3．実装力が鍛えられる自分的良問でした．vector<char>なんて配列，使う必要なかったかもしれない． 方針：先頭と末端両方から文字列を比べる．イテレータを両端においてスタートし，同じ文字であればその文字を別の配列(C)に格納．もし同じ文字でなければ</char>…
今回は初めて★4の問題に挑戦してみました．無論解法を確認しながらですが・・・ ほとんど丸1日かけてACまでこぎつけました．本当は★2~3で基本テクニックに慣れてから解く方が効率はいいのでしょうが，一回★4がどのくらいの難易度かみてみたかったので．これ…
今回は初めてyukicoder主催のリアルタイムでコンテストに参加しました． No.281が本当に問題児だった．始めは★2でしたがコンテスト中に難易度が★3に修正． 問題は門松列に似たような条件を満たすように3本並んだ竹を長さdづつ切っていって，条件が満たすよう…
幅優先探索★3．かなり時間かかったけれど自力でACまで持っていけてかなり嬉しかった． 考え方：基本的には前いた場所と今の場所をセットで持っておいて，次行ける座標とキューの座標2つが門松列になっていればqueueにpushする．確認が終わったqueueの中身は…
ダイクストラ法(?)★3．この手の問題は初めてだったので，解説を少し読んで，priority_queueの仕様を理解してから実装．正味2時間くらいかかったのでは・・ 解説通りスタートからオアシスまで・オアシスからゴールまで・スタートからゴールまでの3ルートに分…
FFT．多項式乗算にフーリエ変換を使うというのは実際問題として出されると思いつかないですね… 情報系学生なのに今までFFTを手打ちしたことがなかった(爆)ので，今回はFFTの実装がメイン．バタフライとかいう仰々しいアルゴリズムの名前が付いていましたけれ…
全探索★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
