読者です 読者をやめる 読者になる 読者になる

mayoko’s diary

プロコンとかいろいろ。

yukicoder

yukicoder No.298 話の伝達

はい・・・・・・・・・・・・・・・・・・・・・・・・・・・・・ 問題 No.298 話の伝達 - yukicoder 解法 割と引っかかる人多い気がするので誤解法も紹介します。 想定誤解法では, dp[i] = (i に話が伝達しない確率)として, 1-dp[N-1] を求めることを目標にします。各 i の dp[i] を求め…

yukicoder No.297 カードの数式

yukicoder に参加しました。初めて作問して出題したのですが, 想定解が間違っていて申し訳ないです… 問題 No.297 カードの数式 - yukicoder 解法 一つ巨大な数を作ってそれ以外の数をひと桁にすると最大, 最小の数が作れそうです。 ただ, マイナス演算子がひ…

yukicoder No.14 最小公倍数ソート

問題 No.14 最小公倍数ソート - yukicoder 解法 先に解法を説明してからなんでそれで良いのかを説明する感じでいきます。まず解法ですが, 最初に 各 ai の約数 div を求めていき, divs[i] という配列にその約数を入れていくと同時に, set を用意して set[div…

yukicoder No.31 悪のミックスジュース

問題 No.31 悪のミックスジュース - yukicoder 解法 まず, N >= V の場合はそれぞれのジュースを 1 リットルずつ買って適当に分配すれば良いです。 V > N の場合もとりあえずすべてのジュースを 1 リットルずつ買っておけば「使わない果物があってはいけない…

yukicoder No.291 黒い文字列

問題 No.291 黒い文字列 - yukicoder 解法 dp[n][k][u][r][o] = (n 文字目までの時点で, "K" のストックが k 個, "KU" のストックが u 個, "KUR" のストックが r 個...) の時の"KUROI" が出来た substring の数 という DP をやります。最高で 100/5 = 20 個…

yukicoder No.288 貯金箱の仕事

問題 No.288 貯金箱の仕事 - yukicoder 解法 まず, ゆきうさぎさんはまずお金を全部貯金箱さんに預けて, そのあと貯金箱さんがなるべく少ない硬貨の枚数でゆきうさぎさんに返せば良い, ということがわかります。つまり, この問題は本質的には「お金をなるべ…

yukicoder No.285〜No.287

問題 No.285 消費税2 - yukicoder No.286 Modulo Discount Store - yukicoder No.287 場合の数 - yukicoder 解法 No.285 はタネあかしすると簡単で, 元の値段に 108 を掛けたあと, それを 100 で割った商が整数部分, 100 で割った余りが少数部分になります…

yukicoder No.282 おもりと天秤(2)

問題 No.282 おもりと天秤(2) - yukicoder 解法 奇偶転置ソートというアルゴリズムを利用します。 奇偶転置ソート - Wikipedia bool cmp[505][505]; int C[505]; bool comp(int a, int b) {return cmp[a][b];} int main() { int N; cin >> N; vector<int> ans(N);</int>…

yukicoder No.281 門松と魔法(1)

問題 No.281 門松と魔法(1) - yukicoder 解法 まず d = 0 の場合は, 現在の高さの配分が上手くいってるかどうかだけで 0 か -1 かを判定できます。それ以外の場合は, 真ん中を一番高くするか, 一番低くするかで場合分けすれば良いです。 int H[3]; const ll …

yukicoder No.277 根掘り葉掘り

yukicoder に参加しました。みんな作問になんとなく「センス」があるのを感じて羨ましいなぁと思っています。 問題 No.277 根掘り葉掘り - yukicoder 解法 30 分くらい想定誤解法で考えていました。 部分木に対する木 DP の要領でやろうとすると頂点 v につ…

yukicoder No.274 The Wall

寝オチして参加できなかった yukicoder。 問題 No.274 The Wall - yukicoder 解法 貪欲で解けます。まず, 左端のブロックが一番左に寄るようにします。そのためにブロックを回転させるかさせないかを選びます。で, ブロックは一番左端のブロックの座標が小さ…

yukicoder No.270 next_permutation (1)

勉強になりました。 問題 No.270 next_permutation (1) - yukicoder 解法 next_permutation の実装で, swap されるものをメモしておいて, 変化した分を適当に足しこんでいけば良いです。 next_permutation の実装は以下を参考にしましょう。英語ですがそんな…

yukicoder : No.269 見栄っ張りの募金活動

感動しました。 問題 No.269 見栄っ張りの募金活動 - yukicoder 解法 想定解法とアイデアは変わりませんが, 計算量的に怪しい解法で通しました。一番大事なアイデアは, 「n 人目の人が前の人に比べて i 円支払うお金を増やしたら, それ以降の人はその i 円の…

yukicoder No.265 数学のテスト

疲れた… やっぱ構文解析難しいです。 問題 No.265 数学のテスト - yukicoder 解法 構文解析する。ノリは↓と同じです。AOJ 109 Smart Calculator - mayoko’s diarymayokoex.hatenablog.com int d; typedef string::const_iterator State; vector<ll> expression(S</ll>…

yukicoder No.260 世界のなんとか3

なんか結果が合わなくて解ききる前に寝てしまった。 問題 No.260 世界のなんとか3 - yukicoder 解法 見た目から明らかに桁DPです。dp[n][big][exist][mod3][mod8] = (n番目までで,元の数より大きいフラグがbigで,とある桁に3があるかのフラグがexistで,3で割…

yukicoder No.258 回転寿司(2)

頭の悪い方法で解いてしまった。writerの解説(http://yukicoder.me/problems/710/editorial)のほうが計算量的に優れています。 問題 No.258 回転寿司(2) - yukicoder 解法 メモ化再帰で解きました。cur番目の寿司を食べるか食べないか決める時,curを食べずに…

yukicoder No.200 カードファイト!

この問題とは関係ないですがカードヒーローってゲーム僕はすごく好きです。 問題 No.200 カードファイト! - yukicoder 解法 貪欲で解く。Aが勝てるときはAはなるべく小さい値で,Cはなるべく大きい値で勝つ。Aが負けるときもAはなるべく小さい値で,Cはなるべ…

yukicoder No.243 出席番号(2)

これは良い問題だと思いました。 問題 No.243 出席番号(2) - yukicoder 解法 なんとなく包除原理っぽいです。(0個以上嫌いナンバーが選ばれる場合の数) - (1個以上嫌いナンバーが選ばれる場合の数) + (2個以上嫌いナンバーが選ばれる場合の数) - ...という感…

yukicoder No.97 最大の値を求めるくえり

昨日のAtCoderのD問題の類題ということで解きました。 問題 No.97 最大の値を求めるくえり - yukicoder 解法 Nがそこそこ小さい時(3000未満)のときはそのまま計算しても間に合うので普通に計算する。Nが大きい時を考える。100003は素数であることに注意する…

yukicoder No.86 TVザッピング(2)

アイデアはそれほど難しくないような? 問題 No.86 TVザッピング(2) - yukicoder 解法 ぐるっと回ってすべての点を一周するためには,外側から囲うように回っていくしかありません。なので,スタート地点を全列挙して上のルールにしたがって動いていった時,ち…

yukicoder No.245 貫け!

幾何ライブラリを補充しました。 問題 No.245 貫け! - yukicoder 解法 「どの端点とどの端点を通るような直線を作るか」で全探索する。直線が線分と交差しているかどうかの判定は基本的には蟻本に書いてあるとおり。ただサンプル4のようなケースは通らない…

yukicoder No.247 線形計画問題もどき

これはもっと早く解けるべきだった… 問題 No.247 線形計画問題もどき - yukicoder 解法 dp[c] = 「cを作るx_1, ..., x_nの組の最小値」 とするとdpで解ける。 const int MAXC = 100100; const int MAXN = 101; const int INF = 1e9; int dp[MAXC]; int C, N;…

yukicoder No.226 0-1パズル

いやぁこれ結構実装大変だと思うんですけど… なんか一発ACしてる人多いですねぇ。 問題 No.226 0-1パズル - yukicoder 解法 基本的な方針は,「上の行が決まると下の行も決まるんじゃね?」ということです。この予想はある程度正しくて,上の行に少なくともひ…

yukicoder No.15 カタログショッピング

最近yukicoderやってなかった… 問題 No.15 カタログショッピング - yukicoder 解法 半分全列挙するだけ。 const int MAXN = 32; int P[MAXN]; struct pll { ll first; ll second; }; bool operator<(const pll& lhs, const pll& rhs) { return lhs.first < r…

yukicoder No.54 Happy Hallowe'en

ツボクラさんがSRM 502のmedはこの問題の類題で解いたとつぶやいていたので解いてみました。 こっちの方が3倍位難しく感じる… 問題 No.54 Happy Hallowe'en - yukicoder 解法 medと同じように何らかの基準を見つけ,その基準通りもらえる家の順番を並べ,dpし…

yukicoder No.210 探し物はどこですか?

これは面白い問題だなぁ。 問題 No.210 探し物はどこですか? - yukicoder 解法 実際に最適な動きをシミュレーションする。具体的には,・現時点で一番ある確率が高い部屋に探しに行く。今までに部屋iにx回通っていたとすると,その部屋でものを見つける確率は…

yukicoder No.209 Longest Mountain Subsequence

見た目から動的計画法だろうと思ったけど出題時は☆2で,「もっと簡単な方法があるのかなぁ」とか悩んでしまった。 問題 No.209 Longest Mountain Subsequence - yukicoder 解法 問題設定がちょっと複雑だが,とりあえずという方から考える。 dp[cur][pre] := (…

yukicoder No.206 数の積集合を求めるクエリ

なんか久しぶりに記事書いてる気がする… この問題はあとでFFT使って解いてみたいです(まだFFTをよく理解していないのでできませんが…) 問題 No.206 数の積集合を求めるクエリ - yukicoder 解法 基本は解説(http://yukicoder.me/problems/440/editorial)に書…

yukicoder No.196 典型DP (1)

なんか狐につままれたような気分。問題:No.196 典型DP (1) - yukicoder解法:解説のところに書いてあるとおり,O(N^3)であるような気がする計算量が,実はO(N^2)であるというトリックで時間内に解くことができる,という感じ。ソースコード参照しながらそのこと…

yukicoder No.189 SUPER HAPPY DAY

どうでもいいけど最近朝が早いせいでめっちゃ眠い。問題:No.189 SUPER HAPPY DAY - yukicoder解法:いわゆる桁DPを使う。dp[n][sum][flag] = (今n番目の数を見ていて,フラグ(まだ与えられた数そのままになる可能性があるか)がflagの状態になっていて和がsumに…

yukicoder No.186 中華風 (Easy)

ぐぬぬ。性格悪い。問題:No.186 中華風 (Easy) - yukicoder解法:1つ目と2つ目を満たす制約を全探索で見つけ,それと3つ目を満たす制約を全探索で探す。性格悪いというのは正整数でないといけないということ。 0 2 0 3 0 5 という入力で0を出力するとWAです。 …

yukicoder No.184 たのしい排他的論理和(HARD)

考え方はあってたけどランクの実装でバグってた。問題:No.184 たのしい排他的論理和(HARD) - yukicoder解法:bit的な意味で線形独立なものの個数を考えれば良い。そのためにランクを計算することになるが,通常と比べてxor演算して0と1を入れ替えるだけなので…

yukicoder No.181 A↑↑N mod M

yukicoderに途中まで参加していました。2問目に日本語の問題で引っかかって1問目と3問目の2完でした。問題:No.181 A↑↑N mod M - yukicoder解法:Mの値が小さいのでなんとなくMの周期について考えられそうな気がします。ただし正直にa^NをMで割ったあまりをそ…

yukicoder No.176 2種類の切手

星3つはありそう。問題:No.176 2種類の切手 - yukicoder解法:uwiさんのコードを参考にさせていただきました。 Bが1000より大きい時は,T/Bは10^6以下に抑えられるので,p*A+q*Bのqの値を全探索して最適な値を調べれば良い。 Bが1000より小さい時に同じやり方で…

yukicoder No.177 制作進行の宮森あおいです!

あっ!この問題,進研ゼミで見たことある!問題:No.177 制作進行の宮森あおいです! - yukicoder解法:最近(自分の中で)流行りの最大フロー問題。 以下ソースコード const int dx[] = {1, 0, -1, 0}; const int dy[] = {0, 1, 0, -1}; using namespace std; ty…

yukicoder No.173 カードゲーム(Hard)

うーん、なんか最近方針はあってるけどちゃんと実装するまでがめっちゃ遅い。問題:No.174 カードゲーム(Hard) - yukicoder解法:まずAとBのカードをソートする。解法としては,A,Bがi番目のカードをターンtに出す確率を求めて,それを比べることで答えが求ま…

yukicoder No.173 カードゲーム(Medium)

モンテカルロ法が想定解のことあるのかー。問題:http://yukicoder.me/problems/325解法:誤差が結構許容されるのでモンテカルロシミュレーションする。ちょっと気になったので調べたところ、モンテカルロの精度をN倍するためには試行回数をN^2倍しないといけ…

yukicoder No.171 スワップ文字列(Med)

これわからなかったのちょっと恥ずかしい気がする問題:http://yukicoder.me/problems/414解法:573が素数じゃないので、割り算するのはマズイ。ということで、数え上げをすべて掛け算で済ませることを考える。M個の数列でm1,m2,m3,...,mn個の共通因子がある場…

yukicoder No.168 ものさし

問題:http://yukicoder.me/problems/296 解法:それぞれの点から点への距離をソートする。そして、距離が短いものから順につなげていき、グループを作る。そして、0とN-1が同じグループになった時のものさしの長さが求める答えとなる。これを実装するためにUn…