「教えてPKU」の版間の差分

提供: IS2005 Wiki
移動: 案内、 検索
(ページの作成:「PKUで解けない問題の番号を投げると，誰かが解答をupしてくれるかもしれないページとして使いましょう．」)
 
 
(15人の利用者による、間の48版が非表示)
1行目: 1行目:
 
PKUで解けない問題の番号を投げると，誰かが解答をupしてくれるかもしれないページとして使いましょう．
 
PKUで解けない問題の番号を投げると，誰かが解答をupしてくれるかもしれないページとして使いましょう．
 +
==  1159 Palindrome ==
 +
http://acm.pku.edu.cn/JudgeOnline/problem?id=1159
 +
*letter
 +
**LCSだと思ったのですが、WA…誰か教えて
 +
***ただのバグでした。すいません。
 +
 +
==  2723 Get Luffy Out  ==
 +
http://acm.pku.edu.cn/JudgeOnline/problem?id=2723
 +
*ymatsu
 +
**2-SAT の変形ということは Discuss を読めばわかるのですが，その先の効率のよい実装がわかりません．一応ACは出たのですが，遅い．．．どなたか高速なコードを．一応正しいコードはこれ．[[media:教えてPKU-2723.ymatsu.java]]
 +
 +
==  2109 Power of Cryptography ==
 +
http://acm.pku.edu.cn/JudgeOnline/problem?id=2109
 +
 +
2109の効率的な解き方plz > educa
 +
 +
while1fork, dm, dragonfly7, y_sawaはJavaで力押しbinary searchだと思われる。
 +
 +
* educa
 +
**binary searchが正解だと思います。あの問題はdoubleで値を受け取ってpower(p,1.0/n)という冗談みたいな式で通ってしまいます･･･
 +
 +
== 1273 Drainage Ditches ==
 +
http://acm.pku.edu.cn/JudgeOnline/problem?id=1273
 +
 +
