cplusplusonly's memo

Atcoder: https://atcoder.jp/users/cplusplusonly

AtCoder ABC128 参戦記

競技プログラミング プログラミング

AtCoder の ABC 128

atcoder.jp

結果 5 完 50 分 でまずまずスピード出せたかな？と思って終了時に順位表見たら驚きの 106 位。
5 完までに難しいところがなかったので早解き合戦で 500 位ぐらいだと思ってたのでびっくりしました。
パフォーマンスが判明したところ驚愕の 2332...。レーティングも一気に引きあがりました。

f:id:y_r:20190526232831p:plain

感想

A 問題

瞬殺

B 問題

これは B 問題にしては難しい。結局 string -> vector (要素 : struct {int index; int p; }) みたいな map を作って、

  • map を昇順にまわす
    • 内部の vector は p で降順ソート
    • ソート済みの index を出力

とした。

C 問題

電球に応じてスイッチをグループ化して...と考えるとめんどくさいが n, m はせいぜい 10。bit 全探索にかければ終了。
このコードを最初からバグなし (初回ビルドがテストケースを全部通る) で書けたのでうれしかった。

D 問題

宝石を戻す手順は最後に固めてよいので、

  • 宝石を取る手数を選ぶ。ここで宝石を戻せる最大個数が決まる
    • 宝石を左右からとってくる
      • マイナスの宝石をマイナスが大きいものから捨てておく
      • 残った宝石の価値の最大値が答え
E 問題

実は出発時にはどこで工事にぶつかるかわかる。したがって

  • 工事開始時刻 (を出発地点の時刻に直したもの)
  • 工事終了時刻 (を出発地点の時刻に直したもの)

を用意してやれば、Di が出発しようとしたときの工事状況がわかるので、工事地点の X が一番小さいものが答えになる。工事してなければ無限に歩けて -1。

D が単調増加しているので助かった。単調増加してない場合はソートして答えの時に戻す手順が必要。

F 問題

(A - B) = X とおくと、ゴール時の制約により、 X によって B mod X] は一意に決まる。すると、 X のとりうる値の範囲 [1, 2/n) に対して、

  • X * k の累積和
  • X * k+ B の累積和


の 2 個の累積和ができ、前者は前から n 個取ったときの和、後者は後ろから n 個取った時の和を足した値で最大になる値が答え。
ただし、B mod X が 0 のときは n に制限がかかる (池ポチャになる n はとれない) のでその場合を除外する。

ぐらいまで考察して 1:40:30 *1 ぐらいに提出したところ WA。あと少し足りなかったらしい。

*1:当然時間オーバー

AtCoder ABC126 参戦記

プログラミング 競技プログラミング

AtCoder の ABC 126

atcoder.jp

結果 5 完で可もなく不可もなく...といった感じでしたが、途中で遭遇したジャッジの不具合 (ジャッジが途中でリスタート or 最後まで終わらない) に引きずられて undated になりました。
全体的な感想としては各問題 100 点ずつ高くない？というものでした。

感想

A 問題, B 問題

瞬殺

C 問題

double で計算したら誤差が範囲外だったのであわてて有理数 (しかも分母で固定のなんちゃって有理数) で実装した。
後で聞いたら double で十分精度が出るらしい。誤差が範囲外だったのは相対誤差だけだったからね...

D 問題

最初のノードを 0 にして、枝をたどって枝の重さが奇数なら 0 ⇔ 1 と変化させればよい。あとは適当なノードから探索。

E 問題

Xi と Yi についてはどちらかがわかれば確定する。つまり、必要な手数は独立したグラフの数。
Union-Find してグラフの数 (= find(i) で見つかる値の個数) を数えればよい。

F 問題

0\ 1\ 2\ ...\ 2^m -1\ 0\ 1\ 2\ ...\ 2^m -1 を回転すればよい!! と考察したが外れ。
これでは n のペアに対して値が n になってしまう。

AtCoder diverta 2019 参戦記

プログラミング 競技プログラミング

AtCoder の diverta 2019 Programming Contest

atcoder.jp

