ICPC2019国内予選にwe regret to inform you...というチームで参加しました。3完86位という結果で完全に実力不足ということで納得していたのですが、ホスト校枠の関係で85位の慶応のチームがアジアに行く見込みらしくてwe regret to inform you...という結果…

atcoder.jp いつも通り自明早解き青パフォだった。そろそろ黄パフォが欲しいなということはずっといっているが、実力が付いてきていない。 CかEは解けるべきだった。なんだかmodの逆元の扱いが頭の中でまとまっていなかった。

judge.u-aizu.ac.jp 時間を逆から辿り、連結であれば最小全域木を構成して、状態を保存する。ただし、遡る過程で連結でなくなった場合には状態をリセットする。 連結でなくなったときに建設を止めるというところの認識を間違っていて、後々連結になったら建…

judge.u-aizu.ac.jp まず本を読み終わる時間を最短にするには一人目が所要時間の長い順に本を読み、二人目の子供は二冊目から同様に読めば良い。一人目が一冊目を読む間に、二人目が二冊目以降を読み終わらない場合は最適性は明らか。全て読み終わったあとに…

judge.u-aizu.ac.jp 実装するだけなのだが、次数が1の場合に来た道を戻る処理を書いていないことに気づかずにデバッグに時間をかけてしまった。こういうのは本当に良くないので反省したい。 judge.u-aizu.ac.jp

atcoder.jp 開始直後にたまたまTwitterを見ていて、ABCの形式が変わっていたことを知った。Ratedになったので久々に参加した。 問題は速解きという感じで難しいものはなかった。最近のABCはあんまり典型的なアルゴリズムを使うような問題もないので、特にICP…

judge.u-aizu.ac.jp AOJ-ICPCで500点までの問題のICPC国内予選過去問は概ね解いたが、バグも多いし時間もかかってしまっているので、この辺りの難易度で模擬国内やアジアの問題を少し解いていきたいと考えている。 この問題は一見すると幾何問題だが、実際に…

judge.u-aizu.ac.jp オーバーラップしている面積を全組み合わせについて計算して、重なりがある場合について面積を重みとして持つ辺でグラフを作れば、次数が高々2なので全探索で最小の表面積（重みの和が最大の連結部分グラフ）を探せば良い。 幾何問題なの…

judge.u-aizu.ac.jp なぜかF問題だが、すごく簡単な問題があったので寝る前に解いた。ちょっとバグらせたので30分くらいかかったので何も言えないが、これはC問題くらいでも良い気がする。Python使って解いたので、他の言語だと色々考えないといけないことが…

judge.u-aizu.ac.jp 問題を見てすぐにDPっぽいということが分かる。使用した最小金額を値として持つということが自然なので、すぐに思いつく解法としては[店の数]×[500円の数]×[小銭]が考えられる。なので通るかと思い、実装した。色々とバグらせてしまい、…

judge.u-aizu.ac.jp まず問題を見た時点でDPだということが分かる。そして、制約がなので、がくらいになることがわかる。 想定解法はおそらく場合分けしてDPと全探索の二通りの解法で書くんだろうなと予想していて、実際に講評の解法の1個目はそうなっていた…

judge.u-aizu.ac.jp 島の数がnで橋の数がn-1の連結なグラフなのでサイクルが存在しないということが分かれば簡単な問題。次数が1の島には行かないで橋を撤去するだけ、次数が2以上の島にはいって帰ってきて橋を撤去する、という時間を合計してから次数が1の…

judge.u-aizu.ac.jp ブロックが樹上になっていることがポイントで、一番下から再帰的にブロックの配置を表した木を作り、重心も再帰的に計算する。 このくらいの実装量になると自分がバグらせることは目に見えていたので出来るだけ書き始める前に構成を決め…

judge.u-aizu.ac.jp 基礎的な幾何問題。問題文を読んで簡単そうだと思ったのだが、実装に無限に時間をかけてしまった上に凄くバグらせた。実装を始める前に構成は軽く考えていたのだが、考えていなかったコーナーケースへの対応などでどんどん酷いコードにな…

judge.u-aizu.ac.jp E問題だが、かなりシンプルなメモ化再帰で解ける問題。状態数は任意のサイズの長方形なので、だいたいくらいになって間に合う。実装は30分ほどでできていたのだが、境界をミスしていてデバッグに時間がかかり40分強でAC。 ICPCのD、E問題…

