No.87 Advent Calendar Problem

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 149
作問者 : yuki2006

yukicoderについて色々（+問題）

    この記事はCompetitive Programming Advent Calendar 2014の12/7の記事として書かれた記事であり、問題でもあります。
    問題文はページ下部にありますが、問題文の情報だけでは解けないかも知れませんのでご注意ください。

注意：
長文の日記です。個人用な思想な事が多く、技術的・アルゴリズム的な内容少なめです。
運営者は、レーティングが低いんで説得力がないと思います。もはやAdvent Calendar書いてもいいのかとか思ってます。つまり自分用です。
Competitive Programming Advent Calendarなのに、他の方に比べ競プロ的要素が少ないのと、
読んでも何も得られなかったという方もいらっしゃると思うので、見に来てくれたお礼に問題を出します。

この記事を読んだ後に、「だから、運営者のレーティング低いんじゃ？」とか「競プロの練習としてどうなの？」とか思う方いらっしゃると思いますが、多分その通りだと思われます。
もちろん記事に出てくる各サービスに対しての批判などではないです。

宣伝）12月7日(日)19:00から、簡単な問題から難しい問題まで10問ほど出題する yukicoder open 2014を開催するのでお暇な方はぜひ。

yukicoderができるまで　〜勉強会編〜

• 問題自体は良いアルゴリズムの練習になるので、それ自体は良かった。
• TopCoderアカウントを作成するハードルが高い。（今は楽になったのかな？
• Arenaを入れるのがハードルが高い。 (特に MacのJavaと相性が悪かった
• プラグインをいれるのもハードルが高い。
• 対応言語が少ない。（Rubyなので書いてジャッジを通せない人もいた）
• 提出・システムテストの学習コストも高い。
• 問題文が英語なのもハードルが高い。

正直、英語のサービスなのでほぼしょうがないことですね。

しばらくしてAtCoderを知って、勉強会の題材もAtCoderに移りました。

• 問題文が日本語なのはやはり良い
• いろんな言語が対応してるのも良い　
• アカウント作成・提出・ジャッジの学習コストが低い

これらは結構良くて、以前よりかは、参加者の方は楽しめたのかと思います。
しばらくAtCoderを使わせて頂いて、結構な人にAtCoderを紹介したと思います。

僕の勉強会前の準備としては、勉強会の前にAtCoderの過去問からその時の参加者に良さそうな問題を選び勉強会に出題しておりました。

しばらくしてると運営として少しめんどいなと感じるところが出てきました。
（yukicoderで実装してる機能・運用で察していただければと思います。）

途中からは、ジャッジを使わなくてもいいからと、自作の問題を勉強会に出してたりしました。
勉強会では、主にコードレビューをしてまして、皆さんのコードで色々と議論を交わしてます。
これらがyukicoderをやろうと思った理由の一つです。

yukicoderができるまで　〜ブロマガ編〜

実はこの問題の元ネタは、その勉強会の帰りの電車（特急）を乗り過ごすポカをしてしまい、新幹線で途中駅に追いつくという実話に基づいてます。

最初は、ジャッジとか全くなく、１つのケースに対してideoneに回答するスタイルでした。
みなさんご存知と思われる「nmCoder」を踏まえた形になってました。
（実、僕も何回か参加してました。

ちなみに、配信的には、「すごいHaskell本」を読破する枠をしばらくやっててその企画も終わったので、次何しようと迷走してた時でした。
初め数回は、出題しても誰も解いてくれる人がいなくて寂しい感じでした。。

しばらくはこのスタイルでやっておりまして、
途中からはいろんな方々から問題送って頂いて、なんとかやっておりまして、提出のコードも「提示したケース」では答えは合ってても、別のケースでは間違ってるときは「チャレンジ」として間違いを指摘しあってました。
（これが下の方針につながります。

このやり方で20回くらい行っていた時に
「やっぱりテストケース１つだけだと合ってるかわからないよね」ということからジャッジシステムプロジェクトがスタートしました。

そして、思考錯誤の後、ジャッジシステムができてしまいました。
最初は雑なサイトでしたが、それから、２回生まれ変わり、今のサイトになっています。

yukicoderの方針

今まで参加されている方はご存知かと思われますが、これから参加しようと思ってる方は是非、読んでから参加してみてください。

ブロマガ時代からしばらくやっていて、
僕が思うDiv2勢の競プロの練習として考えた時、欲しいことを考えたものです。
（もちろん、個人的な印象です。できる方、上位の方々はもちろん違うと思います。）

• 公平・競技性の高いコンテストより、教育目的で行う
• 知識の共有をする場所を目指す
• 多少ミス・抜けがあっても、指摘しあってレベルアップを図る
• テストケースについて
• 想定解について（持論）
• まとめ

公平・競技性の高いコンテストではなく、教育目的で行う

yukicoderは競技プログラミングサイトではなく、競技プログラミング練習サイトと名乗ることにしてます。
練習という意味ですが、AtCoderのようにちゃんと時間を決めて、不公平がないような問題・システムの設計ではなく、
競技として出されてたら非難されるような問題・運営でも、終わった後に「勉強になったと思っていただければいい」という方針で行っております。

問題としては、
典型問題でも、既出っぽい問題でも、数学問題でも、やるだけ問題でも、出題します。

特に、典型・既出っぽい問題は、最近競技プログラミングを始めた方に、逆に触れ合う機会が少ないと思うのでなるべく出していきたいと思っております。

かなり実装するだけあまり得るものがないような問題（強実装問題）でなければいいかなという感じです。

知識の共有をする場所を目指す

僕が勝手に思ってるんですけども、
競技プログラミングは、いわゆる典型問題といわれるものや、「DP」とか「最大フロー」などのアルゴリズム、BITなどのライブラリ、
初めての人には難しい「深さ優先探索」なども、どれも多かれ少なかれ知識や事前準備ゲーだと思ってます。

そんな中で「知らなかったから解けなかった」とか「持ってなかったから解けなかった」というのを減らしたいと思っています。

アルゴリズムだけじゃなく、「こうやれば楽に書けるよ」、「この言語ではこんなふうにかけます」など一般的なプログラミングテクニック、知識を「遊びながら」共有する練習場所にしたいと思っております。

目指しているものとしては、
アルゴリズムの知識の共有 というより、プログラミングテクニックの共有に近いかもしれません。

プログラミングだけでなく、作問に使うMathJax(TeX)表記などの周辺知識も共有できらいいなと思っております。
例えば、
$2015 \le N \le 10000000000=10^{10} $は

多少ミス・抜けがあっても、指摘しあってレベルアップを図る

僕自身、結構ツメが甘いミスをします。
そしてミスしてることにも気づいてないことが多々有りますし、具体的に指摘されて初めて気づくということも有ります。
（できればどんどん指摘お願いします。。）

出来る限りのことは善処するけど、それでも抜けているところは指摘してもらって、感謝しながら、 次は活かして徐々にスキルアップをしようというのがベースにあります。

逆に、ミスを指摘できるのもスキルだと思うので、何かしらミスがあるものとして、そのミスを指摘したら、何かしらインセンティブがあるようなことをしたいと思ってます。

テストケースについて

出題時にテストケースを作るのですが、
もちろんありうる全ケース揃えるのが理想ですが、現実問題厳しいです。と言うかほぼ無理です。
なので、数十個のケースだけになるのですが、本当は通らないはずのコードが$AC$してしまうというのがあると思います。

これらは、テストケースが弱いというのは確かで、なるべくなら避けるべきです。

強いテストケースの作り方も学ぶべきだとは思いますし、
強いテストケースを作ることに越したことはないです。（yukicoder以外はそうするべきでしょう）

僕がちょっと思ってるのは、練習場所としてのジャッジは「ある程度のテストケース」＋「強い人のレビュー」ではないかと思ってます。
(人任せです、すいません。強いテストケース作れる方は、もちろん違うと思います。)

個人的には、最初$AC$だったとしても、そのあとで実は$WA$だったと指摘してくれた方が練習という点ではいいと思ってます。 (ちゃんとしたコンテストだともちろんあれですし、強い方だと違うのかもしれません）

テストケース自体のミスがあるかもしれませんので最初WA/TLE/REだったとしても、指摘し分かり次第、修正・ 追加して、適宜リジャッジをします。
その時に回答者に多少ご不便をお掛けする事になると思います。ご了承ください。

想定解について（持論）

上の節から繋がる話です。

人任せで極端なことを書きますが、
「誰からも反論がなければ、とりあえず正しいとする」という考えでもいいんじゃないかと思ってます。
（もちろん極端に言えばということで、一般的には危ない考え方かと思われます。）

Writerが考えていただいた想定解・テストケースがあって、そのときのWriterが正しいと思っていたことでも、的確な反論があれば崩れます。 むしろ反論がなければとりあえず正しいんじゃないかなと思って、そんな方針でもいいかなと思っております。

誰かが気づいて指摘してもらったほうが、Writerの方にも、「見落としてたけど、こういう場合もあった」とか、「こういう知識が知れた」とか何かしら得るものがあったということで、いいのではないのかと思います。

作問の練習をしてみたいという方に対しても、
出題した問題の想定解やもろもろ違っていても、それでも解きたいという方もいらっしゃると思いますし、
誰かが指摘してくれて、気づかなかったことを知れるきっかけになればそれでいいかなと思ってます。

まとめ

コードのミスやアルゴリズムのミス、アルゴリズムの方針のミスなども、何かの練習と思ってお互い指摘、質問し合っていきましょうというのが方針です。
そのために、練習のモチベーションとなるものや機能はどんどん実装していきたいと思っております。

それできっとスキルも上達すると思うので次の機会に気をつければいいかなと、思ってます。
AtCoderやTopCoderで回答や作問に活用していただければと思う次第です。

運用者としては、作問と回答の練習場を提供したいと思っております。

もちろん、いつまでもゆるふわと言っているわけにも行かないので、発展途上ということでお許しを頂いて少しずつスキル・仕組みをしっかりしていきたいと思っております。

遠い将来的は、競技に限らず、全体的なプログラミングの練習サイトにできたらとほんのり思ってます。

yukicoderのシステム構成

• バックエンドWebサーバー Go (Revel フレームワーク/mark6)
• フロントエンド HTML/CSS/JavaScript (HTMLはRevelテンプレート、メタ言語使ってません。)
• フロントエンドライブラリ jQuery / Twitter Bootstrap / noty
• ジャッジサーバー Docker / Python / シェルスクリプト
• データベース MySQL
• データベース管理ソフト MySQLWorkBench
• バージョン管理/バックアップツール Git
• Git ホスティングサイト BitBucket
• IDE IntelliJ IDEA + Goプラグイン
• シンタックスハイライター highlightjs/ACE Editor
• WebFont M⁺ OUTLINE FONTS

Goについて

実は今まで触ってませんでした。

C++の次がDなのか、GoogleのGoなのかというくらいしか知りませんでした。
個人的にはWeb向けの言語は (Java)/PHP/Pythonと触ってましたが、やっぱり型付けがほしいなと思ってまして、これを機に触りましたが、結構気に入りました

言語的には、静的型付けですが、不要・推測可能なものを書かせないという思想な感じです。
複数の戻り値に対応してるので、多くの関数が普通の値とエラー用の戻り値があったり、使ってない変数やimportがあるとコンパイルエラーになります。

触ってる感じでは、例外機構がない (panicはあるけど）、型付け・ポインタがあるPythonという印象です。
やっぱり型付けがあるとリファクタリングする時や軽く書くときに便利です。

Revelフレームワーク

僕はCakePHPとかRailsとかのいわゆるMVCフレームワークをちゃんと触ったことなかったんですが、使ってみると便利で、
特にGoの機能でもあるHTMLテンプレートやControllerへアクセス先がroutesで指定できるのがいいですね。

scalaのplayフレームワークの思想から来たということで、play触ったことある方はわかるかも？
そもそもGo自体の標準機能も強力なのでフレームワークはいらないという声もあるかも。
ちなみに、yukicoderでは、Revelのちょっとしたバグを見つけたのでちょっと自分で修正したバージョンを使ってます。

yukicoderのHTMLのエディタで使えるタグ、属性はホワイトリストになってます。その処理はkrotonさんのmark6を使って処理してます。

jQuery/Twitter Bootstrap/noty

jQueryとTwitter Bootstrapはもはや必須のライブラリになりつつ有りますね。
（べたべたのBootstrap感だと敬遠される方もいらっしゃるようですが。

notyは保存した時などに上に出るやつです。yukicoderではver 2.2.9を使ってますが、最近ver2.3.0にバージョンアップしたそうです。

Dockerについて

最近流行りのコンテナ型の仮想環境です。
ジャッジはこの中で行ってます。

Goから ジャッジサーバーを呼び出して、Pythonで「コンパイル・実行コマンド用」のシェルスクリプトを生成し、実行をDocker内で行ってます。
ジャッジ自体はPythonで行ってます。
Pythonなのは、僕がさくっと書けるのがPythonだったからです。
あと、Java/Scala用に色々ゴニョゴニョしてます。
低負荷な仮想環境を手軽に作れるのがいいですね。

MySQLについて

MySQLは有名なRDBMS(Relational Database Management System)ですね。当初はSqliteでしたが、MySQLに移行しました。
MySQLWorkBenchで管理してます。

Gitについて

gitは言うまでもない、流行りのVCS(Version Control System)ですね。
サーバーにデプロイするときは、bitbucketにpushして、サーバーでpullしてデプロイしてます。
バックアップツールとしても使ってます。cronで自動コミット・自動pushすると色々捗ります。

IntelliJ IDEA

IDEです。
競プロでも使ってます。実は、重いけどEclipseのほうが、かゆいところに手が届くなぁとか思ったり。
プロジェクトごとにWindowを分けられるのはいいかもしれません。
コミュニティバージョンは無料です。

シンタックスハイライター

プログラムコードの部分のシンタックスハイライターはhighlightjsです。
言語を自動判定してくれるという売りですが、pythonの判定が怪しいっぽい。
近いうちに編集ページでも使ってるACE Editorに移行するかも。

WebFont

2015年5月現在廃止しました。
フォントが見にくい、表示がされない・遅いなどのトラブルがありましたし、その対策するコストも高く、Webフォントを表示しても対して、正直ユーザー体験が良くならないので廃止することにしました。
（ついでにホスティングされていたSourceForgeドメインがなくなった）
日本語のWebフォントはまだまだ時期尚早のようです。

WebFont M⁺ OUTLINE FONTS
最近有名な WebFontですね。
特に日本語のWebFontの呼び込みは遅いので遅延ローディングをしてます。導入しないと、特にSafariから見ると30秒以上全く文字が表示されませんでした。
参考：Webサイト高速化のためのWebフォントとソーシャルボタンを遅延読み込みさせるすべらない話(外部サイト)

yukicoder　特徴的な機能

• スマートサブミット　Ctrl+Vで提出できると楽だよね。
• ショートカットキー　キー一つだけでページ遷移できるよ
• 解説タブ　　解説も書けるし、解説ブログのリンクもまとめたい
• 将来的にスペシャルジャッジも含め、他に色々新機能を考えてます。

謝辞

• 現在のシステムのベースを作ってくれたり、運営として影の活躍をしてくれている　 @9610n さん、ありがとうございます。
  
• ほぼ毎回参加されて、過去問移植、ジャッジのテストをしていただいた @naoki_kp さん、ありがとうございます。
  
• この方がいなかったから、yukicoderできてなかったかも、
  たくさん問題ありがとうございます。@enuemuenuemuenu さん
• 多くの問題回答・解説・アドバイスありがとうございます @laycrs さん
  

また、問題出題していただいたみなさま、回答していただいた皆様のおかげで成り立っております。

さて、ようやく皆様お待ちかねのAdvent Calendarの問題です。

問題文

$2015$年~$N$年の間($2015$や$N$も含む)で
yukicoder no.1の出題日（記事中に記載有り）が$2014$年と同じ曜日になる回数を求めてください。

カレンダーは現実世界と同じものを用いる。

うるう年は通常の判定方法を用いる。
・$4$で割れる年はうるう年である。
・ただし、$100$で割れるときは、うるう年ではない。
・ただし、$400$で割れるときは、うるう年である。
西暦$N$年の時点でもグレゴリオ暦を用いるとする。

$N$

2015

0

2038

3

3000

141

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。