Hatena::Grouptopcoder

Wrong Answer -- japlj このページをアンテナに追加 RSSフィード

2013-04-07

Codeforces 83E -- Two Subsequences

| 14:26 | Codeforces 83E -- Two Subsequences - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - Codeforces 83E -- Two Subsequences - Wrong Answer -- japlj Codeforces 83E -- Two Subsequences - Wrong Answer -- japlj のブックマークコメント

http://codeforces.com/problemset/problem/83/E

面白い問題だったので思考過程をメモ.

(当然ですが解法バレがありますので自分で考えて解きたい人は注意)

続きを読む

2013-02-18

AOJ 0586

| 15:29 | AOJ 0586 - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - AOJ 0586 - Wrong Answer -- japlj AOJ 0586 - Wrong Answer -- japlj のブックマークコメント

制約が書かれてないが,どうせ解ける範囲しか来ないと思って書くと通った.c ≧ 0 のときは全探索して,c < 0 のときは偶数桁の回文数が 11 で割り切れるので n = 1 のときを除いて 999..999 を出力すればよい.

AOJ 0585

| 15:28 | AOJ 0585 - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - AOJ 0585 - Wrong Answer -- japlj AOJ 0585 - Wrong Answer -- japlj のブックマークコメント

よくある最近点対のアレ(xでソートして,これまでの最近点対の距離よりxが離れてたら枝を刈る)で通った.

AOJ 0584

| 15:27 | AOJ 0584 - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - AOJ 0584 - Wrong Answer -- japlj AOJ 0584 - Wrong Answer -- japlj のブックマークコメント

小さい方から4つだけ分かっていれば求めたい数は分かる.

AOJ 0583

| 15:27 | AOJ 0583 - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - AOJ 0583 - Wrong Answer -- japlj AOJ 0583 - Wrong Answer -- japlj のブックマークコメント

それぞれの数の約数を全列挙して unique して公約数になってるかどうか試す,とかしたけど普通に √max まで試し割りでよかったじゃないですかー

AOJ 0582

| 15:26 | AOJ 0582 - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - AOJ 0582 - Wrong Answer -- japlj AOJ 0582 - Wrong Answer -- japlj のブックマークコメント

普通に辺の長さを比べましょう.

2013-02-17

AOJ 0591

| 01:54 | AOJ 0591 - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - AOJ 0591 - Wrong Answer -- japlj AOJ 0591 - Wrong Answer -- japlj のブックマークコメント

多倍長を書いてみようと思ったけど掛け算だけだし大したことはなかった.

ZOJ 1016

| 23:53 | ZOJ 1016 - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - ZOJ 1016 - Wrong Answer -- japlj ZOJ 1016 - Wrong Answer -- japlj のブックマークコメント

問題文に書いてある通りに P を S に直して S を W に直した.直接変換できるのかは考えてない.

2013-02-15

ZOJ 1014

| 02:12 | ZOJ 1014 - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - ZOJ 1014 - Wrong Answer -- japlj ZOJ 1014 - Wrong Answer -- japlj のブックマークコメント

構文解析する必要はない.まず + で切れるか試し,次に * で切れるか試し,次に ^ で切れるか試す.全部ダメなら,括弧で全体が覆われていればそれを外し,そうでなければ元の文字列そのままが答になる.

ZOJ 1013

| 01:41 | ZOJ 1013 - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - ZOJ 1013 - Wrong Answer -- japlj ZOJ 1013 - Wrong Answer -- japlj のブックマークコメント

n 個目までの caravan に helm を計 h 個,armor を計 a 個積んでいるとき,同様にして積める boots の個数の最大値をDP.普通に概算すると 100*500*500*500*500 とかになるが実際は caravan の大きさ制限から枝を刈ると十分に速い.

ZOJ 1012

| 01:02 | ZOJ 1012 - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - ZOJ 1012 - Wrong Answer -- japlj ZOJ 1012 - Wrong Answer -- japlj のブックマークコメント

問題文が曖昧な気がするが,とにかく時間優先で処理すればOK.特に各ジョブは1時間しか要さないので面倒なことはせずに,1時間ずつループを回して処理できるジョブを処理していくとよい.

  • 1PE: 問題ごとに「テストケースとテストケースの答の間には空行を挟むこと」と「テストケースの答の後に空行を出力すること」があって紛らわしい……,いずれにせよちゃんと読む.

ZOJ 1011

| 23:51 | ZOJ 1011 - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - ZOJ 1011 - Wrong Answer -- japlj ZOJ 1011 - Wrong Answer -- japlj のブックマークコメント

各ノードについてそれぞれのsignalが来た時,部分木がvalidになるかを計算する.全二分木で,与えられ方が優しいので簡単なループを回すだけで木DP可能.

