AtCoder Contest初参加 (ABC-117)
初参加のAtCoderは４完で399th、レートは326からのスタート。C問題でコーナー(?)ケースの処理が甘くて時間を吸われて2REしてしまったが、A, B, Dを一発ACできたおかげでそれなりに幸先の良い滑り出し。
コンテスト成績証
| ユーザ名 | cmat |
|---|---|
| コンテスト名 | AtCoder Beginner Contest 117 |
| 順位 | 399th / 2682 |
| レーティング変動 | 326 (初参加) |
パフォーマンスは1519だった。
ものの本
によると初回レーティングは上限値 1600らしいので、滑り出しとしては上々。
とりあえず半年以内に青を目指したいが*1、 4月以降どれだけ時間が取れるかわからないのでなんとも。来週のyahoo主催コンテストで茶色、できれば緑に到達したい。
一応、パフォーマンス1500ぐらい出れば緑に乗る計算。
現時点でやったこととしては、
- 苦CでC言語の文法の確認(=2-3 days)
- AOJのcourseセクション埋め(~1month)
- STLの使い方を学ぶ(=2-3 days)
- AtCoder C問題埋め(~1 week)(ABC038 - ABC117)*2
以下、2/4に解いたC問題についての自分メモ。
ABC105
考察にやたらと時間がかかってしまった。
ある桁を立てたときにその先で取りうる値の範囲を計算して、そこに入るかどうかで判断。
想定解は、小さい桁から決めていくというもので、遥かにシンプル。
ABC106
5000兆 = 5 * 10^15;
一文字目が2だったとして、5000兆日後の2の数は、
2^0, 2^1, 2^2, ….., 2^(5000兆)で, Kの制限を超える。
よって、最初に登場する1以外の数字が答え。
-> K番目まで1が続くケースをケアしていなくてWA。
ABC107
連続したブロックを取ればいいのは明らか。
その端からスタートすればいいので、ソートしておいて、自身からK-1個先 までの距離の最も小さいものを取る。
-> 座標0からスタートするという条件があった。
0より左を何個取るかで分けて計算。
ループ範囲の間違いでWAを出した。
無駄にややこしい実装を採用したせい。
実際このぐらいはサクッと実装できなければ話にならないのだけれど。
想定解法
どのみち連続する範囲なので、行って戻ってなどの計算は必要なかった。
スタートのろうそくについて全探索すればよく、
0から左の最小値 -> 右の最大値
0から右の最大値->左の最小値
の場合について各スタート位置について調べるだけでよかった。
300点問題でそんなにバグりやすい実装を要する問題は出ないので、考察を磨く。
ABC108
1…Nの中でmod Kが同じものを３つ集めてくればok.
ただし、(2*i)%K == 0という条件がつく。
-> 一発AC
想定解法は、偶奇に着目するというもので、本質的には同じ。
C: Triangular Relationship
K が奇数の時、a, b, c を K で割ったあまりはすべて 0 である必要があります。K が偶数の時、a, b, c をK で割ったあまりはすべて 0 であるか、あるいはすべて K/2 である必要があります。このような組の個数 は、N 以下で K で割って 0 あまるものの個数と K/2 あまるものの個数から求めることができるので、この 問題を解くことができました。
2*i %K == 0という条件に着目すると自然と上の解法になる。
最近のコンテストだと、C問題は平均的には30分ぐらいで解けるイメージ。
ハマると一時間かかるけど。
パフォーマンスは相対評価っぽいので、難しいのが今解けなくても気にしない。
ABC109
xi-Xとしてしまえば最大公約数を求める問題に帰着する。
-> 一発AC
ABC110
SとTのパターンが一致していれば良い。
aabeb
ccdfd
のようになっていればok
Sの文字とTの文字の間の対応関係を作り、それが崩れた段階でNoを返す。
-> 時間はかかったが一発AC。想定解法と同じ。
文字の登場回数数えるだけの嘘解法が通る問題だったらしい。
B問題にも致命的な問題があってunratedになった回とのこと。酷い。
ABC111
最初、考察を間違えていてWA.
odd,evenを分けて考える。
oddの中で最も登場回数の多いもの
evenの中で最も回数の多いもの
を求めておいて、それ以外を寄せていく。
ただし、両者が一致する場合には次点を使う必要がある。
nth_elementの使い方と挙動の理解で時間を取られた。
あと、イテレータを取得した後でnth_elementによるソートが行われることで結果が破壊されていた。
nth_element(v.begin(), v.begin()+k,v.end());
vの前からk番目までが、ソートしたときと同じ順になるようにする。
正直使いみちはあまり無い。素直にソートしてやればよかった。
イテレータの破壊は注意が必要。値を使う場合は常に一時変数に入れたほうが安全。
これでARCのA問題は新基準以降全て解いた。
ABC-Cはあと5問。今日中に終わらせる。
ABC112
手がかりは高々100個で、
中心座標の候補は高々100*100.
各中心座標の候補について、givenな情報とconsistentか検証しても10^6。
中心が領域内にあるということは、高さの候補は、yの最大値以上 yの最小値+200以下
-> TLE
最悪の場合2*10^8になるのでギリギリ厳しい。
高さ方向のループを二分探索に変更してAC.
想定解法では、givenな情報の一つから高さを計算し、それが残りとconsistentかどうかを調べるようにしている。
ABC113
アルゴリズム自体ではなく、6桁で出力するという部分で死んでいた。
printfが優秀。0以外で埋めるのはちょっと面倒かもしれない。
こういう部分で時間を取られるのは本当に本意ではないのでB埋めもしたほうがいいのかもしれない。
というか、なぜググらなかったのか。
ABC114
条件を満たすものを桁数の小さいものから数えていくことを考えたが、
最上位桁の値に応じた場合分けがグロすぎる。
候補は最大でも 3^9個程度のはず。条件を満たすか一つずつ見ていっても間に合いそう。
-> 一発AC。だが時間がめっちゃかかってしまった。
前問といい、桁操作への慣れが足りてない。
大会優勝者のコードを見ると、3, 5, 7に対してビットを割り当て再帰によって候補を生成、3つのビットが全て立っているようなものにいてansを増やすというコード。
やっていることの思想は同じだが、非常にスッキリしている。
列挙するタイプの問題は以前も出会った事があるはずなのに.....
ABC115
ソートしてしまえばO(N),
探索領域はみ出しのケアでWA出した。
ABC116
hiの最小値まで一様に伸ばす。
最小値を軸にして左右に分割して再帰的に伸ばしていく。
-> 一発AC。
ただし時間かかりすぎ。
これでACB42 - ABC117のC問題埋めが終了。
DとかよりもCを早解きできるようにしたい。
41番以前のC埋めをやることにする。
ABC41
indexを保持したままソートするだけ。
ABC40
dpするだけ。
ABC39
シンプルな問題なのにTLEが出る。
合法手全てについて試したがそんなことにはならない。
-> 鍵盤のパターンをサンプルケースの出力からコピペしてきていたが、それが12文字ではなく20文字であることを忘れていた。注意力不足。
ABC38
int溢れ見逃してWA食らった。
問題自体はシンプル。
単調増加が壊れるところまで進めて、ansに加えていく。
想定解法はしゃくとり法というやつで、デバッグは楽そう。
しゃくとり法は今回のような条件を満たす連続する部分列を探すのに適している。基本的なアイデアは、
(l,r)が条件を満たすならば l+1スタートの部分配列の探索の右側はrスタートで良い
ということ。