に参加しました。ABCD の 4 個が解けて E に手が出ずに順位が落ちるのを眺めているだけ...と思ったのですがなぜか順位が変わらない...
結局ジャッジサーバダウンで unrated となりました。

感想

A 問題

瞬殺

B 問題

B 問題で TLE 問題が出るとは...一瞬うっとなったがよく考えれば 2 重ループすればよい。

C 問題
  • 途中の AB の数 + min(先頭 B, 末尾 A)
  • (先頭 B かつ 末尾 A) となる数が上記 min と同じだと - 1 する

で回答

D 問題

N が 100 までの計算過程を観察して

  • 商 d が 1 - sqrt(N) までの計算
    • m = n / d とすると m または m - 1 が候補
  • 商がそれ以降の場合
    • m が sqrt(N) まで落ちているので m が 2 に至るまで全部 try

と考察した。

実装を少しミス (安全のために閾値を sqrt(N - 1) としたところ計算間違いを出した) して WA を出したが直して AC

E 問題
  • 一か所の区切りが決まれば、残りの区切り候補は固定される
  • 二個の連続した区切りは除去しても解となる

まで考察して時間切れ...

AtCoder AGC033 参戦記

プログラミング 競技プログラミング

AtCoder の AGC033

https://atcoder.jp/contests/agc033

に参戦しました。ABC の仕様変更 (6 問で 1999 まで rated) により水色を維持することにあまり意味はなくなりましたが、レートは落としたくないので、A 問題はマストとして、B, C のうちどちらかを解ければよい (どちらも解ければハッピー) という考え方で臨みました。
結果は 101 分で A, B の 2 問 (ただし 2 WA 2 TLE) となり、順位は 737 位、パフォーマンス 1548 でした。WA/TLE が多すぎてパフォーマンスを落としましたが、可もなく不可もなしという感じです。

f:id:y_r:20190505001730p:plain

感想

A 問題

最初は \max(\forall 点, min(\forall 黒マス, 点と黒マスの距離)) みたいな実装して TLE くらった... 1000*1000*1000*1000 の計算量は TLE くらうよね...
素直に黒色を中心として幅優先探索をしたのだが、ここでも WA (すべてが黒色のケース) と TLE (探索済みマスの探索防止を忘れてた) により -15 分...

B 問題
  • H 軸と W 軸は独立して扱える
  • 後ろからたどっていって 上下左右に落とせるマスの範囲をもとめて、その範囲内に始点があれば No, なければ Yes となる
    • ただし途中で (右に落とせるマス <= 0) (上下左も同様) となったらその時点で No
    • ただし途中で (左に落とせるマス <= 右に落とせるマス) (上下も同様) になったらその時点で No
      • 上記は嘘解法 (というか考察ミス) 正確には (左に落とせるマス - 1 <= 右に落とせるマス)。

ところまで考察して実装..なのだが、実装ミス*1により WA をくらう。

C 問題

終了 20 分前に

  • コインを取るたびに木のサイズが縮む
  • 縮む量は 1 (葉を取るとき) or 2 (葉以外を取るとき) となる
  • 先手の勝利は木のサイズ依存
    • サイズ {i} で勝てるのはサイズ {i -1} or サイズ {i - 2} が負けるとき (初手で負けるサイズに落として相手に手番を渡せばよい)

まで考察して終了 45 秒前に投げたが WA。いまだ持って WA が取れてない。この方針はダメなのか？
=> やっと理解した。木のサイズ (直径というらしい) を求める計算間違えてた...

*1:しかもサンプルケース WA

AtCoder ABC125 参戦記

プログラミング 競技プログラミング

AtCoder の ABC125

atcoder.jp

に参戦しました。

前回の ARC (形式のコンテスト) へぐって水色から落ちていたので水色に返り咲くのを目標にしました。
結果は C 問題に手こずった挙句 1TLE 出して 64 分かかり、601 位でした。
終了直後は C 問題に手こずって順位を落としたので若干気落ちしていましたが、パフォーマンスが意外に伸びた*1ために水色に返り咲くことができました。

f:id:y_r:20190427231009p:plain

感想

A 問題

速攻

B 問題

速攻

