2016/3 Solved (1)
3/1
3/2
Educational CF #9に参加
ABの2完。Cで悩み続けた。Dは後で見たら出来そうだった...
再帰を使ったDFSをしながら、根からの距離を更新しつつ、最短でない辺が見つかったらそこがループを構成する辺になることに気づく。その際に親と間違えないようにdfsの過程ではずっと親を保存しながら進めていく(submission)。
3/3
前に似たような問題(これ→yukicoder No.85 - TVザッピング(1))を見たことがあったので考察はそんなに難しくなかった。
この問題では、始点と終点が一致している必要はないので、全てのマスを1回ずつ通るだけなら左上から左右にジグザグにいきながら下へ進むような方法で実現出来る。2回以上になると話は別で、全てのマスに均等に訪れる必要がある→一筆書きでスタート地点に戻ってこれるような巡回路が存在というように考えて、そのような巡回路は縦か横が偶数なら存在することは実験してみるとすぐわかる。
3/4
CF #344(Div2)に参加
ABの2完。Cはrの範囲の単調減少部分だけに注目してソートした列を左と右からつめていく方針は合ってたのにループを逆からなめてしまうという超くだらないミスで落とした...
- GCJ Qualification Round Africa 2010 A - Store Credit
- GCJ Qualification Round Africa 2010 B - Reverse Words
- GCJ Qualification Round Africa 2010 C - T9 Spelling
3/5
ARC 048に参加
ABの2完、Cは解説聞いてなるほど〜〜ってなった。かなり考察に比重があった。
3/6
まず根からの距離は普通にBFSすれば分かる。次に葉からの距離だが、まず根からBFSをする際にどの頂点が葉であるかを調べておく(最短距離の更新が一度も起こらなければこのように各頂点の距離が等しい木ならその頂点は葉になる)。葉はいくつか現れるが、それも根からのBFSの時と同じように最初にすべてキューに入れておくことでそのあとの処理はほとんど同じようなものになる。最後にそれぞれの小さい方を出力して終わり(submission)。
この日からコーディングのスタイルをちょっと変えて、for,whileやifなどの中括弧を段を分けて書いてみることにした。昔は中括弧に1行使うのムダじゃん、とか思ってたけどこっちの方が見直す時に括弧の対応が明らかになりやすいので、見通しがいい感じがするという感じで、やはり2,3年ずっと親しんできたスタイルを変えて若干違和感はあるけど、これに慣れていきたい。
3/7
N以下の素数のリストを用意しておいて、素因数分解の高速化を試みる。
頂点と残りコストを持って最短経路を計算。ダイクストラでやったけど、普通に動的計画法的にループをまわすだけで十分だった...(道が必ず頂点番号が大きくなる方向にしか無いため)
1.オアシスを通らずに最短行くか、2.オアシスまで最短で行きオアシスからゴールまで最短で行くのどちらか以外は最適ではないので、まず1を試して、それでムリなときはオアシスがあり、オアシスにたどり着くときの体力が残っている時だけ2もためすことが出来る(submission)。
CF #345(Div2)に参加
ABの2完、Cは方針合ってたのにオーバーフローさせてるといかいう本当にダメなミス。最近こういうの多い気がする...レートを配布してしまった。青から落ちたくないので次はなんとしても上げねば...
Dも普通に時計回り・反時計回り、一度進んでから戻る、一度戻ってから進むの4通りのうち最適なものを選ぶって方は合ってたっぽいのに、maxの比較対象間違えてとんでもないことをしていた...(なぜかansを更新しないといけないのに、そこにansが入っていなくて、もうめちゃくちゃsubmission)。そこを直すだけで通った(submission)。
3/8
SRM 684 Div1に参加
0完、SRM出てもDiv1の器じゃない感がすごいし、しばらく参加しないほうがいい気がしてきた...
現在何番目に注目しているか(10)・0~9の使用状況(210)・現在の合計(最大でも330)の状態を持ってDP。
前から順番に見て、AZを交互に貪欲に取っていく。最後にAが来てしまったらそのAは捨てる。
星座のうちの１つの星をどの星に割り当てるかを決めると平行移動の量が決まる。それによって残りの星もそのぶんだけ平行移動し、そこに星があるかを判定する。
蟻本の反転のページと同じように、1行目の反転を決め打ちにすれば残りを上から順番にみればそこを反転すべきかどうかが決まるので全探索する。
こういう系の問題に対してPythonを積極的に使っていくとsplitとかその辺がめっちゃ楽。
単純にダイクストラに経路復元を組み込むだけだったのに、距離をdouble型にしたくなくて2乗のままで扱ってたらそりゃあ結果かわるということを見落とし、30分くらい悩んだ...「2乗の和」と「和の2乗」はそりゃ違う。
3/9
- CodeThanks2014A日程 A - カメツル算
- CodeThanks2014A日程 B - バッジ
- CodeThanks2014A日程 C - コンテスト
- CodeThanks2014A日程 D - 定期券
3/10
まずn回の過程をそのままシミュレーションしてそれぞれの石像が回転する回数をmod 4でカウントしておく。そこから、i番目の手順が抜けたと仮定すればその範囲を逆に1引いてmod 4で取れば戻すことが出来る。そのとき、カウントが0になっているものを数え上げ、mに一致したものを答えとする。これで、なので間に合う。
低い順位から高い順位だけをむずぶ有向グラフをつくると、1から辿り着ける頂点の範囲は1より確実に順位が高い。この確実に高い順位の人たちだけが実際に1より順位が高い時に1は最高順位を取れる。1から訪れることの出来る頂点をBFSなどで数え上げれば良い。
現在注目している人,とにかく座りたい人だけ座れる席の数,誰でも座れる席の区間開始位置を状態に持つDP。k=K+1の状態は、もう自由に座れる席は1つも無いことを表している(submission)。ループiに関してはiとi-1の関係しか見ていないので、空間計算量はに落とすことも出来るけど、今回は足りると思ったからわざわざやらなかった。
3/11
単純にn個の情報からフィールド情報を作り、その情報に従ってBFS。始点と終点が黒く塗られているかに注意。
文字列の位置を情報に持つDP。DPのシンプルな良い例の問題って印象(submission)。
状態遷移の木を考えて、その状態から１つでも負けに遷移できるならそこに遷移させることで相手を負かすことができる→自分は勝ちとなる。(submission)
乱択を使って解く問題。ヒントのところに書いてある記事を見て、勉強になった。
3/12
虫歯神経の治療がなされた深さに応じて、治療されているとみなせる神経の数は決まる。そして、範囲が被ってしまう場合はどちらかがもう一方を完全にカバーする形になっているので、その一番大きいものだけが治療されたとみなせば良い。つまり、今いる位置から根の方に向かってたどっていく途中で治療済みの神経がなければその神経がその範囲においては最も根に近い治療された神経と見なせて、これらによって治療される神経を数え上げて全体から引けば良い(数え上げは等比級数の公式を使えばすぐ出来る)。
ABC 034に参加
4完、Dは結構悩んだ。平均の最大化は蟻本で目を通していた部分だったんだけど...もう一度読もう。Cは101点解は逆元使うんだろうなーって分かってたけど、一回も逆元書いたことなかったのでとりあえずDP解で100点とってDに行って、また戻ってきて調べながら書いた。
3/13
昨日のABCで逆元を理解したのでこの問題でも実装。
3/14
凸多角形との内外判定を行う。x座標小さい順で点をソートしておき、順に調べていけば良い。ただ、その点が凸多角形に含まれる点ならその点は調べる必要はない。(submission)
3/15
クロスワードの候補となる文字は10種類なので総当り(10!)で間に合う。ワードの開始位置を始めに走査して調べておく。...と思ったらなんか落ちた(submission)。もしかしたら答えが一番最後の順列になるようにしているのかもしれない、と思ってごちゃごちゃにまぜる部分を作ったらすんなり通った(submission)。ちょっとせこい(?)
問題文のヒントから、Gに対する入力が得られ、その出力がHへの入力となり、更にその出力がIへの入力となっている。そして、そのIの出力を見ると...あることが分かり、それをキーにして最後の謎解きをするっていうとてもおもしろいシステムだった。答えも綺麗だったのでとてもびっくりした。
3/16
解説にある通り逆元を使って解くシリーズ。
