水色プログラミング

競プロで解いた問題の記録,ゲーム制作の進捗など...

AtCoder Beginner Contest 110

結果

D 問題を解き1完,1932 位中 940 位.400 点であった D 問題を解けたのはよかったが,C 問題が難しく解けなかった.D 問題より C 問題の方が難しいと感じた.

 

f:id:babcs2035:20180924142540p:plain

f:id:babcs2035:20180924142544p:plain

C - String Transformation

コンテスト後に解いた.

babcs2035.hateblo.jp

D - Factorization

babcs2035.hateblo.jp

CODE FESTIVAL 2018 qual A

結果

2完,1136 位中 250 位.A, B 問題をスムーズに解けたのは良かったが,目標であった3完に届かなかったのが残念.

 

f:id:babcs2035:20180924141858p:plain

f:id:babcs2035:20180924141907p:plain

A - 配点

Submission #3241070 - CODE FESTIVAL 2018 qual A

B - みかん

Submission #3241714 - CODE FESTIVAL 2018 qual A

C - 半分

babcs2035.hateblo.jp

 

AtCoder Beginner Contest 110:D - Factorization

問題

D - Factorization

解法

M を素因数分解する.M の各素因数を N 個の箱に分けていくと考えればよい.このとき,単純に N ^ (各素因数の個数) を掛け合わせたものを答えにしてしまうと,重複が生まれてしまう.なので,重複組み合わせ H(n, r) = C(n+r-1, n) を使う.このとき,逆元などを用いた Combination を使う必要がある(制約が大きいので).

解答

M = 1 のコーナーケースで 1 WA をしてしまった.

Submission #3256550 - AtCoder Beginner Contest 110

f:id:babcs2035:20180924141314p:plain

 

AtCoder Beginner Contest 110:C - String Transformation

問題

C - String Transformation

解法

S -> T になるように各文字を置き換えるとき,S_i が T_i に対応するように1対1の関係になれば一致させることが出来る.逆に,1対1にならなければ一致させることは出来ない(1つのアルファベットを2つに変化させることは出来ないから).

解答

Submission #3262724 - AtCoder Beginner Contest 110

コンテスト中に解けなかった.

f:id:babcs2035:20180924140643p:plain

 

CODE FESTIVAL 2018 qual A : C - 半分

問題

C - 半分

解法

「dp(i, j, f) := i 番目までで j 回操作するときの通り数(f := 今までの要素を 0 にしたかどうか)」で DP をする.f が true のとき,操作の回数が余ったとしても,どこか 0 である要素で余った回数を消費すれば良いので,これによって重複を生まない DP 漸化式になる.

コンテスト中では「dp(i, j) := i 番目までで j 回操作するときの通り数」と考えていて,重複をどうやったら処理できるか悩んでいた.

解答

コンテスト中含め 2 WA + 1 RE.RE は範囲外アクセスが起こっていた.

Submission #3248141 - CODE FESTIVAL 2018 qual A

f:id:babcs2035:20180923160803p:plain

 

PCK 2018 予選に出ました

PCK に初めて出ました

高1になったので,高3の先輩と出ました(許可は得ていないので,名前を書くのはやめておきます).

競技前

先輩と Discord でバチャをやったりしました.ここで僕は問題1~5を 0 WA で早解きする必要があると分かりました.

競技直前

文化祭1日目で忙しいのにも関わらず,部の展示の手伝いをせずに PCK の過去問を解いたり,ジャッジを確認していました(害悪).

部にあるプリンターを会場であるコンピューター教室に運び,印刷テストをするも実行できず(恐らく学校の変な Wi-Fi のせい).しかたなく,急いで部の展示から USB の有線ケーブルを持ってくる羽目に(ここで競技開始まで5分を切る).こちらの PC で印刷して,ほかのチームに配るということになりました.

そして,用意していたキーボードがなぜか反応しない不具合に見舞われます(ここで競技開始まで 15 秒を切る).発狂しつつ競技が始まりました.

競技中

問題1を見る.やるだけ.提出ページで言語を変えるのを忘れないと念じながら提出し AC.

問題2を見る.やるだけ.AC.

問題3を見る.やるだけ.N が自分を含まないことがひっかけ.AC.

問題4を見る.やるだけ.1L の水をいくつ買うか全通り試せばよい.AC.

問題5を見つつ,問題6と7の問題を印刷.

突然変な問題が来たなあと思う.y が高々 72 通りしかないと先輩が気付き,y を全通り試せばよいねとなる.実装でもバグを指摘して頂いた.AC.

僕が問題5を実装している間,先輩が問題6の解法を思いつく.問題5を解いた後,先輩に PC を渡し,自分は問題7を考える.

先輩が問題6を AC し,順位表を見ると意外と上の方にいた.WA を出さなくてよかったと思った.

問題7の概要を先輩に説明し,考える.先輩が DP 解を思いついたので,問題8を印刷し,僕はそちらを読む.

先輩が問題7に提出するが WA.なぜ???となり,ひとまずパス.

