読者です 読者をやめる 読者になる 読者になる

FCCPC

FCCPCについてお伝えするブログ

トレンドマイクロプログラミングコンテスト2014 Round 3, 4

記録: hadrori

TMPC 2014のRound3, 4にFCCPC++として参加していました. メンバーはhadrori, ponyo, stqn, yosupoの4人です.

前も書いたけど特有のルールから

  • submitしたらその問題は次の10分間submitできない
  • 1つの問題に5回までsubmitできる
  • ACした場合の得点は100*(0.6+0.1*(1-実行時間/制限時間)+0.3*(1-経過時間/コンテスト時間))

Round 3

また4問なのでとりあえず1人1問読むことにする.
問題が公開されそうに無いので分かるのだけ概要を書いておきます.

  • A: 重さがdoubleのナップザック. 個数は最大65535
  • B: よく知らない
  • C: 九九表をN*N個に拡張して, そこに現れる数の種類
  • D: よく覚えていないが, 自転車30台運べる車があって, 100個の各場所には100台未満の自転車がある. 総和は5000で, 各場所を50に均すには最小のステップ
0分

001番とかあるしこれきっと最初に作った問題でやばいやつだ. とか話す

5分

Aの制約が書かれていない. clar
No Commentと言われる.
Bの制約が書かれていない. clar
No Commentと言われる.
Cの制約がunsigned intと書かれている.
やばそう.
Dは制約が書かれている.

15分ぐらい

Aがナップザックなんだけど, 制約不明だし, 重さdoubleだしどうしたもんかなあ.
Bは木DPらしい.

20分ぐらい

Aの制約が公開される(情報小出しにするのやめて).
65535とかもうよくわかんないのでどうせ昨日と同じで枝刈り全探索で余裕なやつだろ……

25分ぐらい

Bが問題としてはCodeforces Div1 Aみたいなまともな問題らしい.
投げるもWA. 昇順を見落としていた

30分ぐらい

A AC(hadrori).
自明な枝を刈っただけの全探索が0.000sで通る. うーん.

35分ぐらい

B AC(yosupo).
はい.
C, OEISでみつける(OEISゲーか?). A027424
O(n2/(log n)c)とか見える……
無理ゲーだ. そもそもどう考えてもO(n)でも厳しいので制約が書かれてないタイプでは. clar
No Commentと言われる.

60分ぐらい

Dどうすんだこれ.
greedy考えても一瞬で反例見つかる.
枝刈り全探索事案かなあ.
Cを60000ぐらいまでなら手元で間に合いそうな感じだったのでそれ以上来ないと踏んで提出(assertでそれ以上は落とす). TLE.
ジャッジが激重なのかなあ.
サーバーが仮想だとメモリの読み書きだけ異常に遅い場合があるとかいう噂があるらしい.

70分ぐらい

Cを30000超えたらassertで落とすようにして提出. signal なんちゃら. どうやらassertに引っかかったらしい. 無理だ.

90分ぐらい

とりあえずDを枝刈り全探索的に書く. 超遅い.

110分ぐらい

Dのそれっぽいgreedy解の案が出る. 反例も思いつかないので実装してもらう.

120分

D間に合わず.
ここで模擬国内スタート(別に記事書きます)

Round 4

これも問題概要を書いておく.

  • A: N個(上限の情報なし)の点が平面上にあり, 中心点が決まっているとき, 中心点を1つの頂点とする三角形をつくる.
    また各線分が交差してはならない(点と辺の共有は許される). 三角形の数を最大にしろ.
  • B: 記事を入力として与えるとき, その記事がトレンドマイクロに関するものか当てろ. ただしトレンドマイクロの社名を他社の名前に(またその逆に)している可能性がある.
0分

B意味不明. A問題文がわかりづらすぎて意味不明.
とりあえず点の数が不明なのがやばすぎなのでclar.
問題文に書いてあると言われたので, 上限のことだよ?って聞く.
No Comment
?!?!?!?!??!
どうしようもない.

30分

A, 最小独立集合に帰着できそう. 最小独立集合ってどう求めるんだろう->NP困難だよねえ

70分

できること無いしもうやる気皆無. とりあえずトレンドマイクロのサイトとかからトレンドマイクロに関する単語を集めまくる.

90分

集めた単語やフレーズ(Trend Microは入れてない)を元にパターンマッチングオートマトンを作ってAho-Corasickでチェックしてく(1つでもマッチしたらok).
サンプルは通る(そりゃそうだ).
投げるがWA. そりゃそうだ.
この時点でも全チーム0完太陽で出題者頭おかしいのではってなる.

170分

パターンと入力を全て大文字に変換してマッチさせることにする. WA. 10分ルールによりBは0点確定.
Aもどうしようもないのでwhile(1)を投げる. TLE. 終了. (Round 4は全チーム0完太陽)

まとめ

TMPCクソすぎでは……
競プロ黎明期の問題って感じだ(黎明期とかしらないけど)
解説が欲しいですね
というかジャッジ解が見たい.