ZOJ 1010

| 23:10 | ZOJ 1010 - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - ZOJ 1010 - Wrong Answer -- japlj ZOJ 1010 - Wrong Answer -- japlj のブックマークコメント

書いてある通りに.

  • 1WA: 隣接する辺が交差してると判定されないようにしていたら,辺どうしが重なるときにも交差してないと判定されていた.はじめから問題文に忠実に判定していればこのWAは無くせたはず.

2013-02-14

ZOJ 1009

| 04:52 | ZOJ 1009 - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - ZOJ 1009 - Wrong Answer -- japlj ZOJ 1009 - Wrong Answer -- japlj のブックマークコメント

書かれているとおりにシミュレーション.

  • たくさんWA: 問題文中にある2ローターの図を自分でサンプルに入れていたが,その図に合うようなプログラムはWAになり,合わないプログラムでACが貰える.問題がクソすぎるのでしょうがない.クソ.

ZOJ 1008

| 03:00 | ZOJ 1008 - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - ZOJ 1008 - Wrong Answer -- japlj ZOJ 1008 - Wrong Answer -- japlj のブックマークコメント

枝刈り探索.とはいえ同じピースをまとめて扱うだけでよい.

  • 4TLE: 全探索,適当な枝刈りなど.このへんは手元でちょっとケース作るだけで間に合わないと分かるので,そうするべき.
  • 6WA, 1TLE: 嘘枝刈り.パラメタ調整でWAを量産する嘘枝刈りに走る前に,どんなケースで時間がかかるのかちゃんと考えるべきだった.そうでなくとも同じピースを同一視するぐらいは典型なのでそれをしなかったのはよくない.

ZOJ 1007

| 02:16 | ZOJ 1007 - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - ZOJ 1007 - Wrong Answer -- japlj ZOJ 1007 - Wrong Answer -- japlj のブックマークコメント

Hintにあるように k 項目が Θ(1/kr) (r ≧ 1) ぐらいの無限級数は n 項目以降を無視しても Θ(1/n^(r-1)) ぐらいの誤差にしかならない.よって要求精度12桁を達成するためには k 項目が Θ(1/k4) ぐらいの式に出来ると嬉しい.

問題文通りの式では Θ(1/k2) で,Hintにあるように ψ2(x) = ψ(x) - ψ(1) とおくとこれは Θ(1/k3) ぐらいになる.同様にして ψ3(x) = ψ2(x) / (1-x) - ψ2(0) とでもおけばこれは Θ(1/k4) ぐらいになる.ψ2(0) の値は有名なバーゼル問題の解から π2/6 - 1 だとわかる.

  • 1TLE: Θ(1/k3) の式でTLE.2000*1000000 の浮動小数点演算はさすがにTL 10s とはいえ無茶だった気がする(でもサーバの速度分からなかったのでしょうがないかもしれない(でもこれで解けるとかHintのまんまだしさすがにダメだろう)).

ZOJ 1006

| 01:14 | ZOJ 1006 - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - ZOJ 1006 - Wrong Answer -- japlj ZOJ 1006 - Wrong Answer -- japlj のブックマークコメント

i を移項します.

ZOJ 1005

| 01:00 | ZOJ 1005 - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - ZOJ 1005 - Wrong Answer -- japlj ZOJ 1005 - Wrong Answer -- japlj のブックマークコメント

Ca, Cb は互いに素なので k * Ca (mod Cb) は 0〜Cb-1 まですべての値をとる.AからBにCaずつ注ぎまくる.

ZOJ 1004

| 00:53 | ZOJ 1004 - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - ZOJ 1004 - Wrong Answer -- japlj ZOJ 1004 - Wrong Answer -- japlj のブックマークコメント

全探索

  • 1PE: 行末の空白忘れ.変に気をつけたのが仇になった,問題文(少なくとも入出力セクション)はしっかり読む.

ZOJ 1003

| 00:39 | ZOJ 1003 - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - ZOJ 1003 - Wrong Answer -- japlj ZOJ 1003 - Wrong Answer -- japlj のブックマークコメント

全探索

  • 3WA: そもそも題意をちゃんと把握できていなかった.

ZOJ 1002

| 00:18 | ZOJ 1002 - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - ZOJ 1002 - Wrong Answer -- japlj ZOJ 1002 - Wrong Answer -- japlj のブックマークコメント

全探索

ZOJ 1001

| 00:18 | ZOJ 1001 - Wrong Answer -- japlj を含むブックマーク はてなブックマーク - ZOJ 1001 - Wrong Answer -- japlj ZOJ 1001 - Wrong Answer -- japlj のブックマークコメント

やるだけ.