snuke

Last-modified: 2015-01-26 (月) 17:22:26

おすすめ問題

問題の左に書いてある数字はだいたいの難易度

★★★★★

  • [8]Open cup gp5 problem A 変わった解法。コンテスト中に解けて嬉しかった。
    問題概要
    N個の爆弾が数直線上に並んでいる。
爆弾iはx[i]の位置にあり、爆発すると距離r[i]以内の爆弾を誘爆する。
爆弾iを起爆するときに爆発させられる爆弾の数を全てのiについて求めよ。
1 ≦ N ≦ 10^5, -10^9 ≦ x[i] ≦ 10^9, 1 ≦ r[i] ≦ 10^9
  • [10]UTPC 2013 L めっちゃクール。あんな手法で計算量落ちるとは・・・
  • JOI過去問 良問がたくさん。

★★★★☆

  • [7]XIV Open cup GP of Udmurtia problem I ahoの使い方がうまい
    問題概要
    文字列集合SとTが与えられる。
SはTrie木の形で与えられ、頂点数は10^6くらい。
Tは普通に文字列のリストで与えられ、文字数の合計は10^6くらい。
Tの各文字列について、それがSに部分文字列として何カ所に含まれているかを答える。
例：{S = ("ababa","ba"), T = ("ba","aba")} なら 3 と 2 を順に出力
  • [6]RUPC2013 Replace 良問。あれを回避するためには２種類ぐらい手法があります。解法
  • [7]UTPC 2013 I あんまり見たことが無いタイプの木＋データ構造良問
  • [6]CodeFestivalAsia F Yakiniku 問題を読んだ時「よくある区間系の設定の問題か。貪欲とかかな？」解いた後「ほえー、このsegtreeが必要になるのか。うまいなぁ。」

★★★☆☆

  • [9]JAG summer 2013 Rotation Game phidnightさんの考察力がプロで、終了間際にギリギリ通せて思わず「ヨッシャ」って叫んでしまった問題。
  • [7]UTPC 2013 E なんというか、勝手に作っていた固定概念を覆してくれた問題。
  • [8]CF259 D1E segtreeの新しいテクを知った。ブログに書きました。

★★☆☆☆

  • [4]PKU2345 Central heating 当時は若く、掃き出し法にこんな応用例があるのかーと感動した。この問題というよりは線形代数に対する感動だったのかもしれない。

★☆☆☆☆

  • [4]PKU1984 ~ PKU1987 グラフの練習に良いと思います。入力がちょい面倒かも？
 
 

作った問題

※このコンテンツには、「自分の作った問題は可愛く見える補正」と「思い出の美化」が含まれています。ご注意ください。
星はオススメ度を表しています。

Topcoder