judge.u-aizu.ac.jp 街（この問題ではスタート地点および汚れた床）の間の距離を求めるのにBFSしないといけないので面倒だが、それさえやってしまえばTSPを書くだけの問題。TSPについては停止条件でスタート地点に戻る必要がない点について注意が必要。 実装…

judge.u-aizu.ac.jp 鉄道の最小コストを計算する問題。駅数が少ないのでワーシャル・フロイド法が使える。まず、会社ごとに各駅間の最短経路をワーシャル・フロイド法で計算し、対応する運賃も計算する。次に、各駅間の運賃を全会社の運賃の最小運賃として初…

judge.u-aizu.ac.jp 久しぶりの競プロになってしまった。リハビリがてら、解法が簡単だけれど実装するのが面倒で放っておいた問題を解いた。 幅優先探索をするだけの問題だが、左右の足ごとに距離を持つことを実装している途中で失念して、その他ゴールの処…

codeforces.com 簡単な問題の速解きといった感じの問題セットで、Div. 3としては理想的なんじゃないかと勝手に思った。アルゴリズムというよりもプログラミングの問題だった。 Eを飛ばしてFを解いた時点で40分程度残っていて、立ち回りとしては悪くなかった…

codeforces.com 明らかに難しくないD問題を落とした。まだ見直していないので、原因がわかったら更新する。 しかし本質的な敗因はB問題に時間をかけてしまったことだった。最初に嘘解法を思いついてしまったせいで1WAをしたうえで時間を使ってしまった。こう…

atcoder.jp C問題に異常に時間がかかってしまった。確かに言われてみれば二分探索問題でしかないので、これが思いつかなかったのは反省したい。 僕の解法は想定解法とは違って、O(Q)で走る。詠唱を逆順に読んでいき、左端と右端についてこの段階でこれより左…

atcoder.jp 約一年半ぶりのAtCoder参加。結果としては2完だった。悲しい。 A問題は、A問題としては難しいなと思った。解法は想定解法通りだった。14分かかっているけど、とりあえず良いということにする。 B問題に異常に手こずった。想定解法は綺麗に解いて…

judge.u-aizu.ac.jp permutation(10)ができるので、数え上げるだけの問題。実は、少し前にコードは書いていたのだが想定以上に実行時間がかかってしまい通すのを諦めていた問題。 良い機会だったので遅くなっている部分を調べてみたところ、mapがボトルネッ…

judge.u-aizu.ac.jp 1週間ほど春休みがあり、他の大学の研究室にお邪魔をしていた（ということを言い訳にした）ので競プロをサボっていた。 その間にチームメイトにaoj-icpcの問題数を抜かれてしまったので、簡単な問題を解いて問題数を水増しすることにした…

atcoder.jp 予定があるので出場できるか分からないが、近いうちにAGCがあるので前回のAGCを解くことにした。順位表を見る限り、問題はかなり難しいということが分かる。ひとまず2完を目指したが、結果としてはA問題しかできなかった。 A問題は5分くらいでAC…

codeforces.com 今日から10日ほど予定があって競プロのコンテストに参加できなさそうだったので、朝4時5分開始だが頑張って参加した。 A問題は見返したら17分もかかっていた。寝起きなので許してほしい。 B問題はどちらもできる人を1番目のグループに何人配…

atcoder.jp 競プロを再開してから初めてABCで解けない問題があった。悲しい。 C問題は書くだけ。しかし10分くらいかかった。 D問題が解けなかった。DPかなと思ったのだが制約が厳しくて愚直な方法では通らない。そこからDPを効率良くできないかと考えてしま…

codeforces.com A、B、Cはpretestが通ったが、Cがhackされてしまった。C問題は本当に計算量が大丈夫なのか少し自信がなかったが、WAでhackされていたので不思議に思って確認してみると、iとjを書き間違えている部分があった。なぜprerestに通ってしまったの…

judge.u-aizu.ac.jp ABCの問題は実装練習として進めていくとして、問題としては少し簡単なので問題を解く力が鈍らないようにICPCの問題もたまに解き進めていこうと思う。 10種類のアルファベットを全探索しても通りで、式中のアルファベットの個数は100個以…

codeforces.com まず、コンテスト中にunratedが発表されたので悲しい気持ちになった。しかし結果としてC問題までしか解けなかったので、レートの変動はほぼなかったと思う。いずれにせよ悲しい。 A問題は出場できない生徒の数だけ学校を作る。12分。 B問題は…