反復深化で47ms。その後実験でBFSしてみたらTLEｗｗｗ 最悪 (50+座標) * 4^10 byte 必要なのでメモリ的にも危ないとは思ったけど。

http://www.acm.inf.ethz.ch/ProblemSetArchive.html アーカイブを発見。sample inputとoutputをゲットしてデバッグ完了！1000000000*3は負になっちゃいますよね／(^o^)＼ それだけでした／(^o^)＼

ちょっと訳ありで速くしてみた。 #include <iostream> #include <string> #include <vector> #include <algorithm> using namespace std; struct Data { const char* s1; int l1; const char* s2; Data(const char* s1, int l1, const char* s2) : s1(s1), l1(l1), s2(s2) {} char operator [](int</algorithm></vector></string></iostream>…

http://acm.pku.edu.cn/JudgeOnline/problem?id=2684 久々にやった。今年は頑張って東大勢とさいたま+その他大勢の猛者に勝つ！今年はほぼ確実にawakiaと出れる最後のICPCなので気合い入ってます。もう一人の新チームメイトもポテンシャルがやばいので気合い…

昨日の反省をふまえてLCSを色々作ってみた。昨日のfox(笑)のid:awakia-n案も実装してみた。結構綺麗に出来たと思う。O(NM)。合ってるか分からんけど。考え方。LCSの性質上、文字列x, yの順序を逆転した物をx', y'としたとき、lcs(x, y)とlcs(x', y')の内容は…

違う問題で見かけた陰険インプットを見てひらめいた。実はちゃんとDPできてた。そしてなんで解けないのか分かった。0 0だけで構成されるケースでWAが出てただけでしたorz 道の再構築にsetとか使ってるせいでオーダーがでかくなっちゃってるのでその辺をどう…

1984MSで通したｗ O(N^2logN)だけど実際はO(N^2log(N^2))。もうちょっと色々と減らす方法考えないと。追記: 765MSになった。今度こそ正真正銘O(N^2logN)。後は何かできるかなー。

main(h,m){for(gets();~scanf("%d:%d",&h,&m);)printf("%d\n",m?0:(h+11)%24+1);}30分くらいで76Bにできた。嬉しかった。