書いた問題一覧はここで見ることができます。
わりと気に入ってるものをpickupします。コメントは結構思い出が詰まっていて長いので折り畳みました。

  • ★★★★☆[9]SRM555 D1H MapGuessing
    コメント

    writerデビュー作。SRM555は日本でオンサイトイベントがありました。懐かしいなぁ。感慨深い。最初はもう少し難しかったんですが、簡単になりました。

    • 元の問題について
      今の問題は「実行し終わった時点でGoalと同じであればよい」だけですが、
      元の問題は「実行途中にGoalと同じになってはいけない」という条件もありました。
      制約はテープの長さが 30 くらいです。(今の問題では36)
      是非考えてみて下さい。
      解法
      EgorさんにTCOのインタビューで「好きな問題のタイプ」として挙げていただいた時は嬉しかったです。
  • ★★☆☆☆[5]TCO12 Semifinal1 Med StRings
    コメント

    misofさんに「BWTに関する問題は久しぶりに見たなぁ、nice」的なことを言われた記憶があります。懐かしい。

  • ★★★★☆[9]SRM570 D1H CurvyonRails
    コメント

    初めて書いたフルセットSRM。はじめは直進も曲がるのも同じコストでMediumの予定だったんですが、りんごさんeditionで正解者0の問題になりました。この頃は高校の体育でよくサッカーをやらされてたなぁ、という記憶が蘇ります。

  • ★★★☆☆[6]SRM570 D1M CentaurCompany
    コメント

    同じくSRM570。最初はもうちょい簡単でしたが、シンプルすぎて簡単な数式１つで解けることが判明し、急遽変更を加えました。計算量がモリモリ下がる、木DPの練習としていい感じの問題になりました。

  • ★★☆☆☆[9]SRM578 D1H DeerInZooDivOne
    コメント

    りんごさんととざんと動物園に行った時に作ったセット。

  • ★★★☆☆[8]SRM580 D1M ShoutterDiv1
    コメント

    interval graphを眺めながら適当に考えてたら出来た問題。そのせいかグラフに直してから考える人がわりといたような。入力方式が凄まじいw

  • ★★★★☆[9]SRM580 D1H WallGameDiv1
    コメント

    りんごさんとQuoridorを遊んだ後に一緒に作った問題。懐かしい。一見多項式時間で解ける問題に見えないけど問題の言い換えとかをすると解ける問題になると言う感じ。題材ドリブンとしてはいい出来っぽい。

  • ★★★★☆[7]SRM589 D1H FlippingBitsDiv1
    コメント

    この手法、なんか不思議。tozan曰く「すぬけらしい出題という感じがする。」らしい

  • ★★★☆☆[9]TCO13 Wildcard Hard GoodNumbers
    コメント

    SRM555オンサイトの帰りに思いつきました。SRM555 Div1Easyを考えてる時に派生した問題だっけ。
    TCOではwataさんが単独ACしてWildcardを突破して下さった(プロ！)のでとても嬉しかったです。

  • ★★☆☆☆[9]TCO13 Final Hard TBlocks
    コメント

    この問題はこれを見て「自分ならTブロックをこう使いたいな」と思って作った問題です。自分では簡単だと思っていたんですが、むずかったらしくこんなところに使われてしまいました。
    TCOでは途中から誰にも解かれないんじゃないかとめっちゃヒヤヒヤしてたんですが、Petrプロが単独ACで優勝という結果になって胸をなで下ろしました。WildcardといいFinalといい、1人単独ACという、一歩間違えればeasy,medium早解きが勝つという微妙な結果になるようなギリギリのところで盛り上がる展開となって本当に運が良かったと思います。難易度を適切に見積もってくださったAdmin陣、そしてなによりACされたプロの方々のおかげさまですね。未だにAdmin roomでivanさんに「cool round」と言われた時の興奮が忘れられません。

  • ★★★☆☆[2]SRM602 D1E TypoCoderDiv1
    コメント

    Easyを作るの、面白さと簡単さの両立にいつも苦労するんですが、この回はわりとうまく出来たのかなぁ。twitter評判は良かったです。
    ただ、この回準備がギリギリまでかかってやばかったという苦い思い出もあります。

  • ★★★★☆[10]SRM602 D1H BlackBoxDiv1
    コメント

    しばらくぼんやりと考えていた問題が突然解けたので出題に至りました。最初はうまいことBitDPができないかとか考えてただけだったんですが、まさか多項式で解ける問題だったとは。本番ではhosさんが単独正解でプロでした。少なくとも時間内には誰も解けないだろうと思ってたのでびっくりしました。

  • ★★★★★[8]SRM615 D1M LongLongTripDiv1
    コメント

    スキーに行くバスでスキー場を題材にした問題を考えていて出来ました。最初は全部の辺についてmod試さないと行けないと思ってましたが、１本だけで良くて、なかなか不思議。うまいこと必要十分条件が満たせるんだなぁ。

  • ★★★☆☆[5]TCO2014 R2C Med CliqueGraph
    コメント

    Mediumない？と聞かれて作った。最初はクリーク同士をつなぐグラフでも作れば出来そうと思ってたけど、うまくグラフを作るとクリークを潰せるんですね。wataさんみたいなグラフマスターは知ってたテクらしい。

  • ★☆☆☆☆[4]SRM637 D1M PathGame
    コメント

    制約もっと大きくして出せばよかったなぁ。
    grandy数じゃない再帰的な感じの解法が面白い。
    制約が小さい版が既出(しかも自分解いてた・・・)だったの残念だった。全然気づかなかったなぁ。

  • ★★★★☆[7]SRM637 D1H ConnectingGame
    コメント

    phidnightさんとHexみたいなゲームをしていた時にできた。
    変な形のボードでやろうとする→引き分けが発生する→十字路がなければ引き分けにならない？→引き分けにならない条件をちょっと考えてみよう。
    問題設定がそのまんまで、自然な問題として気に入っている。

  • ★★☆☆☆[4]TCO2014 Semifinal2 Easy PlankTiling
    コメント

    適当に作った感じの問題。制約が両方10^5まででも大丈夫なのがちょっと面白い。（本番では難易度調整のため制約を落とした）

  • ★★★★★[6]TCO2014 Final Med MagicalRocketCar
    コメント

    なんかぼんやり作問してたときの問題の断片を組み合わせて問題にした。テスターの評価とか結構良くて嬉しい。

その他

  • ★★★★★[8]Advent Calendar Contest 個人コンテストということもあり、変わった問題が集まってます。パズルが題材だと作問が捗りました。
  • ★★★★☆[8]CF162 Div1E LISと仲良くなれます。
  • ★★★★☆[6]CF263 Div1C これ作ったときは「降ってきた」という感じだった。
  • ★★★★★[8]CF263 Div1D tozanが実験してたネタを一緒に研究してたら思いのほか綺麗な問題だった。
  • ★★★★★[8]ARC28 D 戻すDPはSRM478 D1Hで出ています。このテクは目からウロコで感動した覚えがあり、紹介したかったのでこの問題を作りました。
  • ★☆☆☆☆[4]KOJ00140015 昔KOJができた頃に、ストックの中にコンテストに出しにくそうな問題があったので提供しました。
  • ★☆☆☆☆[4]JOI模擬予選(非公式) おう、授業中に必死で問題作ってた記憶があるぞ。3,4,6がおすすめかなぁ。

自作問題を振り返っていて思ったのですが、それぞれの問題に作った時の思い出が詰まっていて、本当に懐かしくてたまりません。ここにきて初めて気づいた作問の醍醐味でありました。

その他のトピック

コメントアウトの小技

複数行コメントアウトって

/*
puts("Debug つらい");
*/

みたいに書きますが、これ、コメントアウトを解除したりコメントアウトし直したりするのめんどくさいですよね。だけど、

/*
puts("Debug ちょっとつらい");
//*/

こういう風に書いとくと、

//*
puts("Debug ちょっとつらい");
//*/

っていう風にスラッシュひとつでコメントアウトを解除できるので、ちょっと楽になります。

コメントアウトの小技 (応用形)

さっきの技を応用して、

//* debug output
#define pri(...) fprintf(stderr,"Debug: " __VA_ARGS__)
//*/#define pri(...)

みたいに書くと、１行目の先頭に'/'を加えるだけでpriの定義をトグルすることが出来ます。