drkenさんの記事を進める（蟻本初級編）

JOI2007C ダーツ

保留 リンクhttps://atcoder.jp/contests/joi2008ho/tasks/joi2008ho_c

考え方

N<1000だしDPで全探索して間に合うかな ただ、M<2*10⁸だから素直にテーブル作ると間に合わなそう

三角形

for文回すだけ。3周まわせないことがあるから、s-x-yとかで固定値にしたりする

Ants on a Circle

保留

考え方

跳ね返らないと考えると位置の計算は容易 1番目の蟻がどこにいるのかを考えること。衝突回数などから求まらないか？

部分和問題

bit全探索するだけ

Lake Counting

dfsするだけ、、、なんだけど書けないから書く

とりあえずここまで

Pythonのコーディング規則を読んで

Chainerのtutorialやってて、文章キレイだなぁ、コードキレイだなあと思って、コーディング規則を読むところからコードの綺麗さを直していこうと思っておる。
自分の直感と反していたこととしては、引数の中では"="の両側にスペースを開けないようにするということとか。

すごく細かいところまで練られて作られておるなぁ

バッチファイル出来たので共有

先のbat fileが作れたからおいておきます。 仕様 問題数は何問ですか？（0でmain.cppのみ作成） と表示されたら整数を入力

0の場合カレントディレクトリにmain.cppを作成 1以上の場合main.cppの入ったquestion_?ディレクトリを入力数だけ作成

テンプレートはtempuraさんのAtcorder提出分をお借りしました。 変数代入部分は難しくないので、独自に改定して使えると思います。

@echo off
setlocal enabledelayedexpansion
cd %~dp0
chcp 65001

call :MakeDirectory
REM call :SetTemplate
exit /b

:SetTemplate
set CC=#include^<iostream^>^

#include^<string^>^

#include^<algorithm^>^

#include^<vector^>^

#include^<iomanip^>^

#include^<math.h^>^

#include^<complex^>^

#include^<queue^>^

#include^<deque^>^

#include^<stack^>^

#include^<map^>^

#include^<set^>^

#include^<bitset^>^

#include^<functional^>^

#include^<assert.h^>^

#include^<numeric^>^

using namespace std^;^

#define REP(i,m,n) for(int i=(int)m ; i ^< (int) n ; ++i )^

#define rep(i,n) REP(i,0,n)^

typedef long long ll^;^

typedef pair^<int,int^>^ pint^;^

typedef pair^<ll,int^>^ pli^;^

const int inf=1e9+7;^

const ll longinf=1LL^<^<60 ;^

const ll mod=1e9+7 ;^

int main^(^)^{^

    ^

}

echo !CC! > main.cpp
exit /b

:MakeDirectory
set /p question_number="問題数は何問ですか？（0でmain.cppのみ作成）>>>"
if %question_number%==0 (
    call :SetTemplate
) else (
    for /l %%i in (1,1,%question_number%) do (
        mkdir question_%%i
        cd question_%%i
        call :SetTemplate
        cd ..
    )
)

久しぶりにbat fileやったら結構ハマった話（テンプレートファイルの作成bat）

記事更新が滞っているヤカタです。 今回競技プログラミングのためのテンプレートを作成するためにいろいろ頑張っていたらおまじないが結構あったので、備忘録を兼ねて記事にしました。

コード

@echo off
setlocal enabledelayedexpansion
cd %~dp0
chcp 65001

set BB=#include^<iostream^>^

#include^<string^>
echo !BB!

pause

出力

#include<iostream>
#include<string>

解説

@echo off: これを書かないとログがうるさくなります。（逆に言うとそれだけなので、書かなくてもいい。デバック中は外すこと推奨） setlocaldelayedexpansion: 遅延環境変数を使うためのもの。（!!で囲まれたやつをつかうためのもの） cd %~dp0: このbat fileが存在するディレクトリをカレントディレクトリとする(~で代用できる） chcp 65001: utf-8で日本語表示するためのもの。文字化けを防ぐ

^<: "<"は特殊文字なので、エスケープする必要がある ^(改行）: 改行は”\n”じゃなくてほんとの改行。改行も特殊文字なので、エスケープする必要がある。

C++の標準入力のライブラリコード

前回のC++で標準入力する色々を競技プログラミング用に改定した。

using namespace std;を使っているので、その他の利用は推奨しない

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
using namespace std;

vector<int> input_int_one_line()
{
    // １行を空白で分割して変数に入れる
    string input;
    getline(cin, input);
    istringstream iss(input);
    string str;
    vector<int> result;
    
    while(getline(iss, str,' ')) {
        result.push_back(stoi(str));
    }
    // これで1行入った

    return result;
}

int main() {
    vector<int> ans;
    ans = input_int_one_line();
    for(auto&& num : ans) {
        cout << num << endl;
    }
    return 0;
}

やっていることは前回と同じだけど、関数で分けた。入力のために毎回これだけ書いておけぬ。 複数行使いたい場合はforループで。

c++で競技プログラミングをしようと思ったら標準入力で手間取った話

c++で競技プログラミングをしようと思ったら標準入力で手間取った話

日本語で検索している時点で既に不利なんだけれど、わかりやすさがぜんぜん違うから日本語でつい検索してしまうのよね

誰かの言葉というわけではないのですが、こういうインデントが好きだったりします。ヤカタです。

競技プログラミングをRubyでやることに色々と限界を感じてきて、どうせ新しい言語を学ぶなら速度面で一番有利なC++にしようと思って最近勉強している。 Unityとの関連からC#にしようと思って数題解いたのだが、参考記事の充実さが全然違ったので結局C++に。

前置きはこのくらいで本題は標準入力について。競技プログラミングではよく、1行で空白文字で区切った数字列が与えられる事がある。ただし、いくつの数が連なっているのかがわからない。cinは改行と空白文字の区別を行わないので、std::getlineの使用と数がわからないのでVectorの使用が必須になる。

実装例

#include <iostream>
#include <string>
#include <sstream>
#include <vector>

int main()
{
    // １行を空白で分割して変数に入れる
    std::string input;
    std::getline(std::cin, input);
    std::istringstream iss(input);
    std::string str;
    std::vector<int> result;
    
    while(std::getline(iss, str,' ')) {
        result.push_back(stoi(str));
    }

    int ans = 0;
    for(auto&& num : result) {
        ans += num;
        std::cout << num << std::endl;
    }
    std::cout << ans << std::endl;
} 

参考

getlineはsplitに使える こちらの記事を参考にさせていただきました。

ABC115D

考えのまとめ。実装はまだなので、TLEが出るかもしれないけれど共有。

とりあえずN＝N_maxのときのバーガーの層の数を求めてみる。これは漸化式を解くだけ。レベルNバーガーの層の数をL(N)とおくと

L(N_max)＝2^(N_max+2)-3=2^52-3

これをすべて求めるのはO(10^8)を大きく超えるので、そのまま求めるのは不可能

問題文よりバーガーには対称性がある。その半分はB（レベルN-1バーガー）Pという形をしている。このレベルN-1バーガーには同様に対称性が適応出来る。

これらより、tmp_x = Xとして

i tmp_x>=L(N)/2のとき
ansにレベルNバーガーのPの数+1をaddしてレベルN-1バーガーに対して同様の処理を行う。このときtmp_x-=L(N/2)とする

ii tmp_x<L(N)/2のとき
ansに何もせず、レベルN-1バーガーに同様の処理を行う。このときtmp_x-=1とする

iii N=0のとき
tmp_x=0ならば0、tmp_x=1ならば1をansに足す。

でいけるはず。