PKU
AC率の割に簡単だった。逆に簡単杉だからAC率が低かったのかも。とりあえず某コンテストに似た陰険さを感じたので、実はsearch stringにも変な文字が混ざってて、空文字が発生する可能性があるんじゃないかと思って対策してみた。問題良く読んでないけど実は…
ただの構文解析問題。言われたとおりに普通にLL(1)で実装すればおk。std::stringを使って速度をあまり気にしない実装にしても0MSなのでデータ自体が甘いんだと思う。相変わらずショートコーダーの方々がやばかった。誰かショートコーディング本を俺に買って…
44secとかかかるのでどうにかして高速化しないといかん。 また夜11時くらいに帰ってきてやる。家が暑すぎるぜorz
癒されたくてやった。反省していない。
実際のデータセット取ってきて全部通るのにPKUだとWA。もう原因がわからん。何が悪いんだろう…。
WAの原因が分からん。問題理解してないのかな。 2 2 2.00 5.00この時の出力は2.50にならないといけないような気がするんだけどそれが間違いなのかも。なんか掲示板にもそれらしきことが書いてあったけど中国語で良くわからんかった。ボスケテ追記:PCの無い…
二分探索気味にやってみた。たぶんこれで行けると思うから、後は最大値を効率よく求める方法を考えてまた明日以降にやる。
setとmapを贅沢に使用して超低速解をはじき出しましたorz 書いてる途中に配列でも効率良く処理出来る方法を思いついたけど時間がないのでそのままsubmit。今夜起きてられたら解き直してみよう。
たぶん不可能判定を適当にやったからWA。そしてもの凄く素直に実装したら普通に時間足りてないっぽい。WA出た時点で812ms。今眠いからもう㍉。また涼しくて机の上に物を書くスペースがある時に考える。
なんか考慮し忘れてるっぽいorz なんだろ。
実は偶数座標、奇数座標の差で正解が出るんじゃないのかと。で、合計が奇数個の時は絶対おkなんじゃないのかと。一回後者の条件に気付かなくてWA。二回目はスキップしたときに入力までスキップしてWA。切なかったのでコード短縮したけど、某氏+100Bとかでさ…
反復深化のテスト。幅優先と同程度のタイムでAC。これは行ける。 壁は垂直方向と水平方向に分けて持つと判定がしやすいかも。bit演算でまとめてしまえばかなり処理を統一できそうだけど。ていうかこの次の問題が本当の問題だということが発覚して切ない。
昨日の練習の時にみんなで色々考えた結果をそのままコーディングしたら46msで結構華麗に解けた。mn(n%2==1)が出てくるたびにrの回転方向を変えてひたすら足していく。最終的には必ず rn rn m1のどちらかの形になる。ここで点の個数をNとすると rn ---> m1 r{…
二人とも頑張った。頑張ったけど「これ外側だけ調べればいいんじゃね?」の一言で全てが終了。まぁ頑張った。余りにも切なかったから色々高速化。それでも300MS。これ以上はアルゴリズムを改良するしかねーのかなぁ。
寝る前にソースが見つかって助かった(´・ω・`) 去年解いたグラフの問題。必要なルータの個数とそのルータの次数を出力する。とりあえず適当に二つのルータを繋げる。そうすると、新たなPCを追加するときは、既存のルータから新たな線を延ばさないといけない。…
苦手な動的計画法の練習。上手く漸化式を作れない。「iが0の時、スタート地点から最終地点までタイヤを交換しないときの走行時間を入れる。iがkの時、kでタイヤを交換したとして、その時間が[k+1,n]の地点の最短時間より早かったら値を更新。」っていうのを…
またMSTの問題。とりあえずコーディングしてライブラリに追加。でもpriority_queueとか二重vector使ってるせいか超遅い。汎用性を求めると速度が犠牲になっちゃう気がするけど今はまだいいや。
とりあえずどんな問題が来てもあんまり変更せずに使えるようなクラスと関数を作成するために頑張ってみたけどなかなかうまくいかない。沢山の問題で使ってみるしかない。
算数の問題なのにとけねぇorz
折角なのでunion_findクラスとグラフ用のedgeクラスを作った。これから改良を加えながら活用していかないと。
なんか華麗に解く方法考えたら楽しそうだけど、最速実装練習だったからset2個使って済ませた。
あんまり考えることが無かった。簡単な問題を素早く解く練習。
約数が奇数個の数だけ、すなわち平方数だけ解錠される。だから答えは(int) sqrt(n)。
大学の上位の人が解いてる問題をどんどん解いていこうと思いつつも結構難解というか特殊な問題が多くて困ってたところに出てきたこの問題。簡単だったから嬉しすぎて何も考えずにコーディングしてしまった。
1112 1041 1095
むずかった。正方形だけで構成されたペントミノの問題で、全解を調べなくても良いから解があるかどうかだけ調べろっていう話。隙間が無いことを考慮して できるだけ上の点 できるだけ左の点 の順で正方形の大きさを小さくして配置していく。UNIX端末室のペン…
伝死壊露はよくわかりませんがとけました。うれしかったです。
問題名に対して、まじっすかとしか言いようがない。
むしゃくしゃしてやった。今は反省していない。アルゴリズムを改良すればもっと短くなる気がするけどまずは実験レポートやんないと。
なんか値の範囲があんまり書いてないなーとは思ってた。で、実は大文字も混じってんじゃね?kもすげーでかい値がありそうだなとか色々考えたあげく出したらRE。kvectorのサイズが1以下の時にrotateしようとしておかしくなってただけでしたヽ(´・ω・`)ノ