今日は幅優先探索。まだ途中なので続きは明日。 28 ALDS_11_C - 幅優先探索 毎度おなじみALDS。これはサクッと解けた。 29 AtCoder Beginner Contest 007 C - 幅優先探索 この問題前もやったんだけど、まあいいや、もう一度やった。グリッドを移動する系の問…

最近忙しくてあまりできていなかったのだが今日はやります。深さ優先探索(Depth First Search)。正直DFSは何というか単純すぎてあまり好きではないのだが。全4問、順に所感を書いていきます。 24 ALDS_11_B - 深さ優先探索 ALDSの問題は基本アルゴリズムの実…

昨日の分です。最近遅れ気味なのは反省してます。。 先日 23 JOI 2008 本選 3 - ダーツ でなぜかTLEになった問題。結局コンテナとしてsetを使っていたのをvectorに直したら制限時間内に計算できたのだが、そこで コンテナ毎に実行時間にはどの程度差があるの…

昨日から二分探索に取り掛かっていたのだが記録していなかったので、併せて書いておく。23だけはまだ途中。 18 ALDS_4_B - 二分探索 upper_boundを使えば一発。時間制限が厳しければ他の方法を取るけれどここはそれで十分。 19 JOI 2009 本選 2 - ピザ 本店…

昨日書いたのに投稿し忘れましたorz 以下原文ママ↓ 昨晩のABC199の結果、ついに！ 緑Coderになることができました！ やったね！！ そして水パフォ！これもうれしい。最近力がついてきていた実感があったのでそれが確かめられてよかった。 具体的な回答状況は…

昨日大苦戦したnext_combinationは結局諦めて他の人のコードを写した。もう少し力をつけてからまた見返してみることとする。 今日はまた一昨日の続きに戻る。Q14~17にトライ。 14 Square869120Contest #4 B - Buildings are Colorful! 早速上記のnext_combin…

昨日の流れからいくと今日は14. Square869120Contest #4 B - Buildings are Colorful!からという話になるのだが、これを実装するのにあたり配列を並べ替えて全通りのcombinationを列挙することができたら楽ではないか？？と思い、next_combination関数の実装…

昨日ノーマル全探索を終えたので今日はbit全探索を。bitを用いた実装は初めのころは「ここは&だっけ|だっけ？」みたいな感じで大分手間取った記憶があるのだが、その点かなり慣れてスムーズにできるようになってきた気がする。でもまだ典型的なもの以外は少…

今日は6~9を。昨日の分よりはやや難易度が上がったが、この程度ならまだまだいける。 ただもう少し早くできたら理想かな、という気もする。結構添字とかで「あれここはa[i]だっけ？a[i+1]だっけ？」とかなってタイムロスをしている感。あとはループの範囲と…

昨日見つけたこちらの記事。 qiita.com 水coderになるためにはとにかく演習！ということや、そのためには片っ端からというよりは選ばれた良問をやった方が良い、ということが分かってきたので、この記事に出ていた良問100選を順にやっていくことにした。 と…

本日二つ目の投稿。二つやると結構大変だけど昨日忘れた自分が悪いですねはい() 一言で言えばこんな記事を見つけましたと言う話。 qiita.com 初級編〜上級編とあるが、現在茶コーダーで水を目指す自分として役に立ちそうなのはこれ。具体的に何をやったら良…

昨日書き忘れましたねはい。ので今日二日分書きます。 まずは先日の最強学生プログラマー選手権(だっけ？)のE,F問題を軽く振り返って。まずF問題は座標圧縮が必要になってきそうなので明日学習しようと思う。ちょうど良さげな問題も見つけた。 atcoder.jp ん…

タイトル通り。実は予定があって17:30までしか参加できないのでかなり迷ったのだが…。参加を決めた理由としては、まあこれが原因でRatingが下がるということはないだろう、というのと、単に一刻も早く力試しがしたかったのと。結果はご覧の通り。 短い時間で…

結論から言うと忙しかったので今日はほとんど進められていない。。ABC197-Fに取り組んだがWAになり、原因不明のまま。そろそろ自力は限界なので、他の人のコードを読んでいい所を盗む形でやりたい。 3分の1(10日間)ちょうど経過したので、少し今までを振り返…

昨日の続きということで、今日はEとF問題。これらは完全にアルゴリズムを思いつかず解けなかった。どういう発想が必要だったのか考察してみる。 E - Traveler 「同じ色のボールをどういう順番でとるかがカギだな」「各色について、取り方は高々2通りしかない…

昨日ABC198は一通り復習し終えたので、今日は1つ前のABC197に取り組んでみる。残念ながら100分というまとまった時間は取れなかったので、時間は正確にははかっていないが、多分100分以内に4完したと思う。EとFはまだ途中なので、CとDを先に振り返っておこう…

一昨日大敗したABC198について、昨日は全体的な課題点を考察したが、今日は個別の問題について見ていく。Fは今のレベルではかなり無謀な問題なので、大きな敗因だったDとEの失敗について。 D - Send More Money atcoder.jp 覆面算の問題。これに関しては解け…

昨晩ABC198に参加した。今日新Ratingが出たが、結果は火を見るより明らか。 死にました。 具体的にはこのような結果に。 まさかの3完どまり、パフォも過去最低、という惨敗ぶり。5完目標にしてこれとは情けない限り。悲しんでいても埒が明かないので、以下反…

まずは昨日の復習の続き。 D - I Wanna Win The Game atcoder.jp (本題とは逸れるが、このタイトルはどういう意味が込められているのだろうか…？深い意味があるのかはたまた何の意味もないのか。) 出ましたXOR。苦手なんだよな、、と思いつつも成り立つ性質…

最初はABCをやろうと思っていたのだが、時間もあるのでARCにチャレンジしてみた。 結果はご覧の通り。 400点問題と500点問題の間の壁はやはり高かった。A,Bは(若干苦戦しつつも)解けたが、C,Dは全く歯が立たず、途中でギブアップ。以下解説を見て再考。 C - …

今日は時間がなくてあまりできていないのだが、尺取り法の復習だけ少し。 尺取り法 (two pointers technique) 個人的にはtwo pointersというネーミングの方が分かりやすい感。条件を満たすような最長の区間[l, r)を求めるにあたり、lとrのうち片方を固定、片…

昨日のE問題 E - Transformable Teacher を再考するため、以下の記事を読んで参考にしてみた。 rsk0315.hatenablog.com いくつか学んだことを↓ 累積和はs[0]=0とする これは早速このE問題で使えた。半開区間をベースに考える、という発想らしい(s[0] = [0, 0…

まずは昨日のABC182-Fがまだ実装途中だったので、その続きから。 ついでに、mapにおける演算子[]の使い方を確認。 これがなかなか便利で、 map<string, int> mp; mp["Alice"] = 18; のように用いるのだが、もし該当する要素が存在しなければ自動でデフォルト構築してくれ</string,>…

1日目。 とりあえずAtCoderの過去問を片っ端からやっていき、分からないことが出てきたらその都度調べる…という方針でやっていくこととする。 まず手始めにABC182を解いてみた。100分かけて、バーチャル参加機能を使ってみる。 結果はこのような感じ。 A 0:5…

こんにちは。だぬーくです。 結論から申し上げますと、1カ月だけ競プロに本気で取り組んでみようかなー、と思ってこのブログを始めた次第です。 自分は元来飽きっぽい性格でして、大体何事も長く続かないんですよ。 競プロも、今までに何度かやろうかなーと…