どうみても最大流です。本当に(ry
 +
* ymatsu
 +
**1273でWrongAnswerを食らいます(educaも同様の様子)1459(Power Network)でAcceptする最大流ルーチンを使っているにもかかわらず多重辺についてはすでに考慮しています．1459を解いている人はやってみてください．
 +
**入力ケースを1個もつファイルが複数入力されると思っていたが，1個のファイルが入力ケースを複数個ようだ．そこを直したら通った．超orz
 +
**ラベル付きbreakは知らなかった > namasute
 +
 +
* namasute
 +
**普通にAcceptされますた。
 +
**[[media:教えてPKU-1273.namasute.java]] <- ネタバレ
 +
 +
* educa
 +
**多重辺を考慮してませんでした orz orz orz
 +
**[[media:教えてPKU-1273_educa.txt]] 一文字追加でaccept...
 +
 +
== 2442 Sequence ==
 +
http://acm.pku.edu.cn/JudgeOnline/problem?id=2442
 +
 +
結局解けずじまい。誰か助けて。
 +
 +
* namasute
 +
**a[i]+b[j] (0 <= i, j < n) の中から小さいn個を選ぶというのを
 +
**m-1回繰り返すと多分できます。
 +
**昔は入力が間違ってましたが直ったみたいです。
 +
**[[media:教えてPKU-2442.namasute.java]]
 +
 +
== 1256 Anagram ==
 +
http://acm.pku.edu.cn/JudgeOnline/problem?id=1256
 +
* ymatsu
 +
** namasute解答が爆速なのでぜひ見たいです
 +
 +
* namasute
 +
** 突っ込みどころ満載なコードでよければ
 +
** [[media:教えてPKU-1256.namasute.java]]
 +
 +
== 1230 Pass-Muraille  ==
 +
http://acm.pku.edu.cn/JudgeOnline/problem?id=1230
 +
* Makegumi
 +
**[[media:教えてPKU-1230.makegumi.cc.txt]]
 +
 +
== 2502 Subway ==
 +
http://acm.pku.edu.cn/JudgeOnline/problem?id=2502
 +
* educa
 +
** ダイクストラだと思ったのにWA...助けてください
 +
** You may assume the subway runs in a straight line '''between adjacent stops'''
 +
** Subway Line上にある点は全て一直線だと勘違いしてました
 +
 +
* namasute
 +
** ダイクストラで解けますた。
 +
** [[media:教えてPKU-2502.namasute.java]]
 +
 +
== 1009 Edge Detection ==
 +
http://acm.pku.edu.cn/JudgeOnline/problem?id=1009
 +
* educa
 +
** RLEで与えられた情報から、色の変化するpixelがわかる。edgeを抽出する際、上記のpixelの影響を受ける場所は、そのpixelの周囲8つである。よって、それらのpixelのみのedgeを計算しておいて、それ以外の場所は変化がないということにして、出力画像を計算する
 +
** というアルゴリズムで実装したものの、sampleは通るのにWrong Answerです。
 +
** 既に通った人がいたら教えてください。特に上位にいるzng氏のコードは見てみたい。
 +
** 「色の変化があるピクセル」として、最終ピクセルを入れるのを忘れていました
 +
** [[media:教えてPKU-1009.educa.cc.txt]]
 +
* dm
 +
** なぜか通ったがなぜ通ったかが分からない。
 +
** [[media:教えてPKU-1009.dm.cpp]]
 +
* zng
 +
** 等幅フォントで
 +
** [[media:教えてPKU-1009.zng.c]]
 +
 +
== 1015 Jury Compromise ==
 +
http://acm.pku.edu.cn/JudgeOnline/problem?id=1015
 +
 +
*educa
 +
** DPで解いてみたものの、最適な集合を表示する部分をうまく処理できずTLE
 +
 +
*namasute
 +
** 疲れた。寝るしかないわね。
 +
** [[media:教えてPKU-1015.namasute.java]]
 +
 +
== 1380 Equipment Box ==
 +
http://acm.pku.edu.cn/JudgeOnline/problem?id=1380
 +
 +
*Gus@ex-GNC-(ry
 +
** お邪魔します。6/4のピラミッド 角度を使わない版です。
 +
**[[media:教えてPKU-1380.gus.cpp.txt]]
 +
 +
== 2131 Key Insertion ==
 +
http://acm.pku.edu.cn/JudgeOnline/problem?id=2131
 +
 +
*namasute
 +
** リクエストにより
 +
** [[media:教えてPKU-2131.namasute.java]]

2006年11月28日 (火) 04:45時点における最新版

PKUで解けない問題の番号を投げると，誰かが解答をupしてくれるかもしれないページとして使いましょう．

1159 Palindrome

http://acm.pku.edu.cn/JudgeOnline/problem?id=1159

  • letter
    • LCSだと思ったのですが、WA…誰か教えて
      • ただのバグでした。すいません。

2723 Get Luffy Out

http://acm.pku.edu.cn/JudgeOnline/problem?id=2723

  • ymatsu
    • 2-SAT の変形ということは Discuss を読めばわかるのですが，その先の効率のよい実装がわかりません．一応ACは出たのですが，遅い．．．どなたか高速なコードを．一応正しいコードはこれ．media:教えてPKU-2723.ymatsu.java

2109 Power of Cryptography

http://acm.pku.edu.cn/JudgeOnline/problem?id=2109

2109の効率的な解き方plz > educa

while1fork, dm, dragonfly7, y_sawaはJavaで力押しbinary searchだと思われる。

  • educa
    • binary searchが正解だと思います。あの問題はdoubleで値を受け取ってpower(p,1.0/n)という冗談みたいな式で通ってしまいます･･･

1273 Drainage Ditches

http://acm.pku.edu.cn/JudgeOnline/problem?id=1273

どうみても最大流です。本当に(ry

  • ymatsu
    • 1273でWrongAnswerを食らいます(educaも同様の様子)1459(Power Network)でAcceptする最大流ルーチンを使っているにもかかわらず多重辺についてはすでに考慮しています．1459を解いている人はやってみてください．
    • 入力ケースを1個もつファイルが複数入力されると思っていたが，1個のファイルが入力ケースを複数個ようだ．そこを直したら通った．超orz
    • ラベル付きbreakは知らなかった > namasute

2442 Sequence

http://acm.pku.edu.cn/JudgeOnline/problem?id=2442

結局解けずじまい。誰か助けて。

  • namasute
    • a[i]+b[j] (0 <= i, j < n) の中から小さいn個を選ぶというのを
    • m-1回繰り返すと多分できます。
    • 昔は入力が間違ってましたが直ったみたいです。
    • media:教えてPKU-2442.namasute.java

1256 Anagram

http://acm.pku.edu.cn/JudgeOnline/problem?id=1256

  • ymatsu
    • namasute解答が爆速なのでぜひ見たいです

1230 Pass-Muraille

http://acm.pku.edu.cn/JudgeOnline/problem?id=1230

2502 Subway

http://acm.pku.edu.cn/JudgeOnline/problem?id=2502

  • educa
    • ダイクストラだと思ったのにWA...助けてください
    • You may assume the subway runs in a straight line between adjacent stops
    • Subway Line上にある点は全て一直線だと勘違いしてました

1009 Edge Detection

http://acm.pku.edu.cn/JudgeOnline/problem?id=1009

  • educa
    • RLEで与えられた情報から、色の変化するpixelがわかる。edgeを抽出する際、上記のpixelの影響を受ける場所は、そのpixelの周囲8つである。よって、それらのpixelのみのedgeを計算しておいて、それ以外の場所は変化がないということにして、出力画像を計算する
    • というアルゴリズムで実装したものの、sampleは通るのにWrong Answerです。
    • 既に通った人がいたら教えてください。特に上位にいるzng氏のコードは見てみたい。
    • 「色の変化があるピクセル」として、最終ピクセルを入れるのを忘れていました
    • media:教えてPKU-1009.educa.cc.txt
  • dm
  • zng

1015 Jury Compromise

http://acm.pku.edu.cn/JudgeOnline/problem?id=1015

  • educa
    • DPで解いてみたものの、最適な集合を表示する部分をうまく処理できずTLE

1380 Equipment Box

http://acm.pku.edu.cn/JudgeOnline/problem?id=1380

2131 Key Insertion

http://acm.pku.edu.cn/JudgeOnline/problem?id=2131

「https://is.zng.info/wiki/generic/index.php?title=教えてPKU&oldid=310」から取得