-
×
[PR]上記の広告は3ヶ月以上新規記事投稿のないブログに表示されています。新しい記事を書く事で広告が消えます。
-
主にAtCoderで解いた問題の感想とか詰まったところとかを記録します。
自分に対する解説的な一面はありますが、解説ブログを書いているつもりは一切ありません。
AtCoder マイページ
2019/12 現在緑
シンタックスハイライトが働かなくなってしまったので、適当な無料レンタルサーバー借りてWordPressに移行予定。PR -
問題
unrated
3完
新年初競プロ&新年初C++。
コンテスト前にABCのC問題までくらい1つ解いておこうと思ったが映画見てご飯食べてたら時間なくなった。
そして2連続unrated。
unratedに気づいた後色々あってやる気を失った。
unratedじゃなかったらたぶん4完。
色々書いたけどなんか記事消えたので適当。
保存する押して保存しましたのダイアログと共に消えるの頭おかしいだろ。
忍者ブログ本当に嫌。
A問題
かんたん。
チェック段階でkとxを2回間違えてチェックした。
焦りすぎ。
B問題
もしかしてcount関数ってStringに特殊化されて文字列も数えられる???と淡い期待を抱いて実行したら普通にコンパイルエラー。
素直にループ回した。
C問題
考察実装5分next_permutationの使い方調べるの5分。
なんとなくnext_permutationは順列を扱えるくらいしか知らなかったが、知ってるのは強いね。
初めて使ってみて勉強になった。
D問題
unratedの根源。
わざわざ問題文にa[i]は偶数と書いてあったのに奇数が紛れていたらしい。
「最小公倍数は整数をかける場合の最も小さい公倍数なので、整数+0.5をかける場合の最小の半公倍数は最小公倍数の半分。半公倍数の間隔は最小公倍数。」
という考察をコンテスト中にしたが、半分間違っていた。
「最小公倍数は整数をかける場合の最も小さい公倍数なので、整数+0.5をかける場合の最小の半公倍数になる可能性があるのは最小公倍数の半分。半公倍数が存在するなら間隔は最小公倍数。」
というのが正しい。
というのも、最小の公倍数をZとおくと、Z / a[i]が偶数になるa[i]が存在した場合、最小の半公倍数となる(Z / 2) / a[i]が整数となってしまい、X = a[i] * (p + 0.5)を満たせない。
間隔となる最小公倍数のn倍を足しても必ず満たさないので、半公倍数は存在しないことになる。
ということで、基本的には(Z / 2) + nZ {n:0以上の整数}が半公倍数の数で、答えとなるM以下のものの数は簡単に計算できるが、Z / a[i]が偶数となるa[i]が1つでも存在したら半公倍数は存在しない。
コンテスト中はTLE+WAで、色々改善してTLEはなくしたが、後半15個のWAがなくならなかった。
途中で間違えてEに提出してしまったり、そもそもunratedだったりと、WAは入力ミスが原因だろうと1時間くらいで解くのをやめた。
しかしコンテスト終了後に提出してもWAだった。
改めて考察し直してみると、Twitterで偶奇が云々という記述をいくつか見ていたのもあり、最後の偶奇のチェックが必要だとすぐに気付けた。
unratedで解くのをやめていなければ自力で気付けたと思うが、ちょっと時間かかってたかも。
それでも十分時間内に間に合ったとは思うが。
E問題
やる気はなかったが方針だけは途中まで立てた。
解説を見る限り基本的には合ってそう。
たぶんその先は時間内に思いつけない。
Σa[i] * b[j]を最小化するタイプの問題なので、昇順ソートと降順ソート同士でかけ合わせれば良い。
S[i]が異なっていると置くと、残りN-1個の選び方2^(N-1)の中でC[i]が何番目に大きいかが分かれば良い。
というのをぼーっと考えていたが、進まなかった。
部分問題まで辿り着けたのは成長だが、そろそろ先に進まないといけない頃合い。
後でしっかり解説読んで理解しよう。
F問題
やる気ない中でXORの文字を見つけたので読むのをやめた。
まとめ
1年がunratedで終わりunratedで始まるのはどうなんだAtCoder。
別に文句を言いたい気持ちは全然なくて、イメージ悪くない?大丈夫?という感じ。
明日明後日と3日連続でrated(予定)のコンテストがあるので参加したいのだが、いまいちモチベーションが上がらない。
ブログの移行が進んでいないのが大きい。
詰まった部分は大体解決していて、単純にやっていないからなので頑張ろう。
保存しましたで消えるの本当に頭おかしいから早く移行したい。
・・・本当に頑張ろう。 -
あけましておめでとうございます。
年明けてから年末のコンテスト参加記事をいくつか書いたけど改めて。
とりあえずAtCoderの記録を乗せる。
去年はyukicoderも張ったが、今年はAtCoderがメインで、AOJとyukicoderはライブラリの確認とかでしか解いていないのでAtCoderだけ。
~2020/1/10
やってる時期とやってない時期が激しすぎる。
2週間に1日だけとかが何回かあるのがあんまりやってないなーって感じする。
趣味は他にもいくつかあるからずっとやるのは難しいが、もうちょっと継続的にやりたいね。
今年の目標は黄か橙。
青は(やれば)いけると思うので、その先が大事。
この記事はまた更新するかも。
-
問題
unrated
4完
初めて参加したコンテストがunratedになった。
出来はひどかったので助かった。
A問題
かんたん。
B問題
問題文読み間違えた。
問題文のGreedy Takahashiからして、高橋くんは自分も青木くんもクッキーを持ってる場合、青木くんのクッキーから食べにかかると思って実装してしまった。
普段BくらいまではACを見ずに次の問題に取り掛かるのだが、今回はCを提出した後に20/20の表示でまだジャッジ中だった。
遅くない???と思いつつもDに取り掛かり、途中でBがWAしてるのを確認。
問題の読み間違いに気づき、再度提出してDに取り掛かる。
しかしBだからと高をくくって詰めが甘くてまたWA。
今度はDを解いた後に気づいた。
最終的にACDBという珍しいAC順になった。
毎回毎回あほらしいミスを繰り返しているが、簡単なBで何度もやらかしてしまったのは反省点高い。
C問題
かんたん。
エラトステネスの篩張ったら終わった。
D問題
最近のDにしては複雑な問題だなーという感想。
K個前の値を保存してDPすれば良さそう・・・と思ったのだが、どう頑張ってもK個前の値だけじゃ遷移を進められない。
「K個前の値」じゃなくて「K個前までの全ての値」を保存しないといけないという考えから抜け出せなかった。
あるところでK個毎に独立してるのでは?と気付き、modKで分けてDPの方針が立った。
この時点で結構時間が立っており、これ以上ミスを重ねたくないとかなり安定志向の実装にしたつもりだが、modK毎のインデックスがすんなりいかずデバッグにかなり時間を取られた。
最初は出す手を数字と連想配列でうまく関連付けてシンプルな条件式にしようとしていたのだが、安定志向で条件式が長くなってしまった。
今回はミスしなかったが、長いとミスも増えるしどっちが良いのか悩みどころ。
うまく関連付ける内容は、詳しい部分は忘れてしまった。
もう去年の話だぞ。
記事書いてるのは徹夜明けの早朝6時過ぎだぞ。
最終的にACしたのが73分。
時間かかりすぎ。
聞くところによるとDPなんかしなくても貪欲で良いらしい。
ちょっと考えてみればすぐわかる話だ。
とりあえず勝てるなら勝てる手を出せば、他の順番と比べて同じ点数になることはあっても悪くなることはない。
最善が複数ある場合に貪欲で解けるっていうの慣れないとなと感じた。
これゲーム問題の分野かな。
ゲーム問題も解かないとなぁ。
E問題
去年の話なのでもうあまり覚えていない。去年の話とかいう便利な言葉。とりあえず覚えているのが、AGC 020 Cを思い出したこと。
解いていないのだが、解説をちらっと読んだ覚えがあった。
全ての組み合わせの中から、大きい方からM個を考える時、必ず満たす性質がないかというのをずっと考えていた。
しかしうまくいかずにタイムアップ。
解説PDFをちらっと見て理解した解法が、ある値を決め打つ二分探索を基本として、その二分探索の途中でさらに二分探索をする方法。
2回目の二分探索がPDFで言う「左手で握手する人を先に決めたとき、右手で握手できる人が何人いるかは累積和を用いることでO(1)で求まる」という部分で、最初この部分が理解できなかったので、方針だけ理解して二重に二分探索すればできそうだなと考えた。
制約的にはO(Nlog^2N)でも間に合いそうだが、部分問題として考えるとO(logN)からO(1)は結構大きいので、この累積和の部分を頑張って考えた。
理解はできたのだが、PDFはもうちょっと詳しく書いてほしいなー。
累積和といえば累積和だが、「V[i] = 数列中のi以上の数」と見れば良いだけで、インデックスとして考えるのではなくて値として考えるというちょっと変わった累積和だ。
だから数列中の値の最大値も重要になってくる。
こういう添字に意味を持たせるタイプの問題ずっと苦手だなぁ。
記事に書いた記憶があるが、BITの添字に意味を持たせるタイプの問題で、「こういうデータの持ち方するという発想に至るのきついなぁ。考えられるようになれるかなぁ。」といったことを書いた記憶があるのだが、やはりきつい。
次はこういう発想も道具として取り出せるようにしておきたい。
F問題
なんかむずかしそー。
完。
まぁunratedだし?という気持ちが溢れてた。
まとめ
2019年最後がunrated!
まぁ助かった。
このコンテストは自分の苦手ポイントを自覚させてくれて得られるものが大きかったように思う。
ミスをするなというのは言わずもがな。
・modKで考える発想。
・必ずしも最善は一択ではなく、そのうちの1つが分かれば良いという発想。
・累積和やBIT等、配列的なデータ構造のインデックスに意味を持たせる発想。
この3つが足りないと感じた。
modKは最近の問題でも理解に時間がかかったばかりだ。
値を決め撃って二分探索する発想はかなり浮かぶようになってきたので、この感覚を参考にこれらの発想も定着させていきたいね。
今日は2020年初のコンテスト。
参加するなら新年初C++コーディングになる。
年末年始全くやっていないので心配だなー。 -
あけましておめでとうございます。
新年初記事。
年末に記事を書きたかったけど時間がなかったのでまずは2日連続のコンテスト参加記事から。
問題
順位: 1193パフォーマンス: 1256新レーティング: 1075差分: -27
1完。
初めてAGCに参加したが、さすがに難しかった。
目覚めたらコンテスト開始してて、なんとか頑張って9:10過ぎから活動開始した。
結果論だが、Aは一瞬で解けて終わりなので最初から参加していればもっとパフォーマンス出てそう。
寝起きによる自身のパフォーマンスも含めて。
A問題
直近のABC148 Fとすごい似てるなーという第一印象。
偶奇があっていれば2人とも全て勝ち続ければ出会う。
偶奇を合わせるためにはどちらかが同じ場所に留まる必要があり、端でしか留まることができないので、端に近い人が端に行って1回留まれば良さそう。
普通にAC。
考察から実装まで5分ちょっと。
寝坊のせいで20分になってしまった。
B問題
この問題を2時間近く考えて結局解けなかった。
解析的に解け・・・ない。
二分探索でき・・・ない。(!)
二分探索に使うような関数で全問題に対して可能かどうか走査・・・いけそう?
というような流れで、計算量抑えつつなんとか実装できないか色々してたら解けなかった。
二分探索の発想に至るのにおそらく1時間以上かかったのはまだしも、そこからダメの判断を下したのは非常にbad。
単調増加であるという判断ができなかった。
PやVの値によって場合分けしていたのだが、場合分けしていることが問題を必要以上に複雑にしてしまった。
よく考えてみると、ある問題Xが可能であるとすると、問題Xよりスコアが大きい問題Yと問題Xの選び方を入れ替えると、Yを選ぶことが可能となる。
ただそれだけなのに、何点入れればある問題を選ぶことが可能で、残りの点数はどのように振り分ければ他の問題がある点数以内に収まるか、ある点数以内に収まるようにすると点数が余る場合はどのようにすれば良いか。
こんなことを考えていた。
ある問題を選ぶことが可能であるかどうか知りたいだけなので、M人全員が1点ずつ選ぶとして良い。
それに気付けなかったのが敗因。
C問題
ややこC。
問題文とドミノの配置を理解するのに相当時間がかかった。
偶数(偶数は色々便利そうと考えた)で一番小さい4×4について手作業で考えてみようと思ったが、それすらちょっと考えただけでは分からなかったので、その先は無理だろうということでBに専念。
ただ実際には、苦労してでも4×4を実装することが本筋だった。
マス目が小さい値でクオリティが同じものを構成すれば、後はそれらを組み合わせて対角線上に配置すれば、全ての行列でクオリティを保ったままになる・・・なるほど。
2の場合は不可能、3の場合はクオリティ1を作成でき、4, 5, 6, 7の場合はクオリティ1は作成できないが、クオリティ3のものを作成でき、4, 5, 6, 7があれば8以上は全て作成できるのでこれで考える必要のある構成は全て。
相当パズル要素強い。
競プロの大部分を占めるであろう数学系とかシミュレーション系しか解いたことがないので、こういった問題は面白いと感じるが、さすがに引き出しがなさすぎるからその方向に考えを移行できない。
もっと余裕持って問題解きたいねD問題以降
見てまーーーーーせん。
ABCなら解けなくてもコンテスト終了後に解説見て云々あるのだが、解説すら見ていない。
ちょっとレベルが違いそうで解くのはいつになるやら。
まとめ
初めてのAGCだが、一応レートは上がったので変な苦手意識を持たずに済んだ。
B問題はdiff水色だし解けても良かったなー。
また原因を寝坊に求めることもできるが、そもそも最近まともに頭働いていない状態からコンテストに参加することが多くて反省している。
起きてから本稼働開始までに3,4時間かかる人間なので、本来ならもっと早く起きておくべきなのだが、年末だしねということでひとつ。
年内目標だったブログの移行はまだ少しかかりそう。
水色もブログの移行も年内無理だったかぁ。