main(a,b){for(gets(b);~scanf("%d%d",&a,&b);puts(a

科目登録しねーとと思いつつもPKU。線分の交差判定。「繋がってる」っていう関係が推移律を満たすので、disjoint setで繋がってるかどうか判定してみたけどおせー。とりあえず幾何ライブラリテストとしてはおｋだけど高速化してみないとダメだ。高速化: O(N^…

素数判定っぽい問題。100B切りたい(´･ω･｀) a['aa'],i; main(k,n){ for(;++i<9994;) if(!a[i]){ printf("%d\n",k=i); for(;k<9994;a[k]=1) for(n=k;n;k+=n%10,n/=10); } }ていうかなんだこの適当なプログラム…。

WA8回とか／(＾o＾)＼ 最初にlongを使ったことが全ての始まりだった。なんだこれ実は32bitじゃなくね？32bitっつーのは32bit Pascalの事で、そのLongIntって実は64bitなんじゃね？ふざけんなーｗ ↓ あれｗｗｗまだWA出るｗｗｗうはｗｗｗ ↓ 綴り間違ってない…

a,b,m,p,q,n; main(s){ for(;~scanf("%d%d",&a,&b);printf("%d %d %d\n",a,b,m),m=0) for(p=a

いきなりショートコーディング: 155Bｷﾀｰｗ 反則なのかどうなのかはおいといて、とりあえずコード。 a,b,m,p,q,n; main(s){ for(;~scanf("%d%d",&a,&b);m=0){ for(p=a

awakiaと2000番台から適当に選んで解こうぜｗｗｗうぇｗｗみたいなノリになりながら適当に「じゃー2040でｗｗｗ」とか言ったからこの問題を解いた。調子に乗ってやった。その場で反省した。内容はグラフの同型判定。で、とりあえず多項式時間では解けなそう…

リベンジ完了。1018に関しては、以下に早い段階で枝切りが出来るかが重要だった。実はバックトラックが必要ないのでループで書けたことが発覚。awakiaに感謝。1016は前に解いたときにドツボにはまってもがいてたんだけど今日やったら通った。一体何だったん…

どこをどう見てもブロックソーティングだよなぁ…って思ってそのまま実装したら通った。ショートコーディング: 163BになったけどWAが出たｗ うへー。疲れたからいいや。

眠かったけど微妙に眠れなかったので簡単な問題さがしてたけどこれはさすがにすいませんでしたとしか言いようがありませんでしたorz ちゃんと自分でも書けるようにしときまｓ。ショートコーディング: 実はまだ買ってきた本を読めてないので全然効果は出てな…

漸化式にならないなら再帰のプログラム書いてからそれをDPに直せば良いじゃん。俺は人生で数式よりもプログラムに触れてた時間の方が32倍(当社比)くらいなげーんだよ！って開き直って適当に再帰で書いてみた。 bool search(int sum, int target) { for (int …

M本氏に感謝ｗ 解けーた。既に和の部分が求まっていて、x+y=nのxとyが未知な覆面算として解いた。しかし、覆面算と言っても4桁の場合なら A B C D + B C D --------- A B C D + A C D --------- A B C D + A B D --------- A B C D + A B C --------- 多くて…

ただのシミュレーション問題。ショートコーディング: 319Bまで減った。改行コード変えれば後5B減る。猛者い人達なら余裕でもっと減らせるんだろうなぁ。疲れたからもういいやorz #include<stdio.h> #define C(D)d[t&1][y*22+x D] #define N d[t&1^1][y*22+x] #define </stdio.h>…

AC率の割に簡単だった。逆に簡単杉だからAC率が低かったのかも。とりあえず某コンテストに似た陰険さを感じたので、実はsearch stringにも変な文字が混ざってて、空文字が発生する可能性があるんじゃないかと思って対策してみた。問題良く読んでないけど実は…

ただの構文解析問題。言われたとおりに普通にLL(1)で実装すればおｋ。std::stringを使って速度をあまり気にしない実装にしても0MSなのでデータ自体が甘いんだと思う。相変わらずショートコーダーの方々がやばかった。誰かショートコーディング本を俺に買って…

癒されたくてやった。反省していない。

setとmapを贅沢に使用して超低速解をはじき出しましたorz 書いてる途中に配列でも効率良く処理出来る方法を思いついたけど時間がないのでそのままsubmit。今夜起きてられたら解き直してみよう。

実は偶数座標、奇数座標の差で正解が出るんじゃないのかと。で、合計が奇数個の時は絶対おｋなんじゃないのかと。一回後者の条件に気付かなくてWA。二回目はスキップしたときに入力までスキップしてWA。切なかったのでコード短縮したけど、某氏+100Bとかでさ…

反復深化のテスト。幅優先と同程度のタイムでAC。これは行ける。 壁は垂直方向と水平方向に分けて持つと判定がしやすいかも。bit演算でまとめてしまえばかなり処理を統一できそうだけど。ていうかこの次の問題が本当の問題だということが発覚して切ない。

昨日の練習の時にみんなで色々考えた結果をそのままコーディングしたら46msで結構華麗に解けた。mn(n%2==1)が出てくるたびにrの回転方向を変えてひたすら足していく。最終的には必ず rn rn m1のどちらかの形になる。ここで点の個数をNとすると rn ---> m1 r{…

寝る前にソースが見つかって助かった(´･ω･｀) 去年解いたグラフの問題。必要なルータの個数とそのルータの次数を出力する。とりあえず適当に二つのルータを繋げる。そうすると、新たなPCを追加するときは、既存のルータから新たな線を延ばさないといけない。…

苦手な動的計画法の練習。上手く漸化式を作れない。「iが0の時、スタート地点から最終地点までタイヤを交換しないときの走行時間を入れる。iがkの時、kでタイヤを交換したとして、その時間が[k+1,n]の地点の最短時間より早かったら値を更新。」っていうのを…