📘

AtCoderコンテスト参加記

2020/10/04に公開

ARC107 出来はぼちぼちだったが、緑が見えてきて嬉しかった回

ARC 107
A. (Aまでの和)(Bまでの和)(Cまでの和)
B. x=a+b, y=c+dとしてx-y=kとなるx,yの場合を列挙して、それぞれの場合に、(a+b=xとなるa,bの場合)*(c+d=yとなるc,dの場合)を足しこむ
Cは行と列の独立性みたいなのが全く直感的に感じられなくてわかんねって感じだった。慣れておきたい
https://atcoder.jp/contests/arc107/tasks/arc107_c
そもそもゲームが分からない系でいうと
https://atcoder.jp/contests/arc105/tasks/arc105_d
これとか。

ABC180 ラスト1分でD問を通すが実はD早解きだった回

ABC 180
A. print(n-a+b)
B. abs(x)の配列を覚えてsum,二乗のsumのsqrt, maxをそれぞれ
C. 約数列挙
D. 5WAでAC. dpでやろうとして1WA, カコモン→atcoderの順に貪欲に行けばいいことに気づいて愚直にやってTLE. どっちでもいいから常に小さい方を選んでいけばいいと思ってそれもTLE
カコモンジム→atcoderジムで貪欲にやればいいことに気づいて愚直にやってTLE. その後カコモンジムに通える回数をwhileで持ってそのあとO(1)で求められることに気づいた。しかしそっからコーナーケース通せないマンが始まってしまった。条件がうまく整理できてなかったな。こういうの焦るとだめだな。
整理が甘かったのもあるが、「強さが Y 以上にならないように」という条件がちょっとややこしくて脳内バグった感はある
解説みたいに単純にやればよかったものを、B/(A-1)以下ならば・・・みたいな余計な変数を持ち出してしまったので面倒なことになった。

C問題を約数列挙のコードをググってコピペして解いた罰ですかね。Dでバグらせまくったのは。

ARC105 ユークリッドの互除法

ARC105
A. 気合で8通りループするみたいなことをやったが、ソートすれば一発だったか。
B. 具体例いじっててとりあえず最小値で配列の全要素を割るという動作をやりつづければ求まるなーと思った(mで割ったあまりが0になったらmで置換する)
解説読んだけどこれgcdを求めればいいだけか。といいつつ、よく考えたらこれユークリッドの互除法やってるのと同じか!勉強になった。
ユークリッドの互除法周り、永遠によくわかってない
Dも少し考察した。解説を読んでもよくわからない。こういうゲームで最適手を打っていくみたいな問題解けたらいいな。少しずつ勉強していこう。

HHKB C問レベルの計算量とかコーナーケースの考慮が足りない

HHKBコン2020
A. t.upper()
B. 行ごとにみて列ごとに見てそれぞれ連続した"."の区間ごとに場合の数
C. TLE連発からのAC. 各数字の出現回数を配列で持っておき、最初の0のidxを出力。idxが広義単調増加でidxの走査をO(N)にできる。0の要素を探し始めるときは前回の0の位置から探せばよい
D. WA.とりあえず定数超場合の数ゲーだということは分かった。解説を読んでやっぱりと思った。場合の数苦手なんだよなあ

いやこれはしょうがないですね Cが秒で見えてなかったのが悪いので あと場合の数算数レベルで苦手なので困ったな。 もしかしたらEに取り組んでいたほうが良かったのか?などと苦しい言い訳も書いておきます
いや~~気にしない気にしないと思いつつ、しんどいっすわこれは 明日のARCやっぱ出るか~~?いやそれはやめとこ また次回までのんびり精進しよう

ていうかコンテスト後の良く分からない反省会の時間が長いな その時間あればさっさと復習ACすればいいのに。。。
主催会社のキーボード使って出たのに激悪パフォでした、申し訳ない気分
p.s.
その後D問題を解説になぞってACした。
正方形→対称性に目を付ける、区間が重なる場合→区間が重ならない場合に視点を移せたらよかったのかもしれない。

kupc2020 乱択とかいう世界飛び込んでみたさある

kupc2020
A. 愚直にシミュレーション
B. 二分探索+累積和
C. とりあえずN=5で部分点。途中からなんかランダムに出力してれば当たんねーかなとか思って試行錯誤。結局乱択で行けるらしいが、乱択も勉強してみたい
D. N=偶数の時、Nがあるx**2で割り切れるときまでは分かったけどそこまで。

440点、237位 前後に水色青の人もいっぱいいるしここら辺まで解ければ十分か、、、

ARC104 難問にチャレンジしつつ、堅実なパフォは出せた

ARC104
A. (A+B)//2と(A-B)//2
B. A,G,C,Tの個数に関する累積和をもっておいて、O(N^2)で探索
pypy3で個数をdict型で持ったらTLEした。多分参照するときにO(N)余計にかかったりするのか?配列で持ち直したら通った。
C. わけわからなかった
D. とりあえずDPを使いそうなことはわかった・・・

なんとか二完できたのでよかった!C,Dは無理そうだったな。Cがわけわからんくて、ふと順位表を見たら上位の人たちがDから先に解いてたからDならワンチャン解けるんじゃね?とDをずっと考察していた。

一応Dはがんばって考察したので写経などしつつ復習してみるというのもいいかも。

Discussion