教えてPKU

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