問題8を考える.問題文が日本語読解コンテストで誤読しそうになった.よく分からないのでパス.

問題9を考える.先輩が atan2 が一致すれば一直線上にあると言えるとヒントを言って頂き,僕が実装する.サンプルが通る.提出する.CE(は?).

とりあえず発狂し,atan2 の std:: を外してみる.AC.abs で std:: をつけなければ CE になることは事前に思い知らされていたので気を付けていたが,CE を出してしまい先輩に対しては無限に申し訳ない思いになった(すみませんでした).

ここからは先輩に完全に PC を渡し,自分は問題文の印刷&配布係になる.問題 10 ~ 12 を印刷&配布&読むも,さっぱり分からない.

問題 10 は木なんだなあと感じた.

問題 11 はひっくり返すと円盤を回す方向と数字の正負が逆転するだけだなあなどと感じた.

問題 12 は問題文がシンプルで分かりやすいなあと感じた.

先輩が問題 11 はセグ木に操作を載せてあげればよいと解法を思いつく.先輩が実装&テストし提出.AC.先輩と僕でめっちゃ喜んだ.

順位表を確認する.同率2位だった(確か1位にチーム「solars」さん,2位にチーム「もこくるくる」さんや他数チームが入っていた気がする).

その後,問題8は priority_queue() に突っ込むだけと先輩が気付き,提出,AC.

僕は問題7のバグの原因を探していた.が,先輩が実装の問題に気づき,修正,提出,AC.

ここで残り 30 分ぐらいを切り,僕は集中力がもう切れそうだった.あとは先輩とおしゃべりをしていた.

順位表凍結時の順位は2位.結果は 10 完 3 WA だった(と思う).

競技終了直後

他のチームに結果を聞きにいきました.4 完 1 WA だったそう(問題1で CE を出した人のことをその相方がめっちゃいじってて草だった).

PCK 実況班のツイートを見たところ,問題3の FA だったらしい.

競技終了後

部の展示に戻り,うまく運営できたかなど聞きました.配布 DVD のほとんどがなくなってしまったらしい.500 枚じゃ足りないんだなあと感じました.

予選通過チーム発表

チーム「Noyashi」さんに抜かされ,総合3位でした(うれしいですね).自分が出した CE が響いてしまい,申し訳ありませんでした(2回目).

本選

でも頑張ります.

 

AtCoder Regular Contest 035:D - 高橋くんとマラソンコース

問題

D - 高橋くんとマラソンコース

N 個のチェックポイントが平面上の座標の点にあるとき,走者はチェックポイントを 1, 2, ... , N の順番に,チェックポイント間は最短距離になるように好きな経路を取る.このとき,「k 番目のチェックポイントを (x, y) に移動する」「チェックポイント a -> b と c -> d の経路のどちらが通り数が大きいか」のクエリに答える問題.

解法

区間の通り数は掛け算によって表され,問題の制約 10^6 では通り数がとても大きくなってしまうので,log を取ることを考える.そうすれば,通り数が小さく済み.通り数も足し算で表すことが出来る.前処理で各区間の通り数を Combination を使って計算し,BIT に入れておく.チェックポイントを移動させるクエリでは,変更したチェックポイントの前後の区間の通り数を更新すればよい.通り数を比較するクエリでは,それぞれの区間の通り数の log の和を BIT で取得すればよい.O(Q log N).

解答

Submission #3221586 - AtCoder Regular Contest 035

7 WA した(区間和を取得する際のミス).

f:id:babcs2035:20180919065423p:plain

AtCoder Regular Contest 033:D - 見たことのない多項式

問題

D - 見たことのない多項式

N 次多項式 P(x) があり,P(0), P(1), ... , P(N) が分かっているとき,P(T) を求める問題.

解法

さっぱり分からないので解説を読んだところ,ラグランジュ補間というものを使うらしいと分かった.これは,P(x) を P(v) * (v の式) で表すことができるもの.それぞれ逆元も用いて求めることができる.O(N log mod).

解答

Submission #3220582 - AtCoder Regular Contest 033

実装が分からず 1 WA した&他人のコードを見た.

f:id:babcs2035:20180918191738p:plain

 

AtCoder Regular Contest 032 : D - アットコーダーモンスターズ

問題

D - アットコーダーモンスターズ

N 匹のモンスターには攻撃値と防御値がそれぞれ決まっていて,この中から K 匹選んでチームを作りたい.このチームの「不安定度」はチーム内のモンスター同士の攻撃値の差と防御値の差の min の max で定義される.この時,「不安定度」の最小値と,このときのモンスターの選び方の通り数を求める問題.

解法

攻撃値と防御値を二次元配列にプロットして考える.そうすれば,この問題は「二次元配列上で K 個点を含むような正方形の四方の長さの最小値とは?」に言い換えられる.これは,二分探索を用いて求められる.

この時の通り数は,この正方形の中にある点の選び方の総和になる.重複が生じる場合があるので注意.

解答

Submission #3219197 - AtCoder Regular Contest 032

f:id:babcs2035:20180918143634p:plain