C 問題

一つの数字を抜かした GCM すればよいところまでは簡単に考察できたのに、ひとつずつ数字を除外して GCM する全探索を書いて TLE 。
考えてもわからなかったので D 問題を先にといた。
もどってきて複数数値の GCM は順番は関係ないことに気が付き、GCM(先頭からの GCM, 末尾からの GCM) の最大値が答えであることに気が付く。これを投げて終了。
1 TLE はもったいなかった...とりあえずだめっぽい解答をなげる癖をやめなければ。

D 問題

C 問題ができなかったので先に解いた。
一回ひっくり返すとマイナスが伝播することに気が付き、マイナスの数が偶数なら全部の数の abs の和、奇数ならそこから abs が一番小さい数を引けばよいことに気が付く。テストケースで 0 がある場合 (この場合は全部の数の abs の和が答え) のコーナーケースに気が付き、それに注意して実装、AC。

*1:1300 か下手したら 1200 程度でレート以上のパフォーマンスを取ってレートを落とすかもと予想

AtCoder Tenka1 Programmer Contest 2019 参戦記

プログラミング 競技プログラミング

AtCoder の Tenka1 Programmer Contest 2019

atcoder.jp

に参加しました。

初めての ARC 形式のコンテストでしたが、結果は C 問題に 48 分 3 WA をくらい D 問題以降は解けず...ということで 955 位パフォーマンス 1134 であえなく緑色落ちとなりました。

f:id:y_r:20190421094451p:plain

感想

C 問題

黒石を右詰めすればよいというのは簡単に考察できたが、右詰め手法で実装ミスを出して 3 WA。
最終的な AC コードは

  • left[i] 左から i 番目までを白にするときの手数
  • right[i] 右から i 番目までを黒にするときの手数

としたときに min(left[i] + right[i + 1]) が回答というものだった。

D

よくわからないので全列挙に適当な枝刈りとメモ化再帰を組み合わせたが当然のごとく TLE。
R+G < B だけに頼って R < 2/S を見逃していた。ただし考察あってたとしても DP には持ち込めなかったと思う。

E

答えの候補は a_{0} の素因数というところまでは考察したがそれ以上考察が進まず。

square869120Contest #6 参戦記

プログラミング 競技プログラミング

atcoder.jp

参戦しました。 Paris–Roubaix 見つつしかも酒が入っている状態でしたが 1865 点で 93 位。600 点問題取れたしまずまずだったのではないでしょうか。
マラソン問題はじめてでしたが楽しいですね。時間があっという間でした。ただし解を改善しようしてバグを出して改善できなかったのでもっと実装力をつけないと。

パフォーマンスも計算してくれたみたいです。

drive.google.com

これによるとパフォーマンス 1902。青領域に突っ込んでいたようです。

感想

A 問題

全部足した後で割る。

B 問題

スタートとゴールの候補は品物を買う場所しかない。全探索。

C 問題

H * W の中に

  • 1 -> H に行ける道がある
  • 横一列通れる列がある

を両方満たせば OK。なのだが 1 -> H の探索でポカ (探索済みのマスも探索していた...) をやって TLE を出す。

D 問題
  • 同じ位置にある雪玉は融合必須
  • 雪玉は大小あるときには小を動かすべし
    • つまり、融合場所はどちらかの雪玉がある位置
  • 雪玉を逆方向に動かすと確実に減点

により、初めから雪玉が配置されている位置での、左から雪玉をあつめた時の半径と右から雪玉をあつめた時の半径を計算して、和が最大になるのところをとればよい。
ただし和を計算するときには from_left[i] と from_right[i + 1] の融合になることに気を付けること。(左右から i に来た時の値は i 番目の雪玉が 2 重カウントされる)

E 問題

ぱっとみて方針がたたなかったため I 問題を優先した。

I 問題
  • 縦に一行おきに全部埋める + 適当に横につなぐ
  • 横に一行おきに全部埋める + 適当に縦につなぐ

から得点の高いものをとるという適当実装を投げつけておいて部分点を取った。

そのあと付け替えによって解の改善を試みるも、バグが取れずに改善できず...