プライバシーポリシー
第三者に個人を特定できる情報を提供することはありません。個人情報の管理には細心の注意を払い、以下に掲げた通りに扱います。
アプリの利便性向上のため、匿名で、個人を特定できない範囲に細心の注意を払い、アクセス解析をしております。例えば、アプリがクラッシュした時、どの部分でクラッシュしたかを匿名で送信し、バグの素早い修正に役立たせております。
また、デバイスやアプリバージョンの使用率、特定の機能の使用率などを解析し、アプリの改善に役立てています。(例えば、より使われている機能の改善を優先的の行うなど)
※ご不明な点があれば、お気軽にお問い合わせください。
2h.chitanda.eru@gmail.com
タスク日記 8/1
現状抱えているタスクと解決期限を書くだけの記事です
①校内模試
某塾の校内模試 9-10月は勉強ができない(と思っていい)ので、模試の結果をあげるとか以前に受験勉強をしなければならない
②脳科学
なんだかんだで優先度は高い、brain beeに出るとしたら英語のテキストを読まなければならないので、射程に入れていく感じで
とりあえずはPCKを目標にしていきたいが、今の実力だと同一高制限で切られる以前に実力で落ちるので、夏休みで実力を盛る やるぞ
とりあえず模試で80位以内、brain beeのテキストを読む、AtCoderレート1800を夏休み中に達成するぐらいのつもりで頑張っていきたいと思います、これくらいできれば有意義な夏休みと言えそうなので頑張ります
千反田えるのAC録[ARC096 D - Static Sushi]
いよいよ8月ですね。というより、もう8月に入ってしまいました。夏休み夏休みと言いますが、往々にしてあっという間に過ぎ去っていくものです。限られた時間を有効利用できるように、考えながら過ごしていきたいです。
問題
D: Static Sushi - AtCoder Regular Contest 096 | AtCoder
考察過程
一度解けなかった問題なので解説は見ており、そのためそんなに苦戦しないと思ったのですが、予想通り(?)実装で苦戦する形となりました。こういう問題は直感的に理解しても実装が難しくて敗退、みたいなことが本当によくあるので気をつけていきたい。
解答
千反田えるのAC録[AGC A - Sorted Arrays]
Aにもかかわらずコンテスト中、コンテスト後合わせて9WAの問題児。
問題
A: Sorted Arrays - AtCoder Grand Contest 013 | AtCoder
考察過程
どこかで何らかの基準で区切ればいいことはわかっていた。が、
・単調増加した後は絶対に単調減少の数列が来ると思っていた
この一点の勘違いにより状況は一変。大量のWAを生産する羽目になりましたとさ。
その後も細かい実装で詰まる場面が多かったですし、教育的にいい問題だとは思います。
答え
千反田えるのAC録[JOI 2008 本選 B ピザ][JOI 2007 本選 C ダーツ]
数日競技プログラミングができていませんでしたが、どうにか2問解くことができました。
JOI 2008 本選 B ピザ
考察過程
任意の配達地点は2つの店に挟まれているので、lower_boundとかを使って店の方をソートしてしまえば終わり。難しくはないと思います。
答え
Submission #2904028 - 第８回日本情報オリンピック 本選（オンライン）
JOI 2007 本選 C ダーツ
考察過程
こういうDPっぽい問題、マジで苦手なんですよね...
とりあえず1-4本全部調べれば通るな、とか思って適当に実装しましたが、最後の方で、あれですね、半分全列挙の時に使うテクを使って解いたら解けました。
とはいえめんどくさい実装してバグのオンパレードだったので反省。
答え
Submission #2904137 - 第７回日本情報オリンピック 本選（オンライン）
千反田えるのAC録[ARC070 D - No Need]
夏休みに入ったので、こちらもだいぶ暇です。夏休み中は1日1AC以上を目標にコツコツ頑張っていきたいですね。
問題
考察過程
普通に難しかったです。これ初見でわかる人天才では？
自分は自力実装こそしたものの、答えを見てどうにかの実装となりました。
恐らくですけど、部分点の考察までは割とスムーズにいくんですよ。
この時点でDPを行う必要があるわけですが、高々5000までの和が作れるかどうかの判定ができればいいことに気付けるかどうかでまず一苦労だと思います。
細かいところは公式解説に譲りますが、とにかくk-a[i]<=a[i]以外で作った和<kを達成するものが一つでもある時点でそれは必要な数、ということになります。
これをすべてのa[i]に適用することで部分点を獲得することができますね。
で、満点解法なんですが。さすがに累積和を使って解く方法は思いつかなすぎると思ったので、素直に二分探索をしました。そもそもこの二分探索を使う方法すらほとんど思いつかないと思うのですが。
数字が大きくなるほど必要になっていって、小さくなるほど不必要になっていく、というところは感覚でわかると思います(だって0はどう考えても不必要ですし5000はどう考えても必要でしょう?)が、必要と不必要の間に境界が存在し、二分探索ができるというところに関しては直感的に分かりづらいと思います。
二分探索は個人的にはバグの温床だと思っています、あまり書きたくはない。今回も二分探索の実装で盛大にバグり散らかしました。
感想
難しいです。が、テクニックは平凡なものの集まりなのでしっかり実装できるようにしていきたいです。
コンテスト参加記録[ABC103]
今回はABConlyということでARCではなくABCに参加してきました。
では、一問ずつ問題を見ていきましょう。
A
https://beta.atcoder.jp/contests/abc103/tasks/abc103_a
普通に最大値から最小値を引いてやればいい問題。リジャッジこそありましたが、終わってみればAにはちょうど良かったと思います。
B
https://beta.atcoder.jp/contests/abc103/tasks/abc103_b
string sを任意の位置から見ていったときにtと一致するか、という問題。こういう時は
下手に割るよりsの後ろにもう一つsをくっつけた方がバグりにくいと思うのですがどうでしょうか？こうするとsubstrも使えるので。実際は普通に２重ループを回しました。
C
https://beta.atcoder.jp/contests/abc103/tasks/abc103_c
本コンテストの息抜き場。一見難しそうに見えますが、全要素の最小公倍数-1をmとおくことで、すべての要素に対して余りが最大化されます。m自体を求めることは不可能ですが、求められているのが余りの合計なので、全要素を合わせてから-Nして終わりです。N<=3000なので計算量を誤認して考察しがちだと思います。実際やりかけた。
D
https://beta.atcoder.jp/contests/abc103/tasks/abc103_d
相変わらず難しかったです。このレベルを10分以内に解けないと黄色は厳しいんだろうなと。頑張ります。
まあ振り返ってみればそこまで難易度は高くなくて、
①始点で昇順ソートして、
②前から始点を見ていってそこを現在地とし、
③現在地が終点の最小値を超えたところで橋を落とす
...みたいなことをすれば解けると思います。簡易証明ができず解法に自信が持てなかったのと、最初終点の最小値を何をトチ狂ったかvectorで取っていちいちソートしていたので当然TLE。みたいな感じでグダグダでしたが、とりあえず制限時間内にACはできました。
総評
基本的に400-500が安定しないと黄色に行けないとはよく言われることですが、本当にそうだと思いました。夏にこのあたりを安定させていきたいですね。
