こどふぉ#480Div2 E問題の反省と真解法のメモ(後日更新予定)
この問題
ダメな解法
番号が一番でかいノードを根とする。
すべての葉をヒープに突っ込む。
ヒープからひとつ取り出してその親をヒープに突っ込む。
k個取り出すまで繰り返す。
Submission #38044094 - Codeforces
(ここにtestcase7を踏まえた、なんでダメなのかという考察が入る)
よさそうな解法
AGC022Cでみた
C: Remainder Game - AtCoder Grand Contest 022 | AtCoder
ノードiを取り除くなら、i未満のノードを全部取り除いたほうがまし
→i未満のノードを全部取り除くことでノードiを取り除かないですむなら、取り除かないでおきたい
→i未満のノードを取り除くことでノードiを取り除かなくてもいけるか???
番号が一番でかいノードを根とする。
すべての葉の番号をsetに突っ込む。
取り除くものがなくなるまで以下を繰り返す。
自分より親の番号が大きいような葉の親の番号をsetに突っ込む。
自分より親の番号が大きいような葉を木から取り除く。
setの中身がすべて0になるまで以下を繰り返す。
setの中で、番号が最も大きいものAを探す。
setに含まれるノードで番号がA未満のものの個数を調べる。
k以上なら
setからAを取り除く。
k未満なら
AとAの子孫だったものをダメにして、それらをsetから取り除く。
その個数だけsetに0を突っ込む。
木からAを取り除く。
取り除くものがなくなるまで以下を繰り返す。
自分より親の番号が大きいような葉の親の番号をsetに突っ込む。
自分より親の番号が大きいような葉を木から取り除く。
ダメにしたものを番号順に出力する。
(ここにやってみた結果が入る)
AtCoder Regular Contest 097 反省
爆死
実装力が全然足りなかった
問題C
a,aa,aaa,aaaa,aaaaa,aaaab,aaaac,…,aaabaみたいに辞書順に並んだ文字列を頑張って生成することしか考えてなくて、実装力がないため終わった
問題D
Union-Findを使う
オリジナル即日実装したらバグを量産した
結局ネットに落ちてるやつをコピペして使ったので、バグの原因を明らかにしないといけない
setとかqueueとかを使うたびにSTLの解説ページを読まなきゃいけないので、早いとこメソッドの名前などを覚えてしまいたい
38:23でAC
Submission #2499950 - AtCoder Regular Contest 097 | AtCoder
問題E
2回も解法を間違えた
1回目
どっちか一方に白を全部まとめてからやればいいと思った
サンプルケース1ですら読んでなかったのが原因の1つ
Submission #2502454 - AtCoder Regular Contest 097 | AtCoder
2回目
次に並べるべき白球,黒球2つのうち近いほうを持ってくればいいと思った
真解法には近づいたが詰めが甘い
Submission #2503991 - AtCoder Regular Contest 097 | AtCoder
結果
パフォ:1160
レート:1313->1281
競プロ全振りしなきゃ…
Codeforces Round #480 (Div. 2)
初Codeforces
Codeforcesのルール
ただ問題を解けばいいということではないらしい
自分の解答に満足したら足を引っ張りあえるルール
英語で書かれた問題を読む。
→ 問題を解決するコードを書いて提出する。
→ pretestによって判定され、ACなら暫定的な得点がつく。
(AC: ACcepted/正解の意。 対してWA: WrongAnswer/不正解の意。)
→ よさそうならlockする。こうするとコードの再提出ができなくなる。
→ lockするとhackできる。すなわち他人の提出コードを見てバグりそうな入力を送り付けることができる。
→ hackに成功すると得点を得て、失敗すると得点を失う。また、自分のコードがhackされるとそのコードの得点がなくなる。
コンテスト終了後に再度ジャッジをして、そこで通ったら得点が確定し、通らなかったら得点がなくなる。
2時間で6問出題される。
n問目の配点は最大500*n点で、時間とともに減少する。(終了時には500点減少してる?)
再提出でも減点される。(ACできなかった問題への提出でも)
参加記
今回はCodeforces Round #480 (Div. 2)に参加しました
Div1,2,3があって、番号が小さいほど難しい
開始前(0時5分スタート)
頭が痛かったのでちょっと寝て15分前に起きた
問題A
パールとリンクを繋いで輪状のネックレスを作る。
パールとリンクの個数が与えられるので、パールを等間隔に配置することができるか判定する問題。
パールがあるならリンクの個数をパールの個数で割った余りが0であればよい。
パールがないなら無条件でよい。(これを見落として1WA)
8:34でAC
Submission #38027551 - Codeforces
問題B
4行n列のマス目が与えられる。(nは奇数)
このマス目の辺でも隅でもないところに、k個の通れないマスを配置して、次の[条件]を達成することを考える。
[条件] (1,1)から(4,n)へ隣り合ったマス目を通って最短で移動する経路の個数と、(4,1)から(1,n)へ同様に最短で移動する経路の個数が一致する。
この条件を満たす配置が存在するか判定し、存在するなら構成する問題。
2番目のテストケースを見て謎になった。
問題C
画像データを扱いやすくするために、似ている色の部分を1色で塗りつぶすというテーマの問題。
具体的には、色データがとりうる範囲[0,255]を、幅がk以下になるようにいくつかの連続した区間に分割し、ある区間に属するデータをその区間の最小値に置き換える。
(ここでいう幅とは、区間に属する整数の個数のこと。例えば区間[2,5]の幅は4)
データ列が1列になって入力されるので、置き換えた結果で辞書順最小になるようなものを出力する問題。
辞書順最小なので先に入力されたデータを優先的に小さくしていけばよく、後から入力されたデータはそれに合わせてできる限り小さくすればよい。
46:24でAC
Submission #38036259 - Codeforces
問題D
数列の項をいくつかのグループに分け、グループに属する任意の2要素の積が必ず平方数になるようにする。
入力される数列の連続した部分列のうち、以上のようにグループを分けた時のグループの個数の最小値がkであるような部分列の個数を、各kについて出力する問題。
めっちゃめんどそうなのでやらなかった。
問題E
ある国で地区対抗のゲームが開催されるが、参加させない地区をいくつか選ぶことになった。
ある地区から別のある地区へは、直接移動するか他の地区をたどって移動することができ、その移動経路は1通りしかないことが保証されている。
すなわち、地区を頂点として直接行き来できる地区同士を辺でつないだグラフは木構造をなしている。
地区には番号が振られていて、i番目の地区を参加させないことにするとコストが2^iかかり、またそのi番目の地区は通ることができなくなる。
地区の構造が入力されるので、参加する地区同士は行き来できるようにしながら、k個の地区を参加させないようにする。このときのコストが最小になるような地区の選び方を出力する問題。
pretest7でWA(なんでや)
Submission #38044094 - Codeforces
pretest7の内容を見ると自分のが嘘解法であることが分かった。
考察しなおして真解法がわかった(と思う)ので、これについてはまた別の記事で書こうと思う。
問題F
Eが通らないのがつらくて読めなかった。
結果
A,Cの2完で1658点、6793人中982位。(参加人数がすごい)
レートは1555で緑色、Specialistになった。(称号は持ち上げすぎな気がする)
ブログやってみます
はじめまして
やむなく( @yamunaku )といいます。
プログラミングコンテストやCTF、ゲームなどの日記を書くつもりです。
自己紹介 [18/05/08現在]
やむなく ( @yamunaku )
京都大学工学部1年生
Atcoder 水色(1313)
Topcoder 未参加
Codeforces 未参加
CTF 超初心者
好きなもの: ゲーム
近況
現在ニーアオートマタ(steam版)をプレイ中です
switchとゼルダとスプラとぷよテトをamazonのカートに突っ込んで、いつ買うか悩んでいます
最近チュウニズム金レートになりました
長い銀レ人生だった