ひさしぶりに精進

問題 平面上にいくつかの点があり、いくつかの点の間は道で結ばれている。道同士は端点以外で交差しない（しても接続しない）。2点間の最短距離は、道の上のみを通り、接続点のみで道を変えたときの最短距離である。道の上から2点選ぶとき、最短距離の最大値…

問題 何種類かの硬貨がたくさんあり、それぞれ額面が決まっている。常に1単位硬貨が存在する。 ある両替機は、いくらかのお金(2単位以上)を受け付けて、次の規則で両替する。 「2枚以上の硬貨に両替する。但し、枚数は可能な限り少なくする。枚数が同じとき…

問題 グリッド状の土地があり、金鉱、銀鉱、ワークスペースがある。それ以外のマスには芝生か岩である。 何人かの労働者を雇って、金銀の採掘をさせたい。各労働者には1つずつの金鉱、銀鉱、ワークスペースが与えられる。これらは複数人の労働者で共有しては…

問題 N*Nのボードがあり、色の異なるチェッカーがある。色iのチェッカーはcheckers[i]個ある。回転させて重なる配置を同じ配置と考えるとき、何通りの異なる配置があるか。 解法 90°回転で重なるものがA通り、180°回転で重なる(かつ90°回転で重ならないもの)…

250 二進法ほげほげ。落ちた 600 6個ぐらいの文字列（a-zから構成される）がある。長さLの文字列で、それらのうちちょうどC個を含むような文字列は何個あるかをmodで答えよ。Aho-CorasickしてビットDPするだけに見えて、実際それで通る。Aho-CorasickはPKUの…

問題 真っ白な長方形のグリッドに対して次の操作ができる。「ある行か列を選んで、好きな色で全部塗りつぶす」白く塗ることはできない。すでに塗ってあるところの色は変わる。目標の状態にするには最低何回操作する必要があるか？ 解法 ある行や列に対して、…

パソコン甲子園は問題の質が劣悪ということで定評があります。今年も期待を裏切らない悪問でした。1. 110[sec]で通すことができる程度の非常に簡単な問題 2. 3. 4. やるだけ 5(生ごみ). 面倒なやるだけ 6. 実装 7. 簡単な実装 8. 面倒な実装 9. 時間足りない…