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のカートに突っ込んで、いつ買うか悩んでいます
最近チュウニズム金レートになりました
長い銀レ人生だった
