yukicoder
寝オチして参加できなかった yukicoder。 問題 No.274 The Wall - yukicoder 解法 貪欲で解けます。まず, 左端のブロックが一番左に寄るようにします。そのためにブロックを回転させるかさせないかを選びます。で, ブロックは一番左端のブロックの座標が小さ…
勉強になりました。 問題 No.270 next_permutation (1) - yukicoder 解法 next_permutation の実装で, swap されるものをメモしておいて, 変化した分を適当に足しこんでいけば良いです。 next_permutation の実装は以下を参考にしましょう。英語ですがそんな…
感動しました。 問題 No.269 見栄っ張りの募金活動 - yukicoder 解法 想定解法とアイデアは変わりませんが, 計算量的に怪しい解法で通しました。一番大事なアイデアは, 「n 人目の人が前の人に比べて i 円支払うお金を増やしたら, それ以降の人はその i 円の…
疲れた… やっぱ構文解析難しいです。 問題 No.265 数学のテスト - yukicoder 解法 構文解析する。ノリは↓と同じです。AOJ 109 Smart Calculator - mayoko’s diarymayokoex.hatenablog.com int d; typedef string::const_iterator State; vector<ll> expression(S</ll>…
なんか結果が合わなくて解ききる前に寝てしまった。 問題 No.260 世界のなんとか3 - yukicoder 解法 見た目から明らかに桁DPです。dp[n][big][exist][mod3][mod8] = (n番目までで,元の数より大きいフラグがbigで,とある桁に3があるかのフラグがexistで,3で割…
頭の悪い方法で解いてしまった。writerの解説(http://yukicoder.me/problems/710/editorial)のほうが計算量的に優れています。 問題 No.258 回転寿司(2) - yukicoder 解法 メモ化再帰で解きました。cur番目の寿司を食べるか食べないか決める時,curを食べずに…
この問題とは関係ないですがカードヒーローってゲーム僕はすごく好きです。 問題 No.200 カードファイト！ - yukicoder 解法 貪欲で解く。Aが勝てるときはAはなるべく小さい値で,Cはなるべく大きい値で勝つ。Aが負けるときもAはなるべく小さい値で,Cはなるべ…
これは良い問題だと思いました。 問題 No.243 出席番号(2) - yukicoder 解法 なんとなく包除原理っぽいです。(0個以上嫌いナンバーが選ばれる場合の数) - (1個以上嫌いナンバーが選ばれる場合の数) + (2個以上嫌いナンバーが選ばれる場合の数) - ...という感…
昨日のAtCoderのD問題の類題ということで解きました。 問題 No.97 最大の値を求めるくえり - yukicoder 解法 Nがそこそこ小さい時(3000未満)のときはそのまま計算しても間に合うので普通に計算する。Nが大きい時を考える。100003は素数であることに注意する…
アイデアはそれほど難しくないような？ 問題 No.86 TVザッピング(2) - yukicoder 解法 ぐるっと回ってすべての点を一周するためには,外側から囲うように回っていくしかありません。なので,スタート地点を全列挙して上のルールにしたがって動いていった時,ち…
幾何ライブラリを補充しました。 問題 No.245 貫け！ - yukicoder 解法 「どの端点とどの端点を通るような直線を作るか」で全探索する。直線が線分と交差しているかどうかの判定は基本的には蟻本に書いてあるとおり。ただサンプル4のようなケースは通らない…
これはもっと早く解けるべきだった… 問題 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;…
いやぁこれ結構実装大変だと思うんですけど… なんか一発ACしてる人多いですねぇ。 問題 No.226 0-1パズル - yukicoder 解法 基本的な方針は,「上の行が決まると下の行も決まるんじゃね？」ということです。この予想はある程度正しくて,上の行に少なくともひ…
最近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…
ツボクラさんがSRM 502のmedはこの問題の類題で解いたとつぶやいていたので解いてみました。 こっちの方が3倍位難しく感じる… 問題 No.54 Happy Hallowe'en - yukicoder 解法 medと同じように何らかの基準を見つけ,その基準通りもらえる家の順番を並べ,dpし…
これは面白い問題だなぁ。 問題 No.210 探し物はどこですか？ - yukicoder 解法 実際に最適な動きをシミュレーションする。具体的には,・現時点で一番ある確率が高い部屋に探しに行く。今までに部屋iにx回通っていたとすると,その部屋でものを見つける確率は…
見た目から動的計画法だろうと思ったけど出題時は☆2で,「もっと簡単な方法があるのかなぁ」とか悩んでしまった。 問題 No.209 Longest Mountain Subsequence - yukicoder 解法 問題設定がちょっと複雑だが,とりあえずという方から考える。 dp[cur][pre] := (…
なんか久しぶりに記事書いてる気がする… この問題はあとでFFT使って解いてみたいです(まだFFTをよく理解していないのでできませんが…) 問題 No.206 数の積集合を求めるクエリ - yukicoder 解法 基本は解説(http://yukicoder.me/problems/440/editorial)に書…
なんか狐につままれたような気分。問題:No.196 典型DP (1) - yukicoder解法:解説のところに書いてあるとおり,O(N^3)であるような気がする計算量が,実はO(N^2)であるというトリックで時間内に解くことができる,という感じ。ソースコード参照しながらそのこと…
どうでもいいけど最近朝が早いせいでめっちゃ眠い。問題:No.189 SUPER HAPPY DAY - yukicoder解法:いわゆる桁DPを使う。dp[n][sum][flag] = (今n番目の数を見ていて,フラグ(まだ与えられた数そのままになる可能性があるか)がflagの状態になっていて和がsumに…
ぐぬぬ。性格悪い。問題:No.186 中華風 (Easy) - yukicoder解法:1つ目と2つ目を満たす制約を全探索で見つけ,それと3つ目を満たす制約を全探索で探す。性格悪いというのは正整数でないといけないということ。 0 2 0 3 0 5 という入力で0を出力するとWAです。 …
考え方はあってたけどランクの実装でバグってた。問題:No.184 たのしい排他的論理和(HARD) - yukicoder解法:bit的な意味で線形独立なものの個数を考えれば良い。そのためにランクを計算することになるが,通常と比べてxor演算して0と1を入れ替えるだけなので…
yukicoderに途中まで参加していました。2問目に日本語の問題で引っかかって1問目と3問目の2完でした。問題:No.181 A↑↑N mod M - yukicoder解法:Mの値が小さいのでなんとなくMの周期について考えられそうな気がします。ただし正直にa^NをMで割ったあまりをそ…
星3つはありそう。問題:No.176 2種類の切手 - yukicoder解法:uwiさんのコードを参考にさせていただきました。 Bが1000より大きい時は,T/Bは10^6以下に抑えられるので,p*A+q*Bのqの値を全探索して最適な値を調べれば良い。 Bが1000より小さい時に同じやり方で…
あっ！この問題,進研ゼミで見たことある！問題:No.177 制作進行の宮森あおいです！ - yukicoder解法:最近(自分の中で)流行りの最大フロー問題。 以下ソースコード const int dx[] = {1, 0, -1, 0}; const int dy[] = {0, 1, 0, -1}; using namespace std; ty…
うーん、なんか最近方針はあってるけどちゃんと実装するまでがめっちゃ遅い。問題:No.174 カードゲーム（Hard） - yukicoder解法:まずAとBのカードをソートする。解法としては,A,Bがi番目のカードをターンtに出す確率を求めて,それを比べることで答えが求ま…
モンテカルロ法が想定解のことあるのかー。問題:http://yukicoder.me/problems/325解法:誤差が結構許容されるのでモンテカルロシミュレーションする。ちょっと気になったので調べたところ、モンテカルロの精度をN倍するためには試行回数をN^2倍しないといけ…
これわからなかったのちょっと恥ずかしい気がする問題:http://yukicoder.me/problems/414解法:573が素数じゃないので、割り算するのはマズイ。ということで、数え上げをすべて掛け算で済ませることを考える。M個の数列でm1,m2,m3,...,mn個の共通因子がある場…
問題:http://yukicoder.me/problems/296 解法:それぞれの点から点への距離をソートする。そして、距離が短いものから順につなげていき、グループを作る。そして、0とN-1が同じグループになった時のものさしの長さが求める答えとなる。これを実装するためにUn…
