ABC169参加記
色変記事のためにブログを開設したので、そのまま参加記も書いてみようと思います。
問題B
入力から
をかけた値が
以下であればその値を、そうでなければ-1を出力する問題でした。
であるため0が含まれている場合に注意が必要でした。
まずソートして0を前に持ってきてから、前から積を計算していきを超えたら-1を出力して打ち切る実装にしました。
問題C
入力Aが整数、Bが小数で小数第二桁まで与えられ、これらの積A*Bの小数点以下を切り捨てた整数を出力する問題でした。
今回のコンテストで一番苦労した問題で11ペナでした。
浮動小数点数の理解が足りていなかったです。Bをfloatで受け取った時点で誤差が生じてしまうということだったようです。
最後のほうでdecimalを思い出し、あまり良くわかっていないながらも使ってみたことが功を奏しました。
問題D
Cが解けていなかったので問題文の理解に時間がかかりましたが、素因数分解すれば良いことに気づきました。
入力Nがであり素因数分解の計算量が
であることから方針として問題なさそうであることを確認しました。
問題E
とり得る中央値の個数を出力する問題でした。
まともに証明はしなかったですが、取りうる中央値の最小値と最大値がわかればその間の値も中央値になれるだろうと考えました。
提出コードでははじめに全ての数を2倍にして中央値として小数が出ないようにしたのですが、奇数の場合は中央値は整数にしかなり得ないことに気づき結局また2で割っています。
問題F
問題が読み取りづらかったですが、制約を見るとdpの感じがしたのでその方針で考えていました。
まず、
dp[i][j]:=i番目の数まで見た時に総和がjとなる組み合わせの個数
というのが思いつきましたが、ほしくなるのは何個足すとjになるかという情報であり、このままではうまくいかないなと思いました。
絶対NとSの2重ループで解けると信じて考えているとから初めてどんどん2で割ったものを足していく更新方法ならそれっぽいのかと思い、試すとサンプルと合ったので提出しました。
更新の途中でmodを計算するのを忘れており何回かTLEになりましたが、なんとかACを得ました。
おわりに
コンテスト参加中のことを思い出して書いてみましたが、適当に考えてしまっているなと思いました。
また、途中からやけになってペナを気にしなくなってしまったのですが、かなり良くなかったのでもっと落ち着いてやっていきたいです。
AtCoderで青色になれました
はじめに
はじめまして。reborn18です。
ABC169によりついに青色になれました。
これまでにやってきたことを書いてみようかと思います。
茶色になるまで
2年前くらいに周りで競技プログラミングが流行り出しました。そのとき僕が使えた言語は授業で習ったCとPythonであり、とりあえずCでやり始めました。
しかし初めて出たABCではAしか解けずやる気をなくしてしまいました。
約1年後に2回目のコンテストに出るのですが、あまりきっかけを覚えていません。ただ、やはり悔しさがあったのかなと思います。
緑色になるまで
この頃からPythonを使うようになります。理由としてはスマホで参加することが多くなり、CやC++よりも比較的短く済む方が都合が良かったからです。結局今に至るまでPythonを使っています。
緑色になるためにアルゴリズムの勉強をしましたが蟻本を使っていたわけではなく、過去問を解きながら知らないものがあれば勉強するような形だったと思います。
個人的には幅優先探索をソラで書けるようになったのが成長を感じ、嬉しかったです。
水色になるまで
この頃から毎日何か問題を解こうと思うようになりAtCoder ProblemsのStreakを切らさないようにしていました。これは今も続いています。
最近は解ける問題が少なくなってきたため解説ACなども多くなりがちですが、AtCoder以外にも問題を提供しているものはありますし、もったいないという感覚はありません。
少なくとも何もやらないよりはマシだと思うことにしています。
青色になるまで
続けていくうちに青パフォで安定するようにいつか青に行けそうだなと思えました。
正直新しくアルゴリズムを勉強したということはなく単純に慣れたのだと思っています。
制約からアルゴリズムを絞ることができたり、なんとなく見たことある問題で方針がすぐに定まったりという感じです。
おわりに
地道に精進を続けることでAtCoderを始めた時の目標である青色にたどり着くことができました。
これからも続けていきたいと思います。
ここまで読んでいただきありがとうございました。
