CODE FESTIVAL 2018参加記
お友達がたくさんできたのがよかったです。成績はダメでした。来年がんばりたいね。
高校時代/小学校時代の友達と再会できたしめでたしめでたし。
それにしてもEの簡単な解法に気づかず無限にバグらせて3完だったのはかなりありえなかったので来年は20位ぐらいに入れるようにがんばります。
n進数で桁和がmの倍数⇔mの倍数が成り立つような(n, m)の組合せ
タイトルにあるようなことを昨日考えてました。
試すとわりとすぐに気がつくのですが、(n, (n-1の約数))が条件を満たします。
例えば10進数では(10, 1), (10, 3), (10, 9)で、16進数だと(16, 1), (16, 3), (16, 5), (16, 15)ですね。
導出の過程を簡単に紹介します。 導出のときは、3の倍数⇔桁和が3の倍数、となるような進法が10進数以外にあるか、ということを考えます。
試してみると4進数(3: 3, 6: 12, 9: 21, 12: 30, ...), 7進数(3: 3, 6: 6, 9: 12, 12: 15, ...), 10進数, ...となっていることに気づきます。 逆に、3k+1進数のとき、これが成り立つことは帰納法を用いると示すことができます。3k+1でない場合は、小さなケースを考えるとこれが成り立たないこともすぐに確認できます。
この結果はすぐに一般化でき、mの倍数⇔桁和がmの倍数となるような進法はkm+1進数となることに気づきます。
そうすると、最初に書いた結論が導かれます。
いや〜〜〜〜かなりきれいな結果だと思うんですがこれまで一度も気がつかなかったのはなんででしょうね〜
Codechef SnackDown 2019 Round 1A
@bknshnと組んで出ました。後半３問を担当しました。
Dが難しかったのでE, Fを先に書きます。
E - Chef and Periodic Sequence
https://www.codechef.com/SNCK1A19/problems/PERIODIC
もともとこれがFでしたよねー、いつの間にか順番が変わっていました。明らかにFより簡単だったのでびっくりしてました。
まあ、数字が一つでもあると、1のインデックス（負としてもよい）が決まります。そうすると、1のインデックスの間隔は周期の倍数になるはずなので、 1のインデックス同士の間隔のGCDを取ります（1のインデックスが一つしかない場合は周期infで大丈夫）。これが最大周期です。あとは、順に見ていって矛盾してないかをチェックすればおｋです。
F - Chefland and Average Distance
https://www.codechef.com/SNCK1A19/problems/AVGMAT/
マンハッタン距離を見たら45度回すのは基本ですね〜と言って回します。そうすると、各1について、そこからマンハッタン距離がdの1の個数は、 [x-d, x+d], [y-d, y+d]の正方形の辺上の1の個数です。これは、行と列について1の数の累積和を事前にとっておくとO(1)で求まります。よって計算量はO(NM(N+M))です。
まあ、しかし定数倍がけっこう重い（45度回転させるときに600x600を確保する必要がある）ので、わりとギリギリでした。まあ、回転後に明らかにもとのグリッドを含まない領域の計算を 飛ばすとかなりの定数倍改善になるかもしれませんが、実装難易度はめちゃめちゃ上がると思います。
D - Chef and Strange Addition
https://www.codechef.com/SNCK1A19/problems/CHEFADD
部分点解法としては、popcount(a) bit立っているc以下の数をすべて列挙して、チェックすればいいです。
満点解法はDPっぽいです。
Codeforces Round #517 (Div. 2)
久しぶりの投稿です（Codeforcesは久しぶりではない）
紫になりました。やったー！
D - Minimum Path
解法は以下のSlackのトークを参考にしてください。
ところでこの問題を解いているときに、以前のHackerRankのUniversity Codesprint 5の問題を思い出しました（今回のこどふぉの問題よりずっと難しいしあんまり関係ない話です）。
これですね。今回はpathの長さが2n-1固定なので貪欲でいけましたが、どういう順序で回ってもいい場合は貪欲ではできません。その場合は、suffixに注目したDPをします。これは知っていたのですが、HackerRankはTLE解法を高速化して通したので、DPを書いたことがなく、今回の問題でけっこうびびりました。
DPにstringを保存する（つまり、dp[i]をi番目の頂点からゴールにいく文字列で最小のものとする）とMLEするので、何を保存するのかなと思いましたがdp[i]を、iから遷移できる頂点のうちもっとも辞書順で小さな頂点、としてできる。文字列の比較は、suffix arrayとかを使ってやる模様
↓↓参考↓↓
情報理工院試レビュー
東京大学大学院情報理工学系研究科コンピュータ科学専攻の院試結果の開示が届きました。
自分が受験するときに全然点数情報がわからなかったので、来年度以降調べる人用に自分のものを開示しておきます。
こんな感じです。第一志望の杉山研に受かりました。
数学と専門Iはまあこんなもんか、という感じでしたが専門IIでやらかしてしまい、まわりの人がかなり専門IIで得点をとっていたようなので 緊張してました。
何はともあれ合格してよかったです。
区間と区間がかぶる問題まとめ
【重要】面倒なので、区間の始点終点はすべて異なるとします。そうじゃない場合は適切にソートして順序付けとかしてやると大丈夫です。多分。
すでに区間がたくさんあって交差する回数を数えるやつ
No.743 Segments on a Polygon - yukicoder
すでに区間がたくさんあって、クエリが飛んでてきて指定された区間内にいくつ区間が入っているかを答える
多分一番楽？
- 座標値が収まるような配列を用意し、(Ai, Bi)に対してインデックスAiをBiにセットする
- (Pi, Qi)の間に区間がいくつ収まってるかカウントするときは配列のPi, Qiの範囲内でQi以下の要素の個数を数えます（セグ木とか使って）。
hama-du-competitive.hatenablog.com
ここにも永続セグ木を使うやつとかWaveletMatrixを使うやつなどが載ってます。
区間が動的に追加されていくやつ
無理じゃね？と思っている
競技SwarmerのためのTips
競技Swarmerを引退する（Swarm自体は続けます）のでこの機会に競技SwarmのTipsを残していこうと思います。 得点システムとかあんまり調べても出てこないと思うので自分が1年ぐらいやってわかったことなど思い出しながらまとめていきます。
競技Swarmとは
iOS/AndroidアプリのSwarmで週ごとのチェックインの総得点を競うhogeです。
チェックインしまくればいいだけでは？
競技Swarmerはプロ意識があるのでチェックイン詐称や、通過だけでのチェックインはしません。
競技Swarmerの見分け方
通常ユーザーと比較してみると得点の違いに気がつくと思います。
通常ユーザーのTL
競技Swarmerの場合
まあ基本的に得点の高いチェックインが多いです。ユーザーにもよりますが、1チェックインで100程度まで一気に稼ぐことがおおいです。
得点の稼ぎ方
Swarmで効率よく得点を稼ぐためにはSwarmの得点システムをよく知る必要があります。Swarmには何種類もボーナスが用意されておりこれらを駆使することで得点を 3倍にも4倍にもできます。
ボーナス
ステッカー (×3)
これは一番有名なやつですね。Swarmに登録されているスポットには様々なカテゴリがありますが、その中でも代表的な100種類には、ステッカーが存在し、そのカテゴリに10回チェックインすると2倍ステッカー、25回チェックインすると3倍ステッカーがもらえます。ステッカーは他ボーナスと一緒に使うと最強ですが、次のセクションで説明するようにJapanese RestaurantステッカーはItarian Restaurantステッカーよりも使いやすいなどがあり、優劣があります。10回に満たなくても+2ポイントのボーナスがあります。また、ちょうど10回目、ちょうど25回目もそれぞれ2倍、3倍のボーナスが付きますが、このときチェックイン画面ではハイライトされないため、気づかずスタンプを使わないでいるとかなりもったいないです。あと何回でアップグレードかを常に確認しましょう。
Week Streak (+15) for Category
ボーナスとしては3週目からカウントされます。そのジャンル（ステッカーが登録されていないジャンルでもよい）に連続何週チェックインしたかのボーナスです。過去最高の記録の場合+15, そうではない場合（一度途切れてしまったときなど）は3週目では+5です。また、最高記録依存ですが、最高記録に近づいたりある閾値を超えると+10, +15とボーナスが上がっていきます。
Week Streak (+15) for Spot
同様に、同じスポットに毎週チェックインし続けることでも3週目以降からボーナスが入ります。これは、StreakのUIからは確認できないので、検索欄にそのスポットの名前を入れるなりして自分で日々確認しましょう。ボーナスは同様で3週目以降からカウントされ、新記録の場合+15です。
Day Streak (+15) for Category / Spot
hoge日連続同じジャンルの場所にチェックインしてもボーナスが貰えます。同様に3日目以降からカウントされ、最高記録の場合+15です。スポットに関しても同様。
写真 (+5×枚数)
写真を撮ると1枚につき+5ポイント入ります。撮りすぎるのは得点のとり方がきれいじゃないのでやめましょう。
友達とチェックイン (+5×人数)
これはめちゃくちゃ強いです。友達と旅行するとチェックインする場所も普段よりたくさんあると思うのでいっきに得点が増えます。 友人の中で最初にチェックインによるボーナスは+2なので2人以上でチェックインする場合、あとにチェックインするのが好手です
メイヤー奪取 (+10)
これも強力です。複数人で協力してプレイする場合、毎日交互にチェックインすることで、先攻したほうがメイヤーになれ、後攻のほうが、友達とのチェックインボーナスを貰えるのでwin-winです。
移動距離 (+3 / +5 / +10 / +20)
1000マイル未満だと+3, 2000マイルまでが+5, 2000マイル超えたら+10, 4000マイル超えたら+20です。空港ステッカーは到着の空港で使うのが定石です。
ある複合施設内でのチェックイン (+1 / +2 / +5 / +10)
同じ日に複合施設内のスポットにチェックインすると、1回目には1ポイント、2回目には2ポイントとボーナスが貰えます。4回目のチェックイン以降は+10が常にもらえます。 かなり優秀なボーナスですが、案外こういう複合施設が身近になかったりします。
hoge回目のチェックイン (+5)
ジャンル、スポットともに存在するボーナスです。また、同じ友人とのチェックインに関しても、回数がカウントされ、同様のボーナスが貰えます。あまり自信はないですが、5回, 10回, 20回, 30回, ...と100回までカウントされます。200回目でボーナスはもらえませんでした。友人とのチェックインに関しては10回目からカウントスタートです。基本的に+5なんですが、回数がかなり増えると+10になった気がします（未確認）。
シェア (+2)
ツイッターなどでシェアするとボーナスが貰えます。まあ得点が上がるので嬉しいけどあまりシェアしすぎるとうるさいのでたまにだけにしてね
ここ以下はそんなに役に立たないボーナスです
メイヤー存続 (+3)
ないよりはマシという程度。
初チェックイン (+5)
まあ、記録狙いなら、同じスポットに毎週/毎日チェックインするのが正解なので活用する機会はあまりないかもしれませんが、万が一Streakを切らしてしまったときにステッカーの使い道がなくなったら初チェックインに被せます。
hogeヶ月ぶりのチェックイン (+2)
完全に不要
Trendsetter (+10)
登録されてから最初の50人のチェックインだともらえるボーナス。自分で場所を追加する場合は自明にもらえるがそうでない場合はもらえたらラッキーという程度。
FourSquare Day (+18)
4/16にもらえるという運営会社FourSquareのボーナス。+18が謎すぎる。このボーナスまで意識しだしたら相当の競技Swarmer
Happy Birthday (+20)
登録した誕生日になったらもらえる。さすがにここをいじって得点調整するのは競技Swarmerとしてやっちゃだめ
Anniversary (+5)
登録した日から1年記念にもらえる。
アドバイス
まあということでボーナスはざっくり説明しましたけどこれらをうまく複合させて使いこなすことが重要です。明らかに、努力対効果がもっとも大きいのは+15のWeek/Day Streakですが、さらにこれにも工夫できる点があります。 まず、Categoryは階層構造になっているということです。たとえば、Japanese Restaurantの親としてAsian Restaurantがあり、Ramen Restaurantの親としてJapanese Restaurantがあります。これは何を意味するかというと、たとえばラーメン屋に3日連続チェックインすると、Ramen Restaurantの記録が得られるだけではなくJapanese RestaurantおよびAsian Restaurantの連続記録も得られます。同様の階層構造でよく使うものには次のような例があります。
- Asian Restaurant > Japanese Restaurant > Udon Restaurant
- Asian Restaurant > Japanese Restaurant > Ramen Restaurant
- Asian Restaurant > Japanese Restaurant > Donburi Restaurant
- Asian Restaurant > Chinese Restaurant
- Italian Restaurant > Pizza Place
- Bar > Beer Garden
- Bar > Sake Bar
基本的に3段階の階層構造を持っているのはJapanese Restaurantしかありません（他知らないです）。ですから、効率よくポイントをためたいときは日本食を食べまくりましょう。
また、週明けは0時に得点がリセットされますが、それ以外の日の場合、日ごとの記録がリセットされるタイミングは午前4時です。なので、チェックインを忘れてもあせらないでください。まだ午前4時を回っていないなら間に合います！
さいごに
1回のチェックインでのこれまでの最高記録です。まあここまでに書いたことを完璧にマスターすればそんなに苦労せずとも抜けると思います。
