AGC 028 反省
Aのみの1完. 早ときかどうか微妙なタイムでしたが青パフォがとれ, 無事水色になることができました. Bもちょっと考えたんですけど, わからずじまい....とりあえず水色になった喜びも込めて, Aのみ書きます.
A問題
解法
条件から, がであること必要となります(は整数).
まず, 答えの最小値であるで, が構成できるかを調べます. 具体的には, map
構成できなかったときは-1を出力し, 構成できたときはが答えとなることがわかります.
では, で答えとなるものを構成できなかったとき, あるが存在して, 条件を満たすが存在するのかどうかを考えます.
結論を言うと, 答えを構成できなかったときはこのは存在せず, -1を出力するのが答えです.
なぜなら, 答えとなるものが構成できないということはにおいて, とが参照するものが衝突(食い違っている)している, ということになります. この衝突が起こる文字の位置は, を何倍しても変わりません(添字の計算式に代入してみるとわかります).
等号が成り立っている両辺に同じ数をかけても等号が成り立つのと同じです.
感想
やれることを探すと, 発想は自然に出てきます. しかし, この解法が成り立つのかどうかを考えるのに時間がかかりました. 開始15分ほどのsubmissionでしたが, 水へのパフォは十分で, なかなかAGC-Aにしては解きづらい(というより読みづらいでしょうか)問題だったような気がします.
総評
とりあえず水色やったああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああああ!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
というのが第一です. Twitterでもいろいろな人に祝ってもらえてうれしかったです!
競プロのコンテストにではじめて4ヶ月, あのときはC問題もおぼつかない状態でしたが(これは罠で今もおぼつかない), なんとか水色になれました. 真っ直ぐな道ではなく, なかなかレートが伸びない時期もありましたが,
伸び悩んでいた時期に読み漁った先方erの『水色になるまでにやったこと』記事がなかなか助けになったため, ぼくも暇があれば執筆したいです. というかそれを書きたいのが精進のモチベになっていた気さえします().
次からARCじゃないとレートがつかないのかーとか思うとなかなかプレッシャーですね...
ひとまずは緑に落ちないようにがんばりたいと思います.
埃被った蟻本を再び開くときがきたようだな...って感じです.
ABC 112 反省
全完しました.
しかしC問題に時間をかけすぎてパフォは低め...
B問題
解法
ループを回して, 条件を満たしているものの最小値を取ります.
感想
うん.
C問題
問題
解法
問題文をじっっっっっくり読みます.
,が小さく, これら2つを全探索できそうであることがわかります. これらを決めると, あるについてが1つ決まります. これに対し, すべてのを調べ, このが条件を満たしているか調べます.
しかし, これだけでは不十分で, あるが0のとき, 状態が2つ考えられます. この状態に関してはが確定した後で考える必要があるため, 後回しにして考える必要があります. 制約から, ある0でないが存在しているので, 後で考えてもよいことがわかります.
これを実装するとやっとACできます(9WAしました).
感想
顔を真っ赤にしながら実装していました.
D問題
解法
答えは, の約数であることが必要っぽい(?)ことをエスパーしたので, 約数を全列挙し, その約数を何個作れるか?を考えると, すべての約数について, が答えになります.
感想
CをやっとACしたあとで, ろくに証明もせずになんとなく出したのですが, ACできてよかったです.
総評
次のAGCこそ水色になりたい
C++でNimをつくった
C++で某石取りゲームNimを作りました. Nimのコンパイラを作ったわけではありません... CPUと対決するようなものを作りました.
付録のソースコードをコンパイルしてお楽しみください.
開発環境の都合で表示がバグったりするかもしれないですが勘弁.
使い方
- 起動します
- なにも始まりませんが, 石列の数(数値)を入力します(面倒なので数値以外を入力することを想定していません...)(1~30ぐらいが安全です. )
- ゲームが始まります(必ず先手でスタートします
順番ぎめが面倒だったので) - 最後の石をとると勝ちです. がんばりましょう. CPUは一瞬で石を取るのですぐに自分の番が来ます.
各石列が16個までなのは開発環境の都合です.
クラスとかメソッドとかいろいろ学べてよかったです. あまり活かせてませんが.
にしてもグラフィカルなUIはめんどいっすね〜めんどいめんどい.
コンパイルオプション
g++ -std=c++11 -o nim nim.cpp -lglut -lGLU -lGL
スパゲッティなソースコードは続きから
続きを読むARC103 反省
CとDの部分点の1.5完. とれるところは全部とれたと思う. けど立ち回りがよくなかった.
C問題
問題
解法
偶数添字と奇数添字でグループ分けできる. それぞれで最も数が多い数字にするのが最善であるが, その数字が同じだったときの処理が面倒(最後のサンプルで気づいた).
具体的には, 数字の数が最も多い数字を記録しておき, プリオリティーキューに偶数番目と奇数番目の数字の数を別々のものにいれておき, 数字が一致してしまったときに, どっちかのキューの2番めに大きいものと交換して差が小さくなる方を選ぶと最善.
感想
コンテスト中はコーナーケースあるのでは?とか考えてちょっと提出をためらってしまいました. 実装も面倒で面倒な問題です.
D問題
部分点のみで, 後で満点は解き直します.
解法
部分点解法のみ.
まず, がんばって問題文を読解します.
各について, を考えます. この値が異なるものが存在したとき, どうやっても答えを構築することはできません.
なぜならば, をどのように設定してどのように足しあわせても, 各の和の偶奇は不変で, 偶数グループまたは奇数グループについて, 移動しえない場所が存在してしまいます.
上の条件を満たしていると考えると, すべてのについて, としたとき, 部分点の制約ならば十分小さいで構築が可能であることがわかります.
具体的には,
のとき, として目的の場所まで真っ先に移動し, 反復横飛びでもして残りの移動を費やします.
のとき, として目的の場所まで真っ先に移動し, 反復横飛びでもして残りの移動を費やします.
これを実装して300点です.
600点はまた今度...
感想
和の偶奇とかいうの, 結構当てずっぽだったんですけどヒットしたみたいでよかったです.
総評
Cを遅解きしたあと順位表を見てみると, 誰もDをやっていなかったのでEを見たんですが, 結局は解法は生えずに結構な時間を費やしてしまったので, 結果論ではありますがDをもっと速く考えていればレートは伸びたかなーと思います.
コンテスト中は自分の身の丈にあった問題を考察していきたい.
rating 1089->1134
ABC 110 反省
ABDの3完.
A問題
解法
条件から, どれか一個だけ10倍して足すことができるのと同値になる. よって, が答え.
感想
Aにしてはちょっとむずかしい.
B問題
解法
ならば'No War' ,そうでなければ'War'です. 本番ではmin\{y\}とmax\{x\}だけ調べてかどうかを見て, を満たすが存在するかどうかはそこにさらにループを回して調べました.
今考えると, 無意味ですし実装が面倒になるだけだと思います. 実際, 実装のミスで1WAしています. (リジャッジ後もWAのままでした...)
感想
これもなんか問題文が読みにくく, Bにしてはちょっと面倒です.
C問題
解法
コンテスト中に解けず. 考えていたのは, あるアルファベットからアルファベットへの対応を調べ, 2つ以上に対応するものがあればNo, そうでなければYes, というロジックだったのですが, 実装も考察もまずくWAを連発.
WA解答では無向グラフのように対応を双方向に一気に定めていたため, ハッシュマップがめちゃくちゃになってしまっていたようです.
書き直した解答では, 対応する文字が2つ以上あったときにNoを出力するのは同じですが, あとで対応先の文字がただ1つのアルファベットのみに対応していることを確認するようにしています.
前者がアルファベットからアルファベットへの単射であるかの確認, 後者がその対応がアルファベットへの全射であることの確認となっています.
感想
えーこれ難しくないですか><.
D問題
解法
『素因数をいくつかの箱に入れて分割する』というのは, ARC-004D
D - 表現の自由 ( Freedom of expression )で見ていた(解いていませんでしたが)ので, 分割数やらで掛け合わせるのかなとコンテスト中は, ベル数やらスターリング数やらを調べていましたが, 結局素因数を個の箱に分配するときの重複組み合わせでDPができることに気づき, それを実装しました.
今考えると, ARC-004Dの解答を見れば早かったですね...
DPは,
とすると,
となります.
前後のみを見ているdpなので0次元DPに落とせます.
制約の中では, 素因数の数はたいして大きくならず, コンビネーションの前処理は定数なので, この問題の計算量はの素因数分解がネックとなり, となります.
実は本番のコードはの素因数分解をしてしまっています...
しかし, 通ってしまいました.
提出
(コンテスト時提出したもの)
Submission #3257928 - AtCoder Beginner Contest 110
(に改善したもの)
Submission #3270638 - AtCoder Beginner Contest 110
実に800倍の速度の差が出ています.
感想
ささっと思いつけてよかった.
総評
B問題に不備があり, 結果unratedとなりましたが, 初めて推定パフォ1600上限を出せたのでよかったです.
ABC 041-D 徒競走
問題
解法
のときの部分点はnext_permutationを使うと獲得できます.
満点解法では通りを考える必要があるので, 別の解法を考える必要があります.
と, うさぎの集合を見るようにすると数が小さいです.
これに着目して, bitDPを行うことを考えます.
とすると,
基底
遷移
)
とかけます. 遷移においてのというのは, 与えられたについて, 最後尾がであるが, よりの方が速いといったときには矛盾を孕むことになるので, そのような場合の数は存在せずとなる, ということです.
感想
についての制約をよく見ておらずに領域を十分にとっておらず, ACときどきWA状態でオンオンしてました. 領域足りてなかったらREでてほしいです...